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
.