BuK/IIm10/BuK-Übung07 G2

Wiki-Quelltext dieser Seite.

= Wort-spezifische TM =
==Aufgabe==
Geben Sie sich eine TM <math>M</math> vor, die eine selbstgewählte Funktion <math>f : \mathbb{N}_0 \rightarrow \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)</math> = <math>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==
Wir wählen eine Funktion f, die prüft, ob das übergebene Element ein Palindrom ist oder nicht. Dabei legen wir fest, dass die Elemente des Definitionsbereiches im Dualsystem bereitgestellt werden.
[[Datei:TM_1.png|thumb|right|Übergangsgraph der TM (Teil 1)]]
<math>
f(n_{(2)})=\begin{cases}
1, &\text{wenn }n_{(2)} \text{ ist ein Palindrom};\\
0, &\text{sonst}
\end{cases}
</math>

Wir haben für diesen ersten Teil der Aufgabe eine Turingmaschine entworfen, die immer in einem Endzustand stoppt. Der Kopf der Maschine steht dann über dem zuvor geschriebenen Zeichen, dem Funtktionswert (0 oder 1).

[[Datei:Sistlehm_101.PNG|gerahmt|ohne|Konfigurationenfolge für Eingabe 101]]
[[Datei:Sistlehm_100.PNG|gerahmt|ohne|Konfigurationenfolge für Eingabe 100]]

Für den zweiten Teil haben wir als konkretes Wort "1001" festgelegt. Wir haben eine Turingmaschine erzeugt, die die Zeichen auf das Band schreibt und anschließend den Kopf vor das erste Zeichen bewegt.
[[Datei:Sistlehm_Wortspezifische_TM_part2.png|thumb|right|Übergangsgraph der TM (Teil 2)]]
[[Datei:Sistlehm_1001.PNG|gerahmt|ohne|Konfigurationenfolge für Eingabe 1001]]

Im letzten Schritt werden die beiden Turingmaschinen miteinander verbunden, sodass eine einzelne Maschine entsteht, die das leere Wort als Eingabe nimmt und sich verhält wie die Maschine aus Teil 1 mit Eingabe von "1001".
[[Datei:Sistlehm_TM_gesamt.png|thumb|right|Übergangsgraph der TM (Teil 1 und 2)]]
[[Datei:Sistlehm_Epsilon.PNG|gerahmt|ohne|Konfigurationenfolge für Eingabe <math>\epsilon</math>]]

= Wahrheitstafelmethode für aussagenlogische Äquivalenzen =

== Aufgabe ==
Verwenden Sie die Wahrheitstafelmethode, um zu zeigen, dass aus

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

folgt

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

== Lösung ==

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

<math>A...P'\ entscheidbar</math>

<math>B...P\leq P'</math>

<math>C...P\ entscheidbar</math>

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.

[[Bild:Simaklem2_Wahrheitstabelle.PNG]]

= Reduktion =