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,…
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
- universelle-turing-maschine.txt
#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
#tape >123....2.1!2.3.2
#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
#tape 011>!....
...>......!
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