Please enable JavaScript.
Coggle requires JavaScript to display documents.
Entscheidbarkeit und Aufzählbarkeit (Abschlusseigenschaften # # ( Jede…
Entscheidbarkeit und Aufzählbarkeit
Semi-entscheidbare Mengen
Entscheidungsproblem
Beim Entscheidungsproblem für Mengen wollen wir für beliebige Kandidaten x feststellen, ob x ∈ A oder x !∈ A
Semi-charakteristische Funktion
Liefert 1 falls x in A, n.d. sonst
existiert immer
nur total, wenn A der gesamte Grundbereich G ist
G = def {n | n ≥ 2 und es ex. Primzahlen p, q mit 2n = p+q}
Goldbachsche Vermutung: G = IN \ {0, 1}
Es ex. ein Algorithmus, der für jedes einzelne n die Frage, ob n ∈ G ist, richtig beantwortet.
• Ob das jedoch für alle n ≥ 2 gilt, ist unklar. Für alle Zahlen bis 26 * 10^17 ist das experimentell nachgewiesen (Stand Nov. 2011).
Collatz-Problem
Entscheidbare Mengen
Charakteristische Funktion
A ist in REC, wenn die charakteristische Funktion berechenbar ist
#
total
Liefert 1 wenn x in A, 0 sonst
Klasse der entscheidbaren Mengen heißt REC
Eine Menge ist entscheidbar wenn sie selbst und ihr Komplement semi-entscheidbar sind
Abschlusseigenschaften
#
#
Jede endliche Menge ist entscheidbar (einschl. ∅).
Das Komplement einer entscheidbaren Menge ist entscheidbar.
Vereinigung und Durchschnitt entscheidbarer Mengen sind entscheidbar.
Ist A entscheidbar und f eine berechenbare und totale Funktion, dann ist f −1 (A) = def {x | f(x) ∈ A} entscheidbar (Urbild von A unter f).
Aufzählbarkeit
Eine Menge A ⊆ IN m mit m ≥ 0 heißt aufzählbar gdw. A = ∅ oder es existiert eine berechenbare und totale Funktion f : IN →IN^m mit Wf = A.
Die Klasse aller aufzählbaren Mengen heißt RE
Jede auszahlbare Menge ist semi-entscheidbar
#