====== Aufgaben zu Turing-Maschinen ======
Es gibt viele Varianten, diese Aufgaben zu lösen. Vergleichen Sie die Lösungen auch nach verschiedenen Kriterien wie
* Benötigte Laufzeit (auch in Abhängigkeit des Inputs)
* Lesbarkeit für den Menschen
* Kompaktheit (Anzahl Zustände oder verwendete Symbole)
* Eleganz und Raffiniertheit
Als Konvention soll die Maschine immer auf dem ersten (d.h. am meisten links stehendes) Zeichen stoppen.
===== Einstiegsaufgaben =====
* Addition von zwei unären Zahlen, z.B. 111.1111....
# Addiert zwei Zahlen im unären Format,
# durch *einen* Punkt getrennt.
# Idee: Erste 1 durch Punkt ersetzen
# Trennzeichen durch 1 ersetzen
# Zurück an den Anfang, stop
#tape 111.1111...
start
1 . R trennzeichen
# Hier muss eine Leerzeile zwischen den
# Zuständen stehen!
trennzeichen
. 1 L retour
retour L
. . R stop
* Addition von 1 zu einer Binärzahl im Little-Endian Format.
# Input der Binärzahl im Little-Endian Format
# d.h. Einerstelle zuerst.
# Steht eine Null (oder .), wird diese durch eine 1 ersetzt und man ist fertig (zurück an den Anfang)
# Steht eine Eins, wird diese durch eine Null erstetzt und die nächste Stelle muss erhöht werden.
#tape 1111
start
1 0 R start
[0.] 1 L fertig # [0.1] steht für Null oder Punkt. Könnte man auch in zwei Zeilen schreiben.
fertig L # Wenn nicht anders vermerkt, lasse das Zeichen wie es ist und gehe nach links.
. . R stop
===== Grundaufgaben =====
* Verdoppelung einer unären Zahl (dafür sind zusätzliche Symbole nützlich aber nicht unbedingt notwendig).
#tape 1111
#Idee: Immer eine Ziffer abbauen, und zwei aufbauen
#(die beiden Zahlen werden durch einen . getrennt.
# erste 1 löschen, dann Ende suchen
start
1 . R findDot
# Ende der Eingabe
findDot
. . R write1
# Ende des Resultats suchen und 2 Einsen schreiben, könnte auch mit {P1 R P1 L} abgekürzt werden.
write1
. 1 R write2
# Zweites 1 schreiben und zurück
write2
. 1 L backDot
# Trennzeichen gefunden
backDot L
. . L backOne
# Sind noch Einsen übrig, wenn nein sind wir fertig
backOne L
1 1 L backDot2
. { R R} stop
# Auf erste verbleibende Eins und von vorne beginnen
backDot2 L
. . R start
* Verdoppelung einer binären Zahl :-)
* Eine Maschine, die auf leerem Band folgende Sequenz erzeugt: 1.11.111.1111.11111. etc.
# adds 1 to the last number
start R
. 1 N dup
# duplicate the last number, replace 1 by x temporarily
dup L
. . R done
1 x R add
# forward to the next dot
add R
. . R add1
#forward to the next dot, add 1
add1
. 1 L back
# back to the previous dot
back L
. . L dup
# all copied, replace x by 1 again
done
x 1 R done
. . R start
* Eine Maschine, die die aufsteigenden Binärzahlen durch . getrennt aufschreibt.
* Hinweis: Eine Möglichkeit besteht darin, die Zahl erst zu kopieren (und die 0/1 temporär durch z.B. O/L zu ersetzen). Danach erhöht man die zweite Zahl um 1 und ersetzt in der ersten wieder O/L durch 0/1.
* Multiplikation zweier unären Zahlen
#tape 111.111
#Idee: Erste Zahl abbauen, für jedes Symbol, die zweite Zahl dem dritten Resultat anhängen.
# Start auf der ersten Eins, durch Punkt ersetzen
start
1 . R dot1
# Trennzeichen suchen, mit Addition der zweiten zur dritten Zahl beginnen
dot1
. . R add
# Vorderste Eins der zweiten Zahl mit x ersetzen
add
1 x R dot2
# Trennzeichen zwischen 2. und 3. Zahl suchen
dot2
. . R add2
# Eine Eins hinten an die dritte hängen, zurück zum x
add2
. 1 L backX
# x gefunden, gibt es noch Einsen?
backX L
x x R schonAddiert
# Ein Punkt? Wir haben fertig addiert, Zahl wiederherstellen,
# Sonst ein weiterer Additionsschritt ausführen.
schonAddiert
. . L restore
1 x R dot2
# Zweite Zahl wieder herstellen, dann zur ersten nach links gehen
restore
x 1 L restore
. . L backA
# Nur noch Punkte da? Dann ist die erste Zahl vollständig abgebaut, also fertig
# Sonst gehen wir an den Anfang der ersten Zahl
backA L
. {R R} fertig
1 1 L backA2
# Wir sind am Anfang der ersten Zahl, es hat noch Einsen, als von vorne beginnen
backA2 L
. . R start
# Die erste Zahl ist aufgebraucht, Maschine am Anfang der zweiten, also zum
# Punkt vorrücken und dann auf dem Anfang der dritten Zahl stoppen.
fertig R
. . R stop
* Umwandlung einer Unärzahl in eine Binärzahl oder umgekehrt.
* Umwandlung eine Binärzahl in eine Dezimalzahl oder umgekehrt (es darf ineffzient sein!)
#tape 101010
#Eingabe big-endian, ausgabe big-endian
start
* {L L P0 R R} gor
gor R
. . L sub
sub
1 0 L gol
0 1 L sub
. . L stop
gol L
. . L add
add
0 1 R back
1 2 R back
2 3 R back
3 4 R back
4 5 R back
5 6 R back
6 7 R back
7 8 R back
8 9 R back
9 0 L add
. 1 R back
back R
. . R gor
#tape 42
# Die Eingabe wird zerstört, die Ausgabe ist little-endian
start R
. . L sub
sub
9 8 R add
8 7 R add
7 6 R add
6 5 R add
5 4 R add
4 3 R add
3 2 R add
2 1 R add
1 0 R add
0 9 L sub
. . R finish
add R
. . R add1
add1
0 1 L back
1 0 R add1
. 1 L back
back L
. . L sub
finish R
9 . R finish
. . R stop
* Binäre Addition
* Erzeugung der Fibbonacci-Zahlen in unär.
* Gegeben ist eine Folge von 1/0. Diese soll von hinten nach vorne geschrieben werden.
* Gegeben ist eine Folge von 1/0. Es soll bestimmt werden, wie viele 1 und 0 darin vorkommen (binär oder unär).
===== Tricky =====
* Binäre Multiplikation
* Erzeugung der Folge der Fibbonacci-Zahlen (in binär).
# Start with 1.0
#tape 1.0
start
* * R rechtsnull15
# Suche ersten . nach rechts und überprüfe, ob es noch etwas zu tun gibt
rechtsnull1 R
. . R rechtsnull15
rechtsnull15 R
[01] * R rechtsnull15OK
. . R rechtsnull2
rechtsnull15OK R
. . R rechtsnull2OK
rechtsnull2 R
[01] * R rechtsnull2OK
. . L finish
rechtsnull2OK R
. . L @addieren1(;null)
rechtseins1 R
. . R rechtseins15
rechtseins15
. . R rechtseins2
rechtseins2 R
. . L @addieren1(;eins)
# Zustandsargument ist null oder eins (je nach Behalte)
@addieren1(0;1)
# Go left until the first digit. If there is a . the number is already finished.
start L
[01.] * N $1
null
0 o L @addieren2(;null2)
. . N @addieren2(;null2)
1 l L @addieren2(;eins2)
eins
0 o L @addieren2(;eins2)
. . N @addieren2(;eins2)
1 l L @addieren2(;zwei2)
@end
@addieren2(0;1)
punkt L
. . L start
start L
[01.] * N $1
null2
0 o L @result(;null3)
. . N @result(;null3)
1 l L @result(;eins3)
eins2
0 o L @result(;eins3)
. . N @result(;eins3)
1 l L @result(;zwei3)
zwei2
0 o L @result(;zwei3)
. . N @result(;zwei3)
1 l L @result(;drei3)
@end
@result(0;1)
dot1 L
. . L dot2
dot2 L
. . N $1
null3
. 0 R rechtsnull1
eins3
. 1 R rechtsnull1
zwei3
. 0 R rechtseins1
drei3
. 1 R rechtseins1
@end
finish L
l 1 L finish
o 0 L finish
. . L finish1
finish1 L finish1
l 1 L finish1
o 0 L finish1
. . L finish2
finish2 L finish2
. . R start
* Binäre Division
* Input sind zwei Folgen von 0/1, getrennt durch einem '.'. Die Maschine soll auf dem ersten Vorkommen der ersten Folge in der zweiten Folge stoppen (oder am Anfang der ersten Folge, wenn diese nicht in der zweiten vorkommt).
* Berechung der Folge 1!, 2!, 3!, etc.
* Sortierung einer Liste von 4-Bit Binärzahlen, z.B. 0110.1010.0010.0001.1111.0000.1100....