kurse:ef05a-2021:turingmaschinen:aufgaben [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.
====== 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....
<hidden Lösungsvorschlag>
<code txt>
# 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
</code>
</hidden>
  * Addition von 1 zu einer Binärzahl im Little-Endian Format.
<hidden Lösungsvorschlag>
<code txt>
# 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
</code>
</hidden>  
===== Grundaufgaben =====
  * Verdoppelung einer unären Zahl (dafür sind zusätzliche Symbole nützlich aber nicht unbedingt notwendig).
<hidden Lösungsvorschlag>
<code txt>
#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

</code>
</hidden>
    * Verdoppelung einer binären Zahl :-)
  * Eine Maschine, die auf leerem Band folgende Sequenz erzeugt: 1.11.111.1111.11111. etc.
<hidden Lösungsvorschlag>
<code txt>


# 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

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

</code>
</hidden>
  * Umwandlung einer Unärzahl in eine Binärzahl oder umgekehrt.
  * Umwandlung eine Binärzahl in eine Dezimalzahl oder umgekehrt (es darf ineffzient sein!)
<hidden Lösungsvorschläge>
<code txt 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

</code>
<code txt 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

</code>
</hidden>
  * 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).
<hidden Lösungsvorschlag>
<code txt>
# 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

</code>
</hidden>
  * 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....