Aufgaben zu Turing-Maschinen

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

Lösungsvorschlag

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

Lösungsvorschlag

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

Lösungsvorschlag

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

Lösungsvorschlag

 
# 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

Lösungsvorschlag

#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!)

Lösungsvorschläge

bin2dec.txt

#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

dec2bin.txt

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

Lösungsvorschlag

# 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….

Table of Contents

Aufgaben zu Turing-Maschinen

Einstiegsaufgaben

Grundaufgaben

Tricky