petrov Gast
|
Verfasst am: 09. Dez 2005 13:29 Titel: Aufgabe! HILFEEEE |
|
|
Hallo!
ich habe ein riesen grosses Problem mit einer der Theoretische Informatik Aufgaben. Ich habe keine Ahnung was ich machen soll. Bitte um Hilfe! Hier ist die Aufgabe :
Beweisen Sie die folgende Aussage:
Zu jeder Turing-Maschine M = (X;Z; z0; Q; beta) gibt es eine Turing-Maschine
M0 = (X und {#,§};Z0; z00; Q0; beta0)
mit {#,§} in X und
fM0(w) = fM(w) für w in X¤ und fM(w) ist definiert
nicht definiert sonst
derart, dass jede Endkonfiguration von M0 die Form (¸; q0; v) mit v = fM(w)
hat (d. h. die Maschine M0 hat genau einen Stoppzustand, stoppt nur auf
W¨ortern ¨uber X und stoppt stets ¨uber dem ersten Buchstaben des Ergebnisses
v). |
|