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….
- Addition von 1 zu einer Binärzahl im Little-Endian Format.
Grundaufgaben
- Verdoppelung einer unären Zahl (dafür sind zusätzliche Symbole nützlich aber nicht unbedingt notwendig).
- Verdoppelung einer binären Zahl
- Eine Maschine, die auf leerem Band folgende Sequenz erzeugt: 1.11.111.1111.11111. etc.
- 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
- Umwandlung einer Unärzahl in eine Binärzahl oder umgekehrt.
- Umwandlung eine Binärzahl in eine Dezimalzahl oder umgekehrt (es darf ineffzient sein!)
- 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).
- 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….