====== Universelle Turing Maschine ======
Man kann eine Turingmaschine bauen, der man die Spezifikation einer anderen Maschine und deren Input liefern kann. Die Universelle Turingmaschine simuliert dann die im Input gegebene Maschine.
===== Halbunendliches Band =====
Um die Sache ein bisschen zu vereinfachen, werden wir das Band der simulierten Maschine nur als halb-unendlich annehmen, d.h. das Band beginnt bei einer Zelle und läuft beliebig weit nach rechts.
Diese Einschränkung könnte leicht umgangen werden, indem das Band links mit Markern versehen wird. Soll über den linken Marker geschrieben werden, wird erst das ganze Band um ein Feld nach rechts kopiert (dafür wird der rechte Marker benötigt, dass man weiss, wie weit der Inhalt zu kopieren ist).
Oder man benutzt nur jedes zweite Feld (für positive Positionen) und klappt die negativen Position dazwischen, also 0,-1,1,-2,2,...
===== Codierung vom Input =====
Der Input der zu simulierenden Maschine wird nur in jede zweite Zelle geschrieben. Die Zellen dazwischen sind '.' (leer), ausser *vor* der Zelle, an der sich die zu simulierende TM gerade befindet, steht ein '!'. Z.B.
. 1 . 2 ! 3 . 4 . . . .
Entspricht dem Band '1234...' wenn der Lesekopf sich über der 3 befindet.
Damit muss die zu simulierende TM so codiert werden, dass diese kein '!' im Alphabet enthält. (Der Simulator kann Alphabete durch andere ersetzen).
===== Codierung der Zustände =====
==== Codierung für ein gelesenes Symbol eines Zustandes ====
Die Codierung, was in einem bestimmten Zustand zu ist, erfolgt so:
r w b $n$ .
wobei ''r'' das gelesene Symbol ist, ''w'' das zu schreibende Symbol, ''b'' die Bewegungsrichtung (R,L oder N) und $n$ eine Binärzahl im Big-Endian-Format, die der Nummer des nächsten Zustands enstpricht.
Fehlt $n$ heisst das ''stop''. Die Zustände sind von Null an nummeriert.
Beispiele:
1 1 R 1 1 0 .
read 1, write 1, go right, next state 6.
1 0 L .
read 1, write 0, go left, stop
==== Codierung eines ganzen Zustandes (mit allen Symbolen) ====
Ein Zustand beginnt mit den zwei Zeichen
> .
Danach folgen die Definitionen wie oben für jedes Symbol.
Der '.' nach dem '>' wird beim aktiven Zustand durch ein '!' ersetzt, um diesen zu markieren.
Beispiel:
>..1L1.11R0.
Wird übersetzt mit
zustand0
. 1 L zustand1
1 1 R zustand0
==== Codierung aller Zustände ====
Sämtliche Zustände werden mit ''>'' gefolgt von allen Zustandsdefinitionen codiert, z.B.
>>..1L1.11R0.>...R.11L1.
steht für folgendes Programm:
start
. 1 L fertig
1 1 R start
fertig
. . R stop
1 1 L fertig
==== Komplette Codierung ====
Das Band wird mit genügend Abstand rechts von den Zuständen eingefügt. Die komplette Codierung sieht dann wie folgt aus:
>>!.1L1.11R0.>...R.11L1.......!1.1.1.1.
wobei hier schon der aktuelle Zustand und die Position des Lesekopfes jeweils mit einen '!' markiert sind.
===== Übersicht vom Program =====
Voraussetzungen:
* Die aktuelle Position auf dem simulierten Band ist mit einem '!' markiert.
* Der Aktuelle Zustand ist unmittelbar nach dem '>' mit einem '!' markiert.
* Die Maschine befindet sich auf dem ersten '>' der kompletten Codierung.
==== Ausführungs-Schleife ====
- Symbol lesen
- Bis zum zweiten ''!'' nach rechts, dann rechts davon Symbol $s$ lesen.
- Zustandsdefinition für dieses Symbol finden.
- Zum ersten ''!'' zurück nach links, das ''!''löschen, dann zwei nach rechts.
- Symbol $s$ suchen:
- Wenn $s$ gefunden, weiter beim nächsten Schritt.
- Sonst 3 Schritte nach rechts
- Weiter nach rechts bis zum Punkt und einen Schritt weiter nach rechts.
- Wiederholen
- Wenn das Symbol $s$ gefunden ist, eins nach Links und den ''.'' durch ''!''ersetzen
- Symbol schreiben und Position anpassen
- Zwei nach links und das zu schreibende Symbol $w$ lesen.
- Eins nach links und die Richtung $r$ lesen.
- Rechts nach ''!'' suchen und durch ''.'' ersetzen.
- Ein Position rechts davon $w$ schreiben.
- Je nach $r$ eins nach rechts oder 3 nach links.
- ''!'' schreiben und zum ''!'' (Zustandsmarkierung) zurück.
- Die Binärzahl des nächsten Zustands an den Anfang (vor ''> >'') kopieren (im Little-Endian-Format)
- Wenn keine Binärzahl da, nach rechts zum ''!'' und rechts, stop.
- Die Binärzahl 4 Stellen rechts vom ''!'' Stelle um Stelle 0 durch L und 1 durch R ersetzen.
- Die ersetze Stelle links von ''> >'' anfügen.
- Wenn vollständig kopiert, die L/R wieder durch 0/1 ersetzen und das ''!'' löschen.
- Zurück zum ''> >'' und das ''!'' rechts davon setzen.
- Nächsten Zustand markieren.
- Zahl vor dem ''> >'' um eins vermindern. Wenn diese Zahl -1 ist: Zahl vor dem ''> >'' löschen und auf dem ersten '>' von vorne beginnen.
- Das ''!'' suchen und löschen
- Zum nächsten ''>'' vorrücken und das ''!'' rechts davon schreiben.
- Wiederholen
#Binary counter
#tape >>..1L1010.10R0.llR0.01L1010.ooR0.>...R101.11R1.llR1.00R1.ooR1.>!.1N1010.11R10.llR10.00R10.ooR10.>...L1010.11L11.llL11.00L11.ooL11.>..1L11.11R100.llR100.00R100.ooR100.>..0L11.11R101.llR101.00R101.ooR101.>...R0.11R110.llR110.00R110.ooR110.>...R100.11R111.llR111.00R111.ooR111.>...R110.11L1000.l1L1000.00L1000.o0L1000.>...L1000.1lR111.llR1001.0oR1.ooR1001.>...R1001.11L1010.llL1010.00L1010.ooL1010.......!..
#Unary times two
#tape >>...R110.11L1.>...R11.11L1.>...R100.11R10.>!..R11.1.R10.>..1R101.11R100.>..1L111.11R101.>...R.11R.>...L0.11L111.......!1.1.1.1.
#Unary plus one
#tape >>!.1L1.11R0.>...R.11L1.......!1.1.1.1.
symbolLesen R
! ! R @findRR(!;symbolMerken)
# Sucht das nächste Auftreten des Symbols
# ab der aktuellen Position und geht noch eine Position nach rechts
@findRR(1;1)
suchen R
@1 @1 R $1
@end
@findLN(1;1)
suchen L
@1 @1 N $1
@end
@findLR(1;1)
suchen L
@1 @1 R $1
@end
# Position auf zu lesendem Symbol auf simulierten Band
symbolMerken
* * L @zustandFinden(*;)
# Position auf !-Markierung auf simuliertem Band
@zustandFinden(1;0)
# auf der '!'-Markierung auf dem Band
onExBand L
* * L @findLN(!;onExZustand)
# auf der '!'-Markierung am Anfang des aktuellen Zustands
onExZustand
! . R sucheSymbol
# auf dem read-Symbol innerhalb ein Zustand/Symbol-Definition
sucheSymbol R naechsteDef
@1 @1 L markiereZustand
# Position auf write Symbol
naechsteDef R
* {R R} bisPunkt
bisPunkt R
. . R sucheSymbol
# Position vor dem Lese-Symbol, Markierung des Zustands
markiereZustand
. ! R symbolSchreiben
@end
# In der aktuellen Zustands/Symbol definition auf dem read-Symbol
symbolSchreiben
* * R symbolSchreiben1
# Auf dem Richtungssymbol
symbolSchreiben1
* * R @richtungLesen(*;)
@richtungLesen(1;0)
dummy
L L R @aufBandSchreiben(@1;links)
R R R @aufBandSchreiben(@1;rechts)
@end
@aufBandSchreiben(1;1)
suche
* * R @findRR(!;schreibe)
schreibe
* @1 L $1
@end
# Auf '!' im Band, durch . ersetzen und links oder rechts.
rechts
* {P. R R P! L} @findLR(!;binaryCopy)
links
* {P. L L P! L} @findLR(!;binaryCopy)
# Position rechts von der '!'-Zustandsmarkierung auf dem Lese-Symbol
binaryCopy
* {R R} binaryCopy2
# Position auf der ersten Binärziffer
binaryCopy2
# Maschine halt! (davon noch auf die Position auf dem Band gehen)
. . R @findRR(!;stop)
0 o L @writeBinary(0;)
1 l L @writeBinary(1;)
[ol] * R binaryCopy3
# Position auf n-ter Binärziffer
binaryCopy3
. . L binaryWiederherstellen
0 o L @writeBinary(0;)
1 l L @writeBinary(1;)
@writeBinary(1;0)
# '>' finden
findOne L
> > L findTwo
# das daneben auch '>'?
findTwo
* * L findOne
> > L findPos
findPos L
. @1 R @findRR(!;binaryCopy)
@end
binaryWiederherstellen L
# auf dem Richtungssymbol
* {L L L P.} preFinalCountDown1
l 1 L binaryWiederherstellen
o 0 L binaryWiederherstellen
# Doppeltes '>>' finden
preFinalCountDown1 L
> > L preFinalCountDown0
# Wenn doppeltes '>>' gefunden, ! danach platzieren.
preFinalCountDown0 L
* * L preFinalCountDown1
> {R R P!} finalCountDown
# rechts der '>>', doppeltes '>>' suchen
finalCountDown L
# '>>' suchen
> > L second
second
* * L finalCountDown
> > L preMinusEins
preMinusEins L
. . R minusEins
# Position auf irgend einer Ziffer vor '<<'
minusEins
# oops, das ist -1, also fertig
> > L preCounterLoeschen
# Eins subtrahieren, den !-Zustands-Marker schieben
1 0 R schieben
# Da gibt es einen Übertrag
0 1 R minusEins
# !-Markierung suchen und löschen
schieben R
! . R wo>
# Nächsten Zustand suchen, dahinter die Markierung setzen.
wo>
> > R setzen
setzen
. ! L finalCountDown
preCounterLoeschen L
. . R counterLoeschen
# Position vor der der -1 vor '<<', diese Löschen und von vorne beginnen.
counterLoeschen R
[01] . R counterLoeschen
> > R symbolLesen
===== Aufgaben =====
==== Zeichen lesen und finden ====
* Input:
#tape >123....2.1!2.3.2
* Die Maschine hält auf dem Zeichen im ersten String, das im zweiten String mit ! markiert ist. Die Maschine hält in diesem Fall auf der ersten 2, weil die 2 im zweiten String mit ! markiert ist.
#tape >12x3...2.1!x.2
finde! R
! ! R merke
merke
* * L @suche(*;)
@suche(1;0)
finde> L
> > R findeSymbol
findeSymbol R
@1 @1 N stop
@end
==== Marker schieben ====
* Input
#tape 011>!....
* Output
...>......!
Die Maschine verschiebt das '!' um so viele Positionen nach rechts, wie die in Little-Endian codierte Binärzahl vor dem '>' angibt. Die Zahl davor soll gelöscht werden.!
#tape 011>!..
minusEins
0 1 R minusEins
1 0 R schieben
> > L loeschen
schieben R
! . R schreiben
schreiben L
. ! L back
back L
> > L back2
back2 L
. . R minusEins
loeschen L
[01] . L loeschen
. . R fertig
fertig R
> > N stop