Aus ProgrammingWiki

UTM und Gödelisierung

Aufgabenstellung

Entwerfen Sie eine DTM C, die eine beliebige Zeichenkette , 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

Die zugrunde liegende Idee dieser Lösung ist folgende:

Als erstes wird eine Ziffer von dem Eingabeband gelesen. Ist die Ziffer eine 1 wird ein + auf das Band geschrieben, ist sie eine 0 so wird ein - geschrieben. Danach wird an das Ende des Wortes gelaufen und das erste $ übergangen. Nun wird die entsprechende Zahl auf das Band geschrieben. Also wenn zuerst eine 1 gelesen wurde, wird nun eine 1 geschrieben und ebenso für die 0. Danach wird zurück gegangen bis man auf ein + oder ein - stößt. Bei einem + schreibt man eine 1 und bei einem - eine 0. Anschließend geht man zur nächsten Ziffer und wiederholt den Vorgang.

Sobald kein Ziffer sondern das Vorbelegungszeichen gelesen wird, ist man am Ende des Eingabeworts angekommen und man kann zurück zum Anfang des Wortes gehen, so wie in der Aufgabenstellung gefordert. Dann crasht die TM.

Nachfolgend ist die Definition für eine entsprechende TM angegeben:

Übergangstabelle:

Übergangsgraph: