kurse:ef05a-2021:turingmaschinen:universelle_turing_maschine [https://fginfo.ksbg.ch Fachgruppe Informatik der KSBG]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== 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


<hidden Lösungsvorschlag>
<code txt 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 


</code>
</hidden>

===== Aufgaben =====
==== Zeichen lesen und finden ====
  * Input:
<code txt>
#tape >123....2.1!2.3.2
</code>   
  * 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. 


<hidden Lösungsvorschlag>
<code txt>
#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

</code>
</hidden>
==== Marker schieben ====
  * Input
<code txt>
#tape 011>!....
</code>
  * Output
<code txt> 
...>......!
</code>
 
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.!

<hidden Lösungsvorschlag>
<code txt>
#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

</code>
</hidden>