wilhelm büchner_728x90_bachelor_informatik
 

next up previous contents
Nächste Seite: Zusammenhang zwischen Entscheidbarkeit und Aufwärts: Entscheidbarkeit Vorherige Seite: Charakteristische Funktion   Inhalt

Unterabschnitte

Entscheidbarkeit

Semientscheidbarkeit

Sei $L\subseteq\Sigma^{*}$ eine Sprache. $L$ ist semientscheidbar, wenn es eine DTM $\tau$ gibt, für die gilt

\begin{displaymath}L(\tau)=L\end{displaymath}

d.h. Für alle Worte der Sprache L akzeptiert die DTM $\tau$. Wenn die partielle charakteristische Funktion turingberechenbar ist, ist die Sprache semientscheidbar.

Entscheidbarkeit

Sei $L\subseteq\Sigma^{*}$ eine Sprache. $L$ ist entscheidbar, wenn es eine DTM $\tau$ gibt, für die gilt

\begin{displaymath}L(\tau)=L\end{displaymath}

und für alle Worte $w\not\in L$ verwirft die DTM $\tau$. Wenn die totale charakteristische Funktion turingberechenbar ist, ist die Sprache entscheidbar.

Nicht entscheidbar $\leftrightarrow$ Unentscheidbar

Die Sprache $L\subseteq\Sigma^{*}$ wird unentscheidbar genannt, wenn sie nicht entscheidbar ist, d.h. es gibt keine DTM $\tau$, die für alle $w\in L$ akzeptiert und für alle $w\not\in L$ verwirft.

Nicht semientscheidbar

Eine Sprache $L\subseteq\Sigma^{*}$ wird nicht semientscheidbar genannt, wenn es keine DTM gibt, für die gilt $L(\tau)=L$.