Wort-spezifische TM

Aufgabenstellung

Geben Sie sich eine TM M vor, die die Funktion f: \mathbb{N}_0 \mapsto \mathbb{N}_0 berechnet, d.h. die angesetzt auf ein Eingabewort w \in \mathbb{N}_0 das Resultat M(w) auf das Band schreibt und den Kopf auf das erste Zeichen von M(w) setzt.

Testen Sie diese Maschine ausgiebig. Verwenden Sie AutoEdit aus AtoCC.

Entwickeln Sie anschließend für ein konkretes Wort w \in \mathbb{N}_0 eine TM M_w aus M durch Modifikation der Definition von M per Hand. Wenn M_w auf dem (anfangs) leeren Band gestartet wird, soll M_w als erstes w auf das Band schreiben und sich anschließend verhalten, wie M(w), sodass M_w(\epsilon) = M(w).

Machen Sie sich klar, dass auf diese Weise jedem Wort w \in \mathbb{N}_0 je eine spezielle TM M_w zugeordnet werden kann.

Lösung

Wahrheitswertetafelmethode für aussagenlogische Äquivalenzen

Aufgabenstellung

Lösung

Reduktion

Aufgabenstellung

Lösung