Was ist keine Turingmaschine?

Michael Völker
a) Taschenrechner
b) Tischgenerator
c) Mathematisches Modell
d) Fleißiger Biber

Antwort:

Eine Turingmaschine ist in erster Linie ein mathematisches Modell. Der Tischgenerator ist eine Maschine zur Erzeugung von Elektrizität und damit keine Turingmaschine.

Erklärung:

Eine Turingmaschine kann man sich bildlich recht einfach vorstellen. Zunächst braucht man ein unendlich langes Band Papier, das in Felder unterteilt ist. Über diesem Band wird ein Lese- und Schreibkopf, von einem Programm gesteuert, jeweils ein Feld nach links oder rechts bewegt. Bei jedem Feld kann der Kopf ein Zeichen drucken, ein Zeichen lesen oder gar nichts machen, wobei genau genommen ein bestimmtes Zeichen für "kein Zeichen" verwendet werden muss. Damit hat eine Turingmaschine drei Funktionen: Lesen, schreiben und den Kopf bewegen.

Ein einfaches Beispiel. Auf das Band ist eine beliebige Anzahl von Einsen gedruckt. Rechts der letzten Eins soll ein weiteres Zeichen hinzugefügt werden. Der Kopf steht auf der ersten Eins von links. Das Programm sagt dem Kopf, dass er zunächst das aktuelle Feld lesen soll. Liest er "1", bekommt er die Anweisung, ein Feld nach rechts zu rucken. Liest er nichts, druckt er eine Eins und bleibt dann stehen. Auf diese Zeile des Programms folgt ein Befehl zum Stoppen der Maschine. Ist die Anzahl der Einsen endlich, wird die Maschine auch nach einer gewissen Zeit stoppen. Ist jedoch das ganze Band, das ja unendlich lang ist, mit unendlich vielen Einsen bedruckt, wird die Turingmaschine nie stoppen können.

Das genügt völlig, um alle mathematischen Grundfunktionen auszuführen. Stellt man Zahlen nicht durch die Ziffern 0 bis 9 dar, sondern im Binärsystem – die Neun wird dann etwa als 1001 symbolisiert –, kann man die Turingmaschine ganz gut als Taschenrechner verwenden. Das ist vielleicht etwas aufwändig, aber es geht.

Soll die Turingmaschine möglichst viele Einsen auf das Band schreiben, steht man vor einem Problem. Wenn das Programm nur aus dem Befehl "Wenn das gelesene Feld leer ist, schreibe eine Eins" besteht, wird die Maschine nie anhalten. Eine Turingmaschine, die eine festgelegte Anzahl von Einsen druckt, nennt man "Biber". Der ungarische Mathematiker Tibor Radó fand eine Funktion, mit deren Hilfe es möglich ist, mehr Einsen als alle anderen Turingmaschinen, die (von der eigentlichen Funktion abgesehen) gleich konfiguriert sind, auf das Band zu drucken – und trotzdem nach endlich langer Zeit anzuhalten. Weil die so modifizierte Turingmaschine immer mehr Einsen druckt als alle anderen Biber, also besonders fleißig ist, nannte Radó sie "fleißiger Biber".

Entwickelt wurde die Turingmaschine 1936 vom britischen Mathematiker Alan Turing. Zur Lösung so genannter Entscheidungsprobleme entwarf er ein mathematisches Modell. Ein Entscheidungsproblem war damals die Frage, ob die Mathematik entscheidbar ist oder nicht. Versteht man die Mathematik als Sprache, dann heißt das: Kann man für jeden Ausdruck feststellen, ob er zur Sprache gehört oder nicht? Der deutsche Mathematiker David Hilbert hatte die Frage anders formuliert: Gibt es ein Verfahren, das für jede Aussage deren Wahrheit beziehungsweise Falschheit feststellt? Da Turing "Verfahren" so definierte, dass es rein mechanisch, ohne höhere Einsicht, ausgeführt werden können muss, kam er zu dem Begriff der "Maschine". Diese Maschine kann natürlich nicht gebaut, sondern nur in der Sprache der Mathematik formuliert werden. Turing konnte damit die Frage allerdings noch einmal umformulieren: Gibt es eine Turingmaschine, die für alle möglichen Turingmaschinen und alle möglichen Eingaben entscheidet, ob die Turingmaschine mit dieser Eingabe anhält oder nicht? Die Antwort lautet nein. Und damit war bewiesen, dass die Mathematik nicht entscheidbar ist.

Was ist keine Turingmaschine?