Wort-spezifische TM

Aufgabe

Geben Sie sich eine TM M vor, die eine selbstgewählte Funktion f : \mathbb{N}_0 \rightarrow \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

Wahrheitstafelmethode für aussagenlogische Äquivalenzen

Aufgabe

Verwenden Sie die Wahrheitstafelmethode, um zu zeigen, dass aus

\hspace{5mm}Wenn P'\ entscheidbar und P \leq P', dann P\ entscheidbar.

folgt

\hspace{5mm}Wenn

und P \leq P', dann P'\ unentscheidbar.

Lösung

Die Aussagen werden zuerst Variablen zugeordnet. Diese können entweder wahr oder falsch sein.

In der folgenden Tabelle sind die Aussagen A, B, C, dargestellt. Die beiden markierten Spalten stehen für die beiden Sätze, welche durch die logische Aussagen entstehen. Man sieht, dass beide Spalten identisch sind, somit ist der Satz von der Aufgabe korrekt.

Reduktion