0 Daumen
61 Aufrufe

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.

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community