Übung 12

24. Januar 2002 (Abgabe 4. Februar 2002)

Benutzen Sie das Haskell Programm turing_muster.hs zum Lösen der folgenden Aufgaben.

Aufgabe 1 (6 Punkte)

Implementieren Sie die Funktion show_states, die die Zustände der Maschine und den jeweiligen Inhalt des Bandes (1. Zeile), sowie die Bandposition (2. Zeile) unter dem Band anzeigt.

Zum Beispiel:

Main> start (2,"A",'(',")A") klammer
  2  A()A
      T
  2  A()A
       T
  1  A(XA
      T
  2  AXXA
       T
  2  AXXA
        T
  3  AXXA
       T
  3  AXXA
      T
  3  AXXA
     T
  0  1XXA
     T

Aufgabe 2 (7 Punkte)

Implementieren Sie die Universelle Turing-Maschine als Programm (Zustandsübergangstabelle) für die Turing-Maschine.

Aufgabe 3 (7 Punkte)

Schreiben Sie ein Programm (Symbole auf einem Band) für die Universelle Turing-Maschine, das die Parität einer gegebenen Eingabe berechnet.