BuK/IIm10/BuK-Übung07 G1

Wiki-Quelltext dieser Seite.

= Wort-spezifische TM =
== Aufgabenstellung ==
Geben Sie sich eine TM M  vor, die die Funktion <math>f: \mathbb{N}_0 \mapsto \mathbb{N}_0 </math> 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 ==