Karin Krichmayr sprach mit ihm über Grenzen der Informatik und die Macht der Daten. STANDARD: Warum sollte sich heute noch jemand für die Turingmaschine interessieren?

Henzinger: Die Turingmaschine ist ein Gedankenexperiment, ein ganz präzises Modell eines Computers, um herauszufinden, was alles berechnet werden kann. Das Erstaunliche ist, dass sie erfunden wurde, bevor es überhaupt Computer gab. Turing formulierte sie 1936 in dem wissenschaftlichen Aufsatz On Computable Numbers, with an Application to the "Entscheidungsproblem". Es stellte sich heraus, dass diese ganz einfache Maschine in dem, was sie berechnen kann, genauso mächtig ist wie der mächtigste Supercomputer, den es heute gibt oder den es irgendwann geben wird. Diese Maschine braucht länger, weil sie sehr kleine Schritte macht, kann aber alles berechnen, was ein Computer heute kann und in Zukunft berechnen können wird.

STANDARD: Wie erklären Sie mathematisch Unbedarften die Turingmaschine?

Henzinger: Die Maschine besteht praktisch wie jeder moderne Computer aus einem Steuergerät und Daten. Die Daten sind im Fall dieses Gedankenexperiments auf einem beliebig langen Band vermerkt, das in eine Abfolge von Zellen unterteilt ist. In den Zellen stehen die Daten, zum Beispiel Nullen und Einsen. Daneben ist das Band leer. Computer haben heute kein Band mit Nullen und Einsen, sondern einen Speicher, etwa eine Festplatte. Auf dem Band wird gerechnet. Alles, was die Turingmaschine kann, ist sich nach links oder rechts über das Band bewegen, Ziffern lesen und schreiben, je nachdem, wie es das Programm vorgibt.

STANDARD: Können Sie ein konkretes Beispiel geben?

Henzinger: Statt des Binärsystems kann man der Einfachheit halber auch das Dezimalsystem verwenden. Auf dem Band steht zum Beispiel 53$18$. Nehmen wir an, die Turingmaschine will diese Ziffern addieren. Sie macht es genauso, wie man es in der Volksschule lernt. Sie geht nach rechts zum ersten Dollarsymbol, und weiß so, dass links davon die Zahl steht, die sie addieren muss. Sie liest die Ziffer 3, merkt sie sich, geht nach rechts zum zweiten Dollarsymbol, wieder nach links, wo die zweite Ziffer ist, die 8, die sie zu 3 addiert. Das ergibt 11, also geht sie ausreichend weit nach rechts, schreibt die 1 hin, merkt sich eine 1, geht wieder nach links zum ersten Dollarzeichen und weiter zur 5 und dann nach rechts zum zweiten Dollarzeichen und wieder zurück zur 1. Dann geht sie nach rechts und schreibt die 7. Das Ergebnis ist 71. Das ist in vereinfachter Form die Berechnung: Im Grunde nichts anderes als lesen und schreiben.

STANDARD: Das Faszinierende ist also die Einfachheit dahinter?

Henzinger: Ja, genau. Das Interessante ist aber eigentlich nicht, was die Maschine machen kann, sondern was sie nicht kann. Es ist sehr überraschend, dass es bestimmte, sehr einfach formulierte Aufgaben gibt, die keine Turingmaschine und auch kein moderner Supercomputer berechnen kann. Zum Beispiel Gleichungen mit höheren Potenzen (also in denen etwa die Unbekannte hoch zwei vorkommt) und in denen die Unbekannte ganze Zahlen sind (also etwa 3 und nicht 3,5). Das sind Gleichungen, die in manchen Fällen ein Gymnasiast auf dem Papier lösen kann, jedoch im Allgemeinen kein Programm der Welt. Das heißt, wir können kein Programm schreiben, das alle Gleichungen dieser Art lösen kann. Das ist die große Leistung von Turing: nicht nur zu zeigen, was wir berechnen können, sondern auch, dass es Dinge gibt, die einfach nicht berechenbar sind durch eine Maschine.

STANDARD: Turing hat also die Grenzen der Mathematik aufgezeigt?

Henzinger: Ja. Wir bauen uns durch das Programmieren ständig unsere eigenen Welten auf. In der natürlichen Welt gibt es natürliche Grenzen, die die Physik untersucht. Aber auch in diesen selbstprogrammierten Welten gibt es sehr harte Grenzen, über die wir nicht hinauskönnen. Dieser Grenzen müssen wir uns immer bewusst sein.

STANDARD: Turing stellte 1936 auch fest: "Die Programmanalyse durch ein Programm ist unmöglich." Inwieweit trifft das auf Ihre eigene Arbeit zu? Sie arbeiten ja an Methoden zur automatischen Analyse von Software, um Fehler und Computerabstürze zu verhindern.

Henzinger: Wir arbeiten letztlich immer an Spezialfällen, an solchen, die wir lösen können. Wir können nicht hoffen, ein Programm zu schreiben, das alle Fehler in allen Programmen der Welt findet. Turing hat gezeigt, dass das unmöglich ist. Aber für ganz bestimmte Arten von Programmen können wir sehr wohl Methoden entwickeln, um Fehler zu finden.

STANDARD: Turing sagte den intelligenten, dem Menschen ebenbürtigen Computer für das Jahr 2000 voraus. Wird es diese Art künstlicher Intelligenz jemals geben?

Henzinger: Die große Bedeutung Turings in der Informatik und auch für mich persönlich ist dieses unheimlich Faktische. Da ist nichts Philosophisches an der Turingmaschine. Ich bin jemand, der nicht viel spekuliert. Ich kann nur so viel sagen: In den letzten 50 Jahren Informatik haben wir uns ständig darin geirrt, was Computer können werden. In der frühen Science-Fiction stellte man sich den Computer als denkendes Wesen vor, das Schlussfolgerungen zieht und intelligent handelt. Das ist heute noch so schwierig wie vor 20 oder 30 Jahren. Jedoch hat niemand vorhergesehen, dass Computer diese enormen Datenmengen problemlos verarbeiten können, wie sie es heute tun. Das ist die wirkliche Macht der Computer. Ich sehe keine Gefahr in einem schlauen Computer, sondern darin, dass wir uns in manchen Städten nicht mehr bewegen können, ohne videoüberwacht zu werden, und dass Computer diese riesigen Datenmengen immer schneller auswerten können.

STANDARD: Turing hat Mathematik, Logik, Informatik, Physik, Biologie, und Philosophie verknüpft - würde sich ein Eigenbrötler wie er heute entfalten können?

Henzinger: Ich glaube eher mehr. Er hatte es nicht sehr leicht. (Karin Krichmayr, DER STANDARD, 20.6.2012)