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.

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).

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

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

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

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.

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.

Symbol lesen
1. Bis zum zweiten ! nach rechts, dann rechts davon Symbol $s$ lesen.
Zustandsdefinition für dieses Symbol finden.
1. Zum ersten ! zurück nach links, das !löschen, dann zwei nach rechts.
2. Symbol $s$ suchen:
  1. Wenn $s$ gefunden, weiter beim nächsten Schritt.
  2. Sonst 3 Schritte nach rechts
  3. Weiter nach rechts bis zum Punkt und einen Schritt weiter nach rechts.
  4. Wiederholen
3. Wenn das Symbol $s$ gefunden ist, eins nach Links und den . durch !ersetzen
Symbol schreiben und Position anpassen
1. Zwei nach links und das zu schreibende Symbol $w$ lesen.
2. Eins nach links und die Richtung $r$ lesen.
3. Rechts nach ! suchen und durch . ersetzen.
4. Ein Position rechts davon $w$ schreiben.
5. Je nach $r$ eins nach rechts oder 3 nach links.
6. ! schreiben und zum ! (Zustandsmarkierung) zurück.
Die Binärzahl des nächsten Zustands an den Anfang (vor > >) kopieren (im Little-Endian-Format)
1. Wenn keine Binärzahl da, nach rechts zum ! und rechts, stop.
2. Die Binärzahl 4 Stellen rechts vom ! Stelle um Stelle 0 durch L und 1 durch R ersetzen.
3. Die ersetze Stelle links von > > anfügen.
4. Wenn vollständig kopiert, die L/R wieder durch 0/1 ersetzen und das ! löschen.
5. Zurück zum > > und das ! rechts davon setzen.
Nächsten Zustand markieren.
1. Zahl vor dem > > um eins vermindern. Wenn diese Zahl -1 ist: Zahl vor dem > > löschen und auf dem ersten '>' von vorne beginnen.
2. Das ! suchen und löschen
3. Zum nächsten > vorrücken und das ! rechts davon schreiben.
4. Wiederholen

Lösungsvorschlag

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

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.

Lösungsvorschlag

#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

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.!

Lösungsvorschlag

#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