Unentscheidbare Sprachen

Für eine unentscheidbare Sprache gibt es keine Turing-Maschine, die die Sprache akzeptiert und für jede Eingabezeichenfolge eine Entscheidung trifft w(TM kann jedoch eine Entscheidung für eine Eingabezeichenfolge treffen). Ein EntscheidungsproblemP wird als "unentscheidbar" bezeichnet, wenn die Sprache L aller ja Instanzen zu Pist nicht entscheidbar. Unentscheidbare Sprachen sind keine rekursiven Sprachen, aber manchmal können sie rekursiv aufzählbare Sprachen sein.

Beispiel

Das Halteproblem der Turingmaschine
Das Sterblichkeitsproblem
Das Problem der sterblichen Matrix
Das Post-Korrespondenzproblem usw.