UTM und Gödelisierung

Aufgabenstellung

Entwerfen Sie eine DTM C, die eine beliebige Zeichenkette w, w \in {0, 1}^+ , als Bandinschrift erwartet und diese kopiert, so dass C mit wBw auf dem Band stoppt und der Kopf auf dem ersten Zeichen von wBw steht. B ist das Vorbelegungszeichen von C. Es dient zur Trennung zwischen den beiden Wörtern w.

Verwenden Sie AutoEdit aus AtoCC.

Lösung

Eine Turing-Maschine, die die Aufgabenstellung löst, ist wie folgt definiert:

Übergangstabelle:

Übergangsgraph: