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 ∈ 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¨ur ein konkretes Wort w ∈ 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 ver- halten, wie M(w), sodass M w (ε) = M(w). Machen Sie sich klar, dass auf diese Weise jedem Wort w ∈ 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