kurse:ef05a-2021:turingmaschinen:aufgaben

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:aufgaben [2021/08/19 07:20] – [Einstiegsaufgaben] Ivo Blöchligerkurse:ef05a-2021:turingmaschinen:aufgaben [2021/08/26 07:17] (current) – [Grundaufgaben] Ivo Blöchliger
Line 1: Line 1:
 +====== 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....
 +