Alan Mathison Turing

Über Turingmaschinen gibt es eine ganze Reihe von Büchern. Sie gehören an jeder mir bekannten Universität zum Grundstudium Informatik. Jede Einführung in die theoretische Informatik dreht sich in gewisser Weise um sie (z.B. Uwe Schoening " Theoretische Informatik - kurzgefasst " bei Spektrum - Akademischer Verlag, ca. €20,-).

Das Konzept der Turingmaschine (im weiteren TM) geht auf einen genialen Einfall des englischen Mathematikers Alan Turing zurück.
(Haben Sie schon mal etwas über die deutsche Kodier- bzw. Dekodiermaschine ENIGMA im zweiten Weltkrieg gehört bzw. über die Leute,  die sie geknackt haben? A.M. Turing war einer davon! Es gibt einen lesenswerten Roman darüber: "ENIGMA" von Robert Harris.)

Eine Turingmaschine ist keine Maschine wie eine Bohrmaschine. Sie ist auch kein Programm, sondern eher ein abstraktes Konzept. Dieses Konzept kann z.B. durch ein PASCAL- Programm simuliert werden. Ein solches Simulationsprogramm kann weiter unten auf dieser Seite downgeloaded werden.

Der Sinn von Turingmaschinen liegt in ihrer Bedeutung fuer die Berechenbarkeitstheorie, nicht in der Erstellung konkreter Funktionen. TM's, die etwas Konkretes ausführen bzw. berechnen, sind meist nur Spielerei, oder Übungsaufgaben, um sich mit dem Konzept vertraut zu machen. (BTW: Die "fleissigen Biber" (engl.: Busy Beaver) sind eine Spielerei mit einem ernsthaften Hintergrund - siehe weiter unten.)

1. Bedeutung der TM für die Berechenbarkeitstheorie

Es gilt die folgende grundlegende Aussage in all ihrer Schärfe:
 

Alles was berechenbar ist, ist durch eine Turingmaschine berechenbar!

Auch die Umkehrung:


Alles was nicht durch eine Turingmaschine berechnet werden kann, ist überhaupt nicht berechenbar!

In der formalen Aussage der theoretischen Informatik lauten die obigen Aussagen, die als CHURCHsche These bekannt sind, folgendermaßen:
"Die durch die formale Definition der Turing-Berechenbarkeit (äquivalent: WHILE-Berechenbarkeit, GOTO-Berechenbarkeit, μ-Rekursivität) erfasste Klasse von Funktionen stimmt genau mit der Klasse der im intuitiven Sinn berechenbaren Funktionen überein."

Berechenbar heißt in diesem Sinne, dass ein Algorithmus zur Lösung des Problems existieren muss. Das berühmte Beispiel Kuchenbacken (Algorithmus = Kochrezept) ist also ein Beispiel für eine berechenbare Funktion in obigem Sinne (Nur um zu zeigen, wie weit der Berechenbarkeitsbegriff geht).

Eine TM besteht aus einem unendlich langen Speicherband, dem Turingband, und einem Lesekopf, der jeweils genau ein Zeichen des Bandes lesen und schreiben kann. Ausserdem kann er - abhängig vom gelesenen Zeichen - einen von  mehreren möglichen, aber nur endlich vielen, Zuständen annehmen.

Das ist so zu verstehen:
Die TM liest ein Zeichen auf dem Band, dann schreibt sie ein Zeichen an diese Stelle des Bandes, abhängig davon, welches Zeichen sie gerade gelesen hat, und in welchem Zustand sie sich gerade befand. Danach ändert sie ihren Zustand, ebenfalls abhängig von dem gelesenen Zeichen und dem alten Zustand und bewegt das Turingband entweder eine Stelle nach links, nach rechts oder gar nicht.
Ist der neue Zustand ein ausgezeichneter Zustand, ein Endzustand, so bleibt sie stehen.

(Ausführlicher und exakter kann diese Beschreibung im Buch von Schöning - siehe oben nachgelesen werden, anschaulicher und besser zu verstehen ist sie in A.K. Dewdney, "Der Turing-Omnibus", Springer-Verlag)

Wie die TM ihre Position, ihren Zustand und das Zeichen auf dem Turingband ändert, wird durch die sogenannten Überfuehrungsfunktionen beschrieben. Sie werden z.B. so angegeben:
                           A0 → B1L
Das bedeutet: Ist die TM im Zustand A und liest sie eine 0, so geht sie in den Zustand B, schreibt eine 1 und bewegt das Band nach links.

Mit einer so genial einfachen Maschine ist tatsächlich alles berechenbar, was überhaupt berechenbar ist. Ein echter Hammer! :-)

Eine solche Maschine ist natürlich hoffnungslos ineffektiv bei der Bearbeitung von konkreten Problemen. Sie wird meist "nur" als theoretisches Konzept verwendet.  Dabei hat sie allerdings überwältigende Bedeutung. So kann mit ihrer Hilfe zum Beispiel das zentrale Problem der Informatik, das Halteproblem (leider negativ) beantwortet werden.

TM's, die tatsächlich etwas Konkretes berechnen sind - wie gesagt - meist nur Spielerei, oder zum Üben.

Mit allem, mit dem gespielt werden kann, wird auch gespielt.

So dachte sich der ungarische Mathematiker Tibor Rado 1962 das busy-beaver- Problem aus:

Die gestellte Frage lautet:
 

Busy- Beaver- Problem: Es ist eine TM gegeben, die nur eine bestimmte Anzahl von Zuständen haben darf. Das Turingband ist leer. Wie viele Zeichen kann sie maximal schreiben?

Bemerkung: Es ist überhaupt kein Problem, eine TM zu entwerfen, die unendliche viele Zeichen schreibt. Aber die TM soll ja irgendwann anhalten. Das macht das Problem so schwierig.

Eine TM mit 1 Zustand kann maximal 1 Zeichen schreiben, eine mit 2 Zuständen maximal 4 Zeichen, eine mit 3 Zuständen maximal 6 Zeichen, eine mit 4 Zuständen maximal 13 Zeichen.

Es ist bis heute unbekannt, wieviele Zeichen eine TM mit 5, 6 oder mehr Zuständen schreiben kann!
Man weiss nur, dass es zwei TM's mit 5 Zustaenden gibt, die 4098 Zeichen schreiben koennen. Ob es welche gibt, die mehr schreiben, weiß niemand.

Bei der Anzahl der Zustände der fleißigen Biber werden die jeweiligen Endzustände nicht mitgezählt.

Beispiel:
Fleißiger Biber mit 3 Zuständen (ohne Endzustand):
 

Fleißiger Biber mit drei Zuständen
Keine Eingabe -> Return
0,spc,I,r,1
0,  I,I,l,2
1,spc,I,l,0
1,  I,I,r,1
2,spc,I,l,1
2,  I,I,n,-1
(Die TM ist in der Notation aufgeschrieben, wie sie für das untenstehende Simulationsprogramm benötigt wird. Eine Zeile ist so zu lesen: Zustand vor dem Lesen, gelesenes Zeichen, zu schreibendes Zeichen, auszuführende Bewegung, anzunehmender Zustand.)

Der gleiche Biber als Automat dargestellt:



(Eine abgeänderte Fragestellung des Biber-Problems ist die folgende: Welche TM mit n Zuständen - ohne Endzustand - macht möglichst viele Arbeitsschritte, stoppt dann und hinterlässt ein leeres Band?)

Interessant ist dabei die Feststellung, daß die Funktion Σ(n), die angibt, wie gross die maximale Zahl von Zeichen ist, die eine TM mit n Zuständen (ohne Endzustand) ausgeben kann, zwar wohldefiniert, aber  nicht durch eine TM und somit überhaupt nicht berechenbar ist!!!!!!!!!!!!!

Das Simulationsprogramm

Abb.: Die Turingmaschine in Aktion:

Download:

Hier kann ein ZIP-File turing.zip downgeloaded werden, der sowohl das Simulationsprogramm (inkl. Source in Turbo-Pascal 6.0) sowie mehrere Beispiel-Turing-programme enthält. Ebenfalls enthalten ist die untenstehende Anleitung. Als Bonbon ist noch ein Simulationsprogramm in zwei Versionen (rekursiv und nicht-rekursiv) für die Turmiten (zweidimensionale Turingmaschine) hinzugefügt.

Anleitung:

Die Turingmaschine TURING.EXE wurde (schon vor längerer Zeit) für MS-DOS geschrieben. Man kann sie auch heute noch verwenden, indem man z.B. unter Windows XP bei Ausführen "cmd" eingibt, also den Kommandozeileninterpreter startet. Nachdem man mit "cd" in das Verzeichnis der Turingmaschine gewechselt hat, können die untenstehenden Startbefehle gegeben werden.

Das Simulationsprogramm TURING.EXE interpretiert ein Turingprogramm, das in einer separaten ASCII-Datei geschrieben stehen muß. Ihr Name wird beim Aufruf mitgegeben, z.B. TURING T1.DAT. In diesem Beispiel wird das Turingprogramm in der Datei T1.DAT interpretiert. Wird kein solcher Dateiname übergeben, so hält die TM mit einer entsprechenden Meldung an.

Beim Schreiben des Turingprogramms müssen bestimmte Konventionen eingehalten werden, die zwar von der Theorie der Turingmaschine her nicht nötig sind, aber von der Interpretation durch TURING.EXE für eine korrekte Durchführung unabdingbar sind:

Kopfdaten:

Die ersten beiden Zeilen der Turingprogrammdatei müssen zwei nichtleere Strings enthalten:
Der erste String enthält die Bezeichnung des Turingprogramms (Überschrift).
Der zweite den Prompt der Eingabeaufforderung.
(Am besten Beispiele T1.DAT bis T3.DAT aus dem ZIP-File ansehen.)

Es sind alle ASCII-Zeichen erlaubt, eine Prüfung auf die Zugehörigkeit der Eingabe zum aktuellen Eingabealphabet erfolgt nicht und ist der Sorgfalt des Benutzers überlassen.

Auch die Korrektheit der Ausgaben der Turingmaschine auf das Turingband wird nicht geprüft und ist in diesem Fall der Sorgfalt des (Turing-)Programmierers überlassen.

Bei den Zuständen ist die folgende Konvention unbedingt einzuhalten:
Die Zustände werden mit Integer-Zahlen bezeichnet. Die Zahl 0 beschreibt immer den Startzustand, Endzustände werden durch negative Zahlen beschrieben.

Bei der Formulierung der Übergangsfunktionen muß die folgende Reihenfolge beachtet werden. Jede Übergangsfunktion muß in einer Zeile stehen.

Bsp.:

4, spc, |, R, -1
0, |, |, L, 0
An erster Stelle steht der aktuelle Zustand der Turingmaschine und an zweiter Stelle das Zeichen, für das diese Übergangsfunktion zutrifft, falls es vom Turingband gelesen wurde. Befindet sich die Turingmaschine also in diesem Zustand und liest sie gerade dieses Zeichen vom Turingband, so führt sie die aktuelle Übergangsfunktion aus.

Danach folgt das neue Zeichen, das im Falle der Ausführung auf das Turingband geschrieben wird.

An vierter Stelle dürfen nur die Buchstaben R,L, oder N stehen. Sie spezifizieren die Bewegung, die der Kopf der Turingmaschine ausführt.

Als letztes steht der Zustand, den sie nach Ausführung annehmen soll.

Alle fünf Angaben werden durch Kommas getrennt. Nach der Angabe des neuen Zustandes darf nichts mehr in der Zeile stehen. Einen Sonderplatz nimmt die Zeichenfolge spc ein. Sie darf an Stelle des aktuellen oder des neuen Zeichens
(zweite und dritte Angabe) stehen. Sie sollte für das Leerzeichen auf dem Turingband verwendet werden.
Soll das Leerzeichen direkt angegeben werden, so muß bei der augenblicklichen Programmversion der Punkt "."
benutzt werden.

4, spc, |, R, -1
und
4, ., |, R, -1
sind also identisch.

Die fleißigen Biber sind den Büchern "Der Turing-Omnibus" von A.K.Dewdney und "Technische und theoretische Informatik" von Gasper, Leiss,... beim  bsv entnommen.

PS.: Die Turingmaschine ist so nebenbei entstanden, ohne maximale Sorgfalt beim Programmieren. Es ist also anzunehemen, daß sie noch den einen oder anderen Fehler enthält. In diesem Fall bitte ich um Entschuldigung. OStR März