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.