Ψ Die Informatikseite

Menü
Informatik » Bachelor » Theoretische Informatik » Entscheidbarkeit » Zusammenhang zwischen Entscheidbarkeit und Semientscheidbarkeit
Entscheidbarkeit Entscheidbarkeit Rekursive Aufzählbarkeit
Unterabschnitte

Zusammenhang zwischen Entscheidbarkeit und Semientscheidbarkeit

$L$ entscheidbar, dann auch $\overline{L}$ entscheidbar

$L$ entscheidbar, dann auch $\overline{L}$ entscheidbar.
Wir benutzen eine DTM $\tau'$, die die DTM $\tau$ simuliert. Diese vertauscht die beiden Ausgaben ,,JA'' und ,,NEIN''.
O.b.d.A. können wir annehmen, daß für alle $q\in F$ (für die DTM $\tau$) gilt $\delta(q,a)=\bot$
Wir definieren nun die partielle Übergangsfunktion von $\tau'$ folgendermaßen:

\begin{displaymath}\delta'(q,a)=\left\{\begin{array}{ll} \delta(q,a)&falls\,\del... ...\,(akzeptieren,\, wenn\, \tau\, verwirft)\\ \end{array}\right.\end{displaymath}

Die Endzustandsmenge von $\tau'$ ist $F'=\{q'\}$.

$L$ und $\overline{L}$ semientscheidbar $\Leftrightarrow$ $L$ entscheidbar

Es genügt die Implikation ,,$\Rightarrow$'' zu zeigen:
Wir nehmen die beiden Turingmaschinen, die $L$ und $\overline{L}$ semientscheiden und schalten beide parallel. Eine der beiden Maschinen wird akzeptieren. Akzeptiert $\tau_{L}$ so geben wir ,,JA'' aus. Akzeptiert $\tau_{\overline{L}}$ so geben wir ,,NEIN'' aus.
Wir können die beiden Turingmaschinen parallel schalten, indem wir eine Zweibandturingmaschine verwenden, wobei jede Turingmaschine ein Band besitzt und die Zustandsmenge11 immer hin und her schaltet.

Fußnoten

... Zustandsmenge11
Anmerkung: Die Menge der Zustände der simulierenden Gesamt-DTM beträgt: $n\ast m$, wobei n die Menge der Zustände der ersten DTM ist und m die Menge der Zustände der zweiten DTM.
Entscheidbarkeit Entscheidbarkeit Rekursive Aufzählbarkeit