Die Turing - Maschine

Die "Turing-Maschine" liegt auch als Freeware - Auskopplung des Mathematikprogrammes "Funktion" vor. Es bestehen keine Nutzungseinschränkungen.

Download Turing-Maschine

Was ist eine Turing - Maschine
Die Turing - Maschine wurde 1936 von dem englischen Mathematiker ALAN TURING als mathematisches Modell zur Untersuchung prinzipieller Fragen der Berechenbarkeit geschaffen.
Sie ist eine Präzisierung des bis dahin mehr oder weniger allgemeinen Algorithmenbegriffes. Die Turing - Maschine ist kein Modell für die Arbeitsweise realer Computer.  Vielmehr wurde hier die Zerlegung algorithmischer Prozesse in einfache Operationen bis an die Grenze getrieben.
Dies schmälert allerdings nicht ihre mathematische Bedeutung. Eine Turing - berechenbare Funktion ist, soweit Speicherbedarf und Rechenzeit ausreichen, auch auf realen Computern berechenbar.
Umgekehrt sagt die These von CHURCH, dass jede intuitiv berechenbare Funktion auch Turing - berechnbar ist.

Aufbau und Arbeitsweise
Die Maschine besteht aus
- einem äußeren Speicher (Endlosband)
- einem inneren Speicher (Strukturschema, Register)
- Lese/Schreibkopf

Das vorliegende Programm simuliert eine einfache Turing - Maschine.  Als äußeres Alphabet dient (zunächst) {1,+}, wobei + für das Leerzeichen steht. Diese Symbole können vom Endlosband gelesen und darauf geschrieben werden.
Eine Zahl wird durch nacheinanderfolgende Zeichen "1" dargestellt, also 3 = "111" 7 = "1111111" usw. Beim Programmstart und Programmende sollte der Lesekopf des Bandes auf der ersten "1" der Zahl stehen. (siehe Abbildung). Zwei Zahlen werden durch ein Leerzeichen (+) getrennt, also 2 und 3 ="11+111".

Die Arbeit der Maschine wird über die Register gesteuert. Dabei bedeuten in einer Zeile:
 
Beispiel
1 
+ 
L 
2 
Bedeutung gelesenes Zeichen zu schreibendes Zeichen Richtung der Lesekopfverschiebung neues Register
Es wird also,  wenn auf dem Band das Zeichen 1 steht:
- das Leerzeichen "+" geschrieben (anstelle von 1)
- der Lesekopf nach links verschoben
- das Register 2 aufgerufen

Eine Karte enthält bei unserem einfachen Alphabet genau 2 Zeilen. Die zweite Zeile der Karte bestimmt die Arbeit, wenn das Zeichen "+" gelesen wird. Durch die Gestaltung dieser Karten kann nun die Arbeit der Maschine gesteuert werden. Die Maschine beendet ihre Arbeit, wenn gelesenes und geschriebenes Zeichen identisch sind und keine Bewegung des Bandes sowie der Karte stattfindet, also z. Bsp. 1 1 S 3     oder   + + S 3 für die Karte Nummer 3.
Während der Arbeit wird die Bewegung des Endlosbandes angezeigt. Das gerade aktive Register wird rot hervorgehoben.