Entscheidbarkeit ::: Theoretische Informatik

Sei $L\subseteq\Sigma^{*}$ eine Sprache.

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.

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$ .

Charakteristische Funktion Entscheidbarkeit Zusammenhang zwischen Entscheidbarkeit und Semientscheidbarkeit

Ψ Die Informatikseite

Entscheidbarkeit

Semientscheidbarkeit

Entscheidbarkeit

Nicht entscheidbar Unentscheidbar

Nicht semientscheidbar

Nicht entscheidbar $\leftrightarrow$ Unentscheidbar