wilhelm büchner_728x90_bachelor_informatik
  Home     
    
    Bücher   Links   Impressum

next up previous contents
Nächste Seite: Rekursive Aufzählbarkeit Aufwärts: Entscheidbarkeit Vorherige Seite: Entscheidbarkeit   Inhalt

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.
next up previous contents
Nächste Seite: Rekursive Aufzählbarkeit Aufwärts: Entscheidbarkeit Vorherige Seite: Entscheidbarkeit   Inhalt