Please enable JavaScript.
Coggle requires JavaScript to display documents.
Unentscheidbare Mengen (Indexmenge (Indexmengen enthalten für eine…
Unentscheidbare Mengen
TOTAL
Eingabe: i ∈ IN.
Frage: Ist phi_i total, d.h. gilt Dphi_i = IN?
-
-
Indexmenge
Eine Menge A ⊆ IN heisst Indexmenge, falls für alle i, j ∈ IN gilt:
Ist i ∈ A und ϕ i = ϕ j , so ist j ∈ A.
Indexmengen enthalten für eine berechenbare Funktion alle (Nummern von) Algorithmen, die ebenfalls diese Funktion berechnen.
-
-
-
-
Jede nichttriviale Indexmenge, die den Index der nirgends definierten Funktion enthält, ist nicht aufzählbar.
Satz von Rice:
Sei C 6= ∅ eine echte Teilmenge aller berechenbaren Funktionen. Dann ist die zugehörige Indexmenge
I(C) = def {i ∈ IN | ϕ i ∈ C}
unentscheidbar.
Korrektheitsproblem
-
Berechnet ein vorgegebenes Programm (mit Gödelnummer i) die Funktion ϕ? Oder anders ausgedrückt: Ist ϕ i = ϕ?
Feste Eingabe
-
Die Mengen
A j = def {i ∈ IN | M i (j)↓} sind für jedes j ∈ IN unentscheidbar, z.B. die Menge A 3 aller Algorithmen, die bei Eingabe 3 anhalten.
Feste Ausgabe
Die Mengen B j = def {i ∈ IN | es ex. x ∈ IN mit ϕ i (x) = j} sind für jedes j ∈ IN unentscheidbar, z.B. die Menge B 3 aller Algorithmen, die irgendwann die Ausgabe 3 liefern.
-
-