Please enable JavaScript.
Coggle requires JavaScript to display documents.
Das Halteproblem (Many-one-Reduzierbarkeit (Many-one-Äquivalenz (K und K0…
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?
Eingabe: x, y ∈ IN.
Frage: Hält M_x bei Eingabe y an?
K = {(x, y) ∈ IN 2 | M_x (y)↓} ⊆ IN^2
-
-
Das Spezielle Halteproblem #
-
-
-
K 0 ist aufzählbar, aber nicht entscheidbar.
-
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
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 #
-
-