Die Mephistofolge ist eine rekursiv definierte Folge aus Binärziffern. Mephisto ist bekanntlich „der Geist, der stets verneint " 1 . Die ersten Folgenglieder der Mephistofolge sind \( 0,01,0110,01101001,0110100110010110, \ldots \)
Konstruieren Sie eine Turingmaschine für die Mephistofolge:
(a) Entwerfen Sie eine Turingmaschine mit dem Bandalphabet \( B=\{0,1, \#\} \), die aus einem gegebenen Folgenglied das nächste erzeugt.
(b) Entwerfen Sie eine Turingmaschine mit dem Bandalphabet \( B=\{\mid, 0,1 \), \# \( \} \), die zum Eingabewort \( n \) in unärer Darstellung das \( n \)-te Folgeglied der Mephistofolge berechnet. Die Anfangskonfiguration \#|||\# z.B. wird also in die Endkonfiguration \#0110\# überführt.
(c) Sei \( M \) die Mephistomenge, also die Menge, die aus allen Folgengliedern besteht. Ordnen Sie diese Menge in die Chomskyhierarchie ein und beweisen Sie dies.
