In der theoretischen Informatik beschäftigt man sich u.a. mit dem Algorithmusbegriff und damit zwangsläufig der
Turingmaschine. So staubtrocken auch die Theorie sein mag, TP's erfordern gute Planungsarbeit, vergleichbar der Assemblerprogrammierung.
Mit dem Simulator ist es einfacher Fehler zu finden und das Testen von TP's durchzuführen.
Wer jetzt nicht weiß wer Turing war bzw. seine Maschine nicht kennt, der sollte die doc-Datei lesen oder sich folgende Links anschauen.
de.wikipedia.org/wiki/Alan_Turing
de.wikipedia.org/wiki/Turingmaschine
Aufbau eines TP's
Beispiel mit Alphabet A={B,I}, das TP P laute:
01#BBR#02
01#INR#00
02#BIR#03
02#IIR#02
03#BBL#04
03#IIR#03
04#BBN#00
04#IBL#05
05#BBN#00
05#IBL#06
06#BBN#00
06#IIL#06
Quelltext
1:
2:
3:
4:
5:
6:
7:
| Der Aufbau einer Programmzeile (z.B. 5 I B L 6):
Zustand Zeichen lesen Zeichen schreiben Verschieben Folgezustand
5 I B L 6
Allgemein leistet das Programm:
_ _
P(BI.......IBI.......IBB...)=BI.........IBB..
x+1-mal y+1-mal x+y+1-mal |
Aus diesem Grund heißt das Programm auch add.
Einige Programmzeilen sind überflüssig, bereinigt:
01#BBR#02
02#BIR#03
02#IIR#02
03#BBL#04
03#IIR#03
04#IBL#05
05#IBL#06
06#BBN#00
06#IIL#06
Mit Unterprogrammen sieht es so aus:
01#B(REB)I(REB)LBLB(LIB)#00
Das Band ist linksseitig begrenzt und nach rechts beliebig lang, in der Originalarbeit war das Band beidseitig beliebig lang.
Der L/S soll bei allen Programmen am Ende auf Position 0 stehen, wenn denn nichts anderes gefordert ist (z.B. Biberprobleme).
Wenn unter dem L/S (Lese-Schreibkopf)ein 'B' steht suche das nächste 'B' rechts, schreibe ein 'I', suche das nächste 'B' rechts, bewege L/S ein Feld nach links, schreibe ein 'B', bewege L/S ein Feld nach links, schreibe ein 'B', suche das nächste 'B' links und halte an.
Die mitgelieferten TP's sind durch Kommentare dokumentiert bezüglich Aufgabenstellung und Bandeingabe.
Fehleingaben sind bei allen TP's natürlich zu unterlassen, die Programme erwarten einen intelligenten User.
Die natürlichen Zahlen werden durch unäre Zahlen dargestellt.
Jede Zahl n wird durch n+1 'I' auf dem Band dargestellt. 0 - I, 3 - IIII usw.
Das Standardalphabet für die TM ist A={B,I}, das Alphabet kann je nach Problem erweitert werden.
z.B. A={B,I,0,1} für die Umwandlung von n in d(n), Umwandlung in Dualdarstellung.
An Unterprogrammen sind implementiert
ADD addiere zwei natürliche Zahlen
VZL verschiebe den ersten Symbolblock, der von B's eingerahmt ist, rechts an den L/S
DUP dupliziere eine Zahl
MUL multipliziere zwei Zahlen
LIB REB LII REI LI0 RE0 LI1 RE1 bewege L/S links (rechts)zum nächsten Zeichen(B,I,0,1)
DIF berechnet die Differenz(a-b) falls a>=b, andernfalls werden a und b gelöscht
DUN Dualnachfolger
DUV Dualvorgänger
DUA duale Addition
Die Unterprogrammen und die Schleifenlänge, die eine Todschleife repräsentiert (z.Zt. 100000000),
sind in Turing.ini festgelegt.
Zum Üben sollten die Unterprogramme selbst entwickelt werden, so bekommt man einen Eindruck wie die TM arbeitet.
Viel Spaß beim Experimentieren
Fiete
Edit1: kleine Änderungen und mehr Beispiele
