Das Halteproblem

Gibt es einen Algorithmus, der für beliebige Programme P und Eingaben y entscheiden kann, ob P bei Eingabe y anhält oder nicht?

Name: K

Der zu prüfende Algorithmus muss als Gödelnummer angegeben werden.

Das Spezielle Halteproblem #

Name: K0

Eingabe: x ∈ IN.


Frage: Hält M_x bei Eingabe x an?

Eingabe: x, y ∈ IN.


Frage: Hält M_x bei Eingabe y an?

K = {(x, y) ∈ IN 2 | M_x (y)↓} ⊆ IN^2

K0 = {x ∈ IN | M_x (x)↓} ⊆ IN

K 0 ist aufzählbar, aber nicht entscheidbar.

Das Komplement von K0 ist nicht aufzählbar

Folgerung: RE ist unter Komplement nicht abgeschlossen

K ist aufzählbar, aber nicht entscheidbar

Many-one-Reduzierbarkeit

Eine Möglichkeit, Mengen bzgl. ihrer algorithmischen Beherrschbarkeit zu vergleichen

K ist algorithmisch nicht ‘leichter’ als K 0 , denn mit Hilfe eines Entscheidungsalgorithmus für K könnte man erst recht K 0 entscheiden. Damit steckt in K eine algorithmische Komplexität, die mindestens so groß ist, wie zur Entscheidung von K 0 benötigt. # #

x ∈ A <=> f(x) ∈ B

reflexiv und transitiv

Quasiordnung

Es muss kein Algorithmus für die Berechnung der charakteristischen Funkton von B bekannt sein um A auf B zu reduzieren

Many-one-Äquivalenz

K und K0 sind many-one-äquivalent #

Alle nichttrivialen entscheidbaren Mengen sind mann-one-äquivalent

K ist RE-vollständig