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 <math>w \in \mathbb{N}_0</math> das Resultat <math>M(w</math>) auf das Band schreibt und den Kopf auf das erste Zeichen von <math>M(w)</math> setzt.

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

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

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

== Lösung ==

= Wahrheitswertetafelmethode für aussagenlogische Äquivalenzen =
== Aufgabenstellung ==
Verwenden Sie die Wahrheitswertetafelmethode, um zu zeigen, dass aus

<math>Wenn\text{ }P'\text{ }entscheidbar\text{ }und\text{ }P \leq P',\text{ }dann\text{ }P\text{ }entscheidbar.
</math>

folgt

<math>Wenn\text{ }P\text{ }unentscheidbar\text{ }und\text{ }P \leq P',\text{ }dann\text{ }P'\text{ }unentscheidbar.</math>

== Lösung ==

= Reduktion =
== Aufgabenstellung ==
== Lösung ==