kurse:ef05a-2021:turingmaschinen:universelle_turing_maschine

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision		 Previous revision
kurse:ef05a-2021:turingmaschinen:universelle_turing_maschine [2021/09/02 06:31] – [Zeichen lesen und finden] Ivo Blöchligerkurse:ef05a-2021:turingmaschinen:universelle_turing_maschine [2021/09/09 07:14] (current) – Ivo Blöchliger
Line 1: Line 1:
 +====== 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>