Turingmaschine

Der britische Mathematiker A. Turing entwickelte 1936 die nach ihm benannte Maschine.
Mit diesem theoretischen Maschinen-Modell kann gezeigt werden, wie ein Rechner einen Algorithmus abarbeitet. Mit anderen Worten: Mit diesem einfachen Modell einer Maschine kann man alles berechnen, was auch ein Computer berechnen kann. Dies wird Churchsche These genant. Wäre da noch die Zeitfrage ;-)

Bestandteile:

1. Speicherband - unendlich lang, kann auf jedem Feld genau ein Zeichen des verwendeten Alphabetes speichern, ein spezielles Zeichen des Alphabetes wird als Leerzeichen interpretiert.
2. Überführungsfunktion, welche jedem Paar (Zustand, gelesenes Zeichen) ein Tripel (zu schreibendes Zeichen, Kopfbewegung, Folgezustand) zuordnet
   zum Beispiel                                                   (z1, 1) -------------------------------> (z2, _, R)
                                                 (Wenn im Zustand 1 eine 1 steht,) ---> (geht die Maschine in den Zustand 2,
                                                                                                               schreibt ein Leerzeichen
                                                                                                               und bewegt sich ein Feld nach rechts)
3. Lese- und Schreibkopf - liest Bandinhalt an der aktuellen Position ein, schreibt ein Zeichen an der aktuellen Position auf das Band, bewegt sich um einen Schritt nach links oder rechts
4. Eingabealphabet
5. Bandalphabet
6. Blank- oder Leerzeichen
7. Anfangszustand und Endzustand

Pro Takt liest die Maschine über den Lese-/Schreibkopf den Inhalt des Feldes, über dem sich dieser gerade befindet. Der alte Feldinhalt wird überschrieben mit einem Zeichen aus dem Bandalphabet, welches in der Überführungsfunktion festgelegt wird.Dann wird der Lese-/Schreibkopf um genau ein Feld nach links oder nach rechts bewegt, der Automat nimmt dann einen neuen Zustand ein.

Aufgabe a) Arbeiten Sie sich die Erläuterungen auf den Seiten von Matheprisma durch, zeichnen Sie das Modell einer Turingmaschine ab und beschriften Sie es!

Beispiel für die Turingmaschine auf MathePrisma
Die Anweisungen können in die Turingmaschine kopiert werden.

1. Addition
Zwei Summanden sollen addiert werden, am Ende soll vor der Summe ein Gleichheitszeichen stehen.
also 1111+111                                                                           =1111111

Dies ist ein möglicher Algorithmus dazu:
(z1 ,1) ---> (z1 ,1,R)
(z1 ,+) ---> (z2 ,1,R)
(z2 ,1) ---> (z2 ,1,R)
(z2 ,_) ---> (z3 ,_,L)
(z3 ,1) ---> (z4 ,_,L)
(z4 ,1) ---> (z4 ,1,L)
(z4 ,_) ---> (z4 ,=,H)

2. Subtraktion
(Löschen vom Rand aus).
Dabei wird die Größe von Minuend und Subtrahend jeweils durch eine Folge von (in diesem Beipiel) Einsen dargestellt, dazwischen ein Leerzeichen _.
11111_111
Nun wird angewiesen, das - beginnend beim Subtrahenden rechts) jeweils abwechselnd am rechten Ende des Subtrahenden und am linken Ende des minuenden eine 1 durch ein _ ersetzt wird. Dies geschieht so lange, bis am rechten Ende keine 1 mehr steht.
Ergebnis: 11

(z1 ,1) ---> (z1 ,1,R)
(z1 ,_) ---> (z2 ,_,R)
(z2 ,1) ---> (z3 ,1,R)
(z2 ,_) ---> (z8 ,_,L)
(z3 ,1) ---> (z3 ,1,R)
(z3 ,_) ---> (z4 ,_,L)
(z4 ,1) ---> (z5 ,_,L) [Subtrahend rechts löschen]
(z5 ,1) ---> (z5 ,1,L)
(z5 ,_) ---> (z6 ,_,L)
(z6 ,1) ---> (z6 ,1,L)
(z6 ,_) ---> (z7 ,_,R)
(z7 ,1) ---> (z1 ,_,R) [Minuend links löschen]
(z8 ,_) ---> (z9 ,_,L)
(z9 ,1) ---> (z9 ,1,L)
(z9 ,_) ---> (z10,_,R)

Aufgabe d) Zur Festigung sollte auch die Darstellung auf Wikipedia durchgearbeitet werden.

Aufgabe e) Übung macht den Meister! Laden Sie sich die beiden Freeware-Versionen TM 1  und TM 2 herunter und üben Sie mehrere Problemstellungen.

Aufgabe f) Turingkara bietet eine Möglichkeit, eine Turingmaschine zu "konstruieren". Laden Sie sich das Programm von der Website und probieren Sie, eine Folge von Nullen und Einsen zu invertieren!

Wenn Sie auf "Aufgaben" klicken, finden Sie weitere Problemstellungen und auch Lösungen dazu.

Persistente Turingmaschine

= 3-Band-Turingmaschine mit einem Input-, einem Arbeits- und einem Output-Band

•  Input wird auf Arbeits-Band verarbeitet und nach vollständiger Bearbeitung gelangen
    Ergebnisse auf dem Output-Band in "Umwelt", danach kann neuer Input aus Umwelt verarbeitet werden
•  zwischen diesen Arbeitsschritten bleiben Inhalte des Arbeitsbandes als "Gedächtnis" erhalten
•  "Modell mit Gedächtnis"

Ameise

•  Turingmaschine mit zweidimensionalen Band
•  sehr einfache Regeln
•  kann zu komplex-chaotischen oder komplexen Strukturen führen

Fleißiger Biber

•  Turingmaschine, schreibt möglichst viele Einsen auf das Band schreibt, ohne in Endlosschleife zu geraten
•  Über die Anzahl k n von Einsen, die Fleißigen Biber mit n Zuständen schreibt,
   definiert man den Wert der Fleißigen-Biber-Funktion an der Stelle n : S( n ) = k n
•  nicht allgemein algorithmisch lösbar
•  deswegen nicht entscheidbar, ob Turingmaschine mit n Zuständen tatsächlich Kette von Einsen maximaler Länge schreibt