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