Rechnen und Denken

Können Computer denken?

Ein im Jahr 1950 von Alan Turing entwickelter Test versucht diese Frage durch ein spezielles Setting zu normieren: Es gibt 3 Spieler A, B und C. Spielerin C ist ein Mensch und muss auf Basis eines Frage- und Antwortspiels über einen limitierten Kanal herausfinden, wer Mensch und was Computer ist. Kann C das nicht, muss sie davon ausgehen, dass auch Computer denken können (oder vorsichtig formuliert: C stellt fest, dass sie beim Output von denkenden Wesen und von Computern über diesen Kanal keinen feststellbaren qualitativen Unterschied erkennen kann).

Würde C ausschließlich die Meldungen zu ihrem Geburtstag auf Facebook einem Turing-Test unterziehen, könnte sie sie zu dem Schluss gelangen, dass ein Großteil ihrer “Freunde” sich wie einfallslose Maschinen verhalten, jedoch mehr Rechtschreibfehler machen.

Der Streit ist vorprogrammiert, wenn es um die Unterscheidung von Simulation und echtem, menschlichen Verhalten geht. Als ob wir ignorierten, dass die Tricks der Simulation von unserem eigenen Wunsch ausgehen, uns selbst zu überraschen, zu täuschen oder zu entlasten. Die zum Leben erwachte, verselbständigte Maschine ist von uns selbst angetrieben.

Zum 100. Geburtstag von Alan Turing schiebe ich den Turing-Test zur Seite. Zum Vorschein kommen die Turing-Maschine und die Frage nach der Relevanz in Informatikforschung und Softwareverwendung.

Die Turingmaschine und die Grenzen der Softwareanalyse

Die Turingmaschine ist ein Gedankenexperiment, in dem einen fiktive Maschine Zeichen auf einem Band manipuliert. Es gibt vier Operationen: Der bewegliche Schreib-/Lesekopf kann sich nach links und rechts bewegen sowie ein Zeichen an der aktuellen Position lesen bzw. überschreiben. Wann welche Operation ausgeführt wird, wird durch den aktuellen Zustand und einer Tabelle mit Regeln der folgenden Art bestimmt: Wenn Zustand x, dann wechsle in Zustand y und führe Operation z aus. Auf diese Art lässt sich jeder Algorithmus beschreiben und analysieren. Das Prinzip ist bis heute dasselbe geblieben, sodass man (mit genügend Geduld und Platz) jeden Algorithmus als Turingmaschine beschreiben könnte.

Turing hat mit Hilfe einer fiktiven Maschine die Grundlagen der Berechenbarkeitstheorie stark geprägt. Beispielsweise hat er mit dem sogenannten Halteproblem gezeigt, dass es kein Verfahren, also kein Programm, gibt mit dem wir für ein beliebiges Programm p feststellen können, ob p zu einem Ende gelangt. Es stellt sich heraus, dass alle interessanten Eigenschaften von p nicht hinreichend von Programmen entschieden werden können.

Software die wir im Alltag verwenden sind Betriebssysteme, Internet-Browser, Textverarbeitungsprogramme. Diese sind zunehmend unübersichtlich geworden. Microsoft Windows XP basiert auf 45 Millionen Zeilen Programmcode. Obwohl wir jedes Snippet Programmcode von Microsoft Windows analysieren könnten, reicht unsere Lebenszeit nicht aus, jede Zeile zu analysieren. Im Unterschied dazu ist es möglich, ein Buch und unter Umständen sogar das ganze Lebenswerk von Niklas Luhmann zu lesen.

Motiviert durch zunehemende Komplexität und Unübersichtlichkeit von Software nimmt die Informatikforschung zwar die Ergebnisse von Turing hin, versucht aber trotzdem, Verfahren zu entwickeln, die Eigenschaften von Programmen extrahieren. Die Art und Weise, mit Hilfe eines Programms Eigenschaften eines anderen Programms festzustellen, wird in der aktuellen Informatikforschung Softwareanalyse genannt, wobei zwischen statischer und dynamischer Softwareanalyse unterschieden wird. Während dynamische Softwareanalyse das Programm während es läuft (“zur Laufzeit”) mit Hilfe eines Analyseprogramms analysiert, betrachtet statische Analyse nur den Programmcode und  die Struktur desselben. Die Ergebnisse von Turing bilden die äußersten theoretischen Grenzen vor allem der statischen Softwareanalyse.

Was mich ausgehend von Turing interessiert ist die Komplexität heutiger Software. Ich betrachte also nicht Text zum Zwecke der Kommunikation sondern Programmcode zum Zwecke der automatischen Abarbeitung von Aufgaben. Dabei sind zwei Dimensionen zu betrachten, durch die sich verstehen lässt, warum Software die Eigenschaft hat, unübersichtlich zu werden. Eine dritte Dimension weist auf die materielle Abhängigkeit von (noch so verschachtelter) Software hin. Unter Berücksichtigung dieser Dimension kann die Tendenz zur Komplexitätssteigerung von Software sowohl ausgenutzt, als auch gebremst und gedreht werden, was der Softwareanalystin zumindest lokale Übersichtlichkeiten eröffnet.

Räumliche Dimension – Software als Labyrinth

Abhängig von den konkreten Eingabewerten einer Software, durchwandert der Computer einen von vielen möglichen Pfade durch die Software. Die Gesamtheit der möglichen Pfade bildet ein Labyrinth, genauer ein geflechtartiges Gebilde (“control-flow graph”). Die Anzahl der möglichen Pfade wächst exponentiell mit der Anzahl an Verzweigungen des Geflechts, d.h. praktisch: Je mehr Zeilen ein Programm hat, desto mehr mögliche Pfade hat es in der Regel.

Obwohl jede Instruktion, jedes Pfadstück, präzise definierte Effekte bewirkt, gelingt es uns rein syntaktisch nicht, all jene Wege zu finden, die die gewünschten Eigenschaften erfüllt, ohne den Weg tatsächlich zu gehen. Denn nicht alle Eigenschaften sind direkt aus den Instruktionen abzuleiten, manche ergeben sich erst zur Laufzeit. Dies ist ein Grund, weswegen pragmatische Softwareentwicklerinnen davon ausgehen, dass viele Fehler erst nach der Publikation der Software gefunden werden. Sie rechnen manchmal damit, dass selbst kleine Änderungen in einer unscheinbaren Routine zu unvorhergesehenen Folgen (z.B. Abstürzen) führen können. Die Betrachtung eines Ausschnitts des Programmcodes ist keine Garantie dafür, dass man ihren Einfluss auf das Gesamtverhalten des Systems verstanden hat.

Sowohl Menschen als auch Maschinen gelangen durch Explosion der Möglichkeiten an ihre Grenzen.

Zeitliche Dimension – Software lebt

Selbst wenn wir für wichtige Programme die labyrinth-artige Struktur von Software in den Griff bekommen und durch Austesten, manuelle Code-Reviews oder annäherungsweise Softwareanalyse Fehlfunktionen finden können, ist weiters zu betrachten, dass Software ständig in Bearbeitung ist.

Eine Referenzversion des Betriebssystems Linux kann schon nach 2 Wochen an zentralen Stellen von der Entwicklergemeinschaft modifiziert sein. Die Analyse hinkt aktiven Codeprojekten hinterher, da diese ständig “work in progress” sind.

Software ist natürlicher geworden, durch unsere kontinuierliche Partizipation an ihr.

Materielle Dimension – Software läuft auf Hardware

Die letzten beiden Dimensionen betrachten die Sphäre von Software isoliert von der Hardware auf der sie letztlich läuft. Gerade jetzt, wo Software in voller Blüte steht und High-Level-Programmiersprachen direkten Hardwarezugriff vermeiden, könnte man übersehen, dass unsere elektronischen Geräte auf hoch-standardisierten Bauteilen beruhen. Anders gesagt: Nur wenn die Hardware mitspielt,  d.h. Millionen von Transistoren, Speicherkondensatoren, etc. sich entsprechend ihrer Spezifikation verhalten, folgt ein Computer den formalen Instruktionen der Softwareentwicklerin.

Um physikalischen Ausfällen temporär zu entgehen, setzt man etwa in großen Rechenzentren auf Virtualisierung ganzer Rechner. Eine virtuelle Maschine ist ein Stück Software, das mit einer physikalischen Maschine funktional äquivalent ist. Programme, die in der virtuellen Maschine laufen, merken keinen Unterschied. Sie verhalten sich, als ob sie direkt mit dem Speicher und Prozessor der physikalischen Maschine arbeiten. Tatsächlich spielt eine Software die Rolle einer physikalischen Maschine und vermittelt die Interaktion zwischen Software und Hardware. Der dadurch entstandene Spielraum kann produktiv genutzt werden.

Was ändert Virtualisierung an der Tatsache, dass am Ende der Kette von Softwarekomponenten eine physikalische Maschine stehen muss? Nicht viel, aber doch Entscheidendes. Die Vermittlungsfunktion einer virtuellen Maschine führt zu einer Abkapselung mit vielen Vorteilen. Virtuelle Maschinen können bequem im Netzwerk transferiert werden, sodass man Rechenkraft (computational power) besser nutzen kann. Bei höherer Auslastung werden virtuelle Maschinen automatisch auf weitere physikalische Maschinen kopiert, um Engpässe zu vermeiden. Man erhält also programmatische Kontrolle über das Verhalten von Rechnern (siehe z.B. Amazon Elastic Compute Cloud).

Das Verhältnis zwischen physikalischer und virtueller Maschine ähnelt dem zwischen Turingmaschine (TM) und Universeller Turingmaschine (UTM).

• Während die Turingmaschine für genau ein Programm ausgelegt ist, kann eine UTM das Programm einer jeden beliebigen TM abarbeiten. Sowohl UTM als auch TM basieren auf den vier Operationen (Links,Rechts,Lesen,Schreiben).
• Am Grundprinzip eines Rechners ändert Virtualisierung nichts. Man benötigt weiterhin einen (oder mehrere) Prozessor sowie Arbeitsspeicher. Doch durch Virtualisierung können beliebige Rechner so wie andere Programme verwaltet werden.
• So gesehen ist eine virtuelle Maschine die Aufhebung einer physikalischen Maschine: (1) Sie unterbricht den Direktkontakt von Software mit den physikalischen Bauteilen durch eine Vermittlungsebene. (2) Sie behält den Bezug zur physikalischen Maschine, da sie selbst ihre Funktion nur mit Hilfe der physikalischen Maschine erfüllen kann. (3) Sie wertet die Möglichkeiten, die durch eine einzige physikalische Maschine entstehen auf. So lassen sich auf einem handelsüblichen PC parallel ein Smartphone, ein alter Commodore64 und ein PC mit einem Macintosh-Betriebssystem betreiben.

Stelze, Hochstand, Flug

Die diesjährige Jahresversammlung der Österreichischen Computergesellschaft wurde Alan Turing gewidmet. Dort fand sich die Aussage “Es gibt einen Rückstoßeffekt von der Materie ins Allgemeine”.

Die “Bezwingung” der Natur durch Technik besteht darin, dass wir auf Stelzen gehen. Dadurch erscheinen wir größer, doch bewirkt der Abstand zum Boden, dass wir sensibler für Unebenheiten werden. Wenn man beim Stelzen-gehen zu Boden fällt, fällt man härter. Ich möchte daher nicht von Bezwingung, sondern von Konzentration der Natur durch Technik sprechen. So nutzen etwa Computer die Eigenschaften von spezifischen Materialien (Silizium, Metalle der seltenen Erden), um gewünschte Effekte zu erzielen. Durch die alltägliche Verwendung von elektronischen Geräten sind wir auf spezifische Eigenschaften von Materialien angewiesen. (Ein Emmentaler besitzt diese Eigenschaften nicht.)

Die Virtualisierung macht einerseits das Vorhandensein von physikalischen Maschinen zur Gewohnheit und verstärkt daher unseren Bedarf an Materialien mit speziellen Eigenschaften (Eine Aufhebung ist auch eine Bestätigung.) Andererseits ist die Vermittlungsrolle einer virtuellen Maschine ein Gewinn an Übersichtlichkeit, was zurück zur Softwareanalyse führt. Denn virtuelle Maschinen können nicht nur zur ökonomischen Verwaltung von Rechenkraft eingesetzt werden, sondern auch zum Aufzeichnen der Interaktionen zwischen Software und Hardware. Als ob die physikalische Maschine ein Zoo und die virtuelle Maschine ein Gehege mit Hochstand wäre. Während sich die zu untersuchende Software wie üblich verhält, kann man Teile der labyrinthischen Binnenstruktur sowie Auswirkungen einzelner Instruktionen auf das Gesamtverhalten des Systems analysieren.

Virtualisierung, d.h. Aufhebung der Interaktion zwischen Software und Hardware, trägt zum Aufbau zusätzlicher Komplexität bei (macht also global gesehen die Sache softwareseitig unübersichtlicher), andererseits kann man diese Komplexität für lokale Übersichten nutzen. Vielleicht verhält es sich mit dem Nachdenken ähnlich:

• Wir schweben nicht über der Welt mit einem unbegrenzten Blick.
• Ein gut gebauter Hochstand hilft uns, über lokale Dynamiken klar zu werden.
• Das Bauen des Hochstand und das Heraufklettern setzen zusätzliche Dynamiken frei, die jedoch nicht im Fokus der Aufmerksamkeit stehen (außer der Hochstand beginnt zu wackeln).