Turingmaschinen (nicht im BP)

Turingmaschinen kommen im Bildungsplan nicht vor. Weil sie aber von sehr hohem theore­ti­schem Interesse sind, werden sie hier der Vollständigkeit halber erwähnt.

Eine Turingmaschine hat keinen Stack, sondern ein Speicherband, auf dem sie ihre Eingabe vorfindet und auch ihre Ausgabe hinterlässt. Im Unterschied zum Stack (der ja immer nur Zugriffe auf benachbarte Einträge erlaubt) kann sie mit dem Schreib-/Lesekopf auf dem Band beliebig hin und her navigieren und auch weiter entfernt stehende Einträge anfahren, auslesen oder neu schreiben. Außerdem ist das Band nach beiden Seiten hin unbegrenzt.

Damit sind Turingmaschinen mächtiger als Kellerautomaten. Sie können z.B. auch kontext­sensitive Sprachen erkennen und sogar Additionen, Multiplika­tionen und andere Algorith­men ausfüh­ren, wie man sich an einfachen Problemen überlegt. Man kann den Automaten, der die Turingmaschine steuert, etwa so aufbauen, dass er beim Start zwei Zeichenketten auf dem Band vorfindet (eine der Länge 3, dann ein Trennzeichen, dann eine der Länge vier als Repräsentation von „3+4“), den Schreib-/Lesekopf in geeigneter Weise auf dem Band hin- und herfährt und dabei schrittweise eine neuen Kette der Länge 7 erstellt.

Von theoretischem Interesse sind Turingmaschinen vor allem deshalb, weil sie sogar alle Algo­rith­men ausführen können. Das ist etwas überraschend, denn Turingmaschinen sind kaum komplexer als Kellerautomaten. Dennoch markieren sie unter den Automatenmodellen auch schon das obere Ende an Mächtig­keit: Kein anderer Automatentyp kann etwas können, was eine Turingmaschine nicht kann! Diese Grenze gilt für alle heutigen und zukünftigen Mehrkern­prozessoren, Quanten- oder andere Computer egal welcher Bauart; sie betrifft jeden denkbaren Algorithmus in jeder nur vorstell­baren Programmiersprache.¹⁹

Dass Turingmaschinen gleich mächtig sind wie „vollwertige“ Programmiersprachen auf moder­nen Computern, macht sie für die Informatik noch interessanter: Ist nämlich ein Problem für Turingmaschinen unlösbar, dann kann überhaupt kein Algorithmus dieses Problem lösen.

Ein solches Problem hat schon Turing selber gefunden: Das „allgemeine Halteproblem für Turing­maschinen“ ist recht einfach zu formulieren und doch unlösbar: „Wenn man eine beliebige vorgegebene Turingmaschine A mit der Eingabe E startet – wird sie irgendwann anhalten, oder wird sie in eine Endlosschleife geraten?“ Wäre das Problem algorithmisch lösbar, könnte man eine Turingmaschine H bauen, die anhand des Bauplans von A ermittelt, ob A mit der Eingabe E irgendwann anhalten wird oder nicht. Turing beweist²⁰ dann, dass es so einen Analysator H aber nicht geben kann – und damit ist das allgemeine Halteproblem prinzipiell unlösbar, denn noch mächtigere Maschinen kann es ja nicht geben.

¹⁹ Bei Interesse an diesem Thema kann eine Recherche etwa an folgenden Begriffen ansetzen: Turing-vollständig als Kriterium: „kann diese Programmiersprache alles, was Turingmaschinen können?“ und Church‘sche These: „alle Berechnungskalküle, Automatenmodelle und Programmiersprachen, die überhaupt eine vernünftige Programmierung erlauben, sind damit schon genau so mächtig wie Turingmaschinen“

²⁰ Eine hübsche Darstellung des Beweises enthält der Kurzfilm „Proof That Computers Can't Do Everything (The Halting Problem)“, auf Youtube z.B.: https://www.youtube.com/watch?v=92WHN-pAFCs

Hintergrundinformationen: Herunterladen [odt][669 KB]

Weiter zu Sprachtypen und zugehörige Grammatiken