Unterabschnitte
Sei

eine Sprache.

ist semientscheidbar, wenn es eine DTM

gibt, für die gilt
d.h. Für alle Worte der Sprache L akzeptiert die DTM

.
Wenn die partielle charakteristische Funktion turingberechenbar ist, ist die Sprache semientscheidbar.
Sei

eine Sprache.

ist entscheidbar, wenn es eine DTM

gibt, für die gilt
und für alle Worte

verwirft die DTM

.
Wenn die totale charakteristische Funktion turingberechenbar ist, ist die Sprache entscheidbar.
Die Sprache

wird unentscheidbar genannt, wenn sie nicht entscheidbar ist, d.h. es gibt keine DTM

, die für alle

akzeptiert und für alle

verwirft.
Eine Sprache

wird nicht semientscheidbar genannt, wenn es keine DTM gibt, für die gilt

.