{-
Berechenbarkeit und Komplexitaet                            SS03 bei Dr. Tompitz
autotool-Aufgabe TM-EXPO                                  Arne Brutschy, 8964813

Idee:   die Maschine schreibt eine Zwei links neben das Eingabewort, fuer
        jede Eins werden die Zweier verdoppelt und jeweils eine Eins mit Null
        ueberschrieben. Am Ende werden alle Nullen geloescht, alle Zweien auf
        Eins umgeschrieben.
Bsp:         11
            211
            201
           3301
           2201
           2300
          32300
         333300
         222200
         1111##
-}
import Turing
student :: Turing Char Integer
student = Turing {eingabealphabet = mkSet "1",
        arbeitsalphabet = mkSet "#0123",
        leerzeichen = '#',
        zustandsmenge = mkSet [1, 2, 3, 5, 6, 7, 8],
        tafel = listToFM [-- Zustand 1: ersetze erste Eins durch Zwei
                          --            ausser bei leerem Band
                          (('#', 1), mkSet [('2', 2, R)]),
                          (('0', 1), mkSet [('0', 5, L)]),
                          (('1', 1), mkSet [('1', 1, L)]),
                          (('2', 1), mkSet [('2', 2, O)]),
                          (('3', 1), mkSet [('3', 1, R)]),
                          -- Zustand 2: laufe nach Links zur ersten
                          --            Zwei, ersetze durch Drei
                          (('#', 2), mkSet [('#', 7, L)]),
                          (('0', 2), mkSet [('0', 2, L)]),
                          (('1', 2), mkSet [('0', 2, L)]),
                          (('2', 2), mkSet [('3', 3, L)]),
                          -- Zustand 3: gehe nach ganz Links und
                          --            haenge Vier an
                          (('#', 3), mkSet [('3', 1, R)]),
                          (('0', 3), mkSet [('0', 3, L)]),
                          (('2', 3), mkSet [('2', 3, L)]),
                          (('3', 3), mkSet [('3', 3, L)]),
                          -- Zustand 5: gehe ganz nach Rechts und
                          --            schreibe alles auf Zwei um
                          (('#', 5), mkSet [('#', 5, R)]),
                          (('0', 5), mkSet [('0', 6, R)]),
                          (('2', 5), mkSet [('2', 5, R)]),
                          (('3', 5), mkSet [('2', 5, L)]),
                          -- Zustand 6: mal sehen ob noch wir nochmal
                          --            verdoppeln muessen
                          (('#', 6), mkSet [('#', 7, L)]),
                          (('0', 6), mkSet [('0', 6, R)]),
                          (('1', 6), mkSet [('1', 2, O)]),
                          (('2', 6), mkSet [('1', 6, L)]),
                          -- Zustand 7: ersetze alle Zweier durch
                          --            Einser und loesche Nullen
                          (('#', 7), mkSet [('#', 8, O)]),
                          (('0', 7), mkSet [('#', 7, L)]),
                          (('2', 7), mkSet [('1', 7, L)])],
        startzustand = 1,
        endzustandsmenge = mkSet [8]}