Problem für die Klasse ALLER Sprachen abgeschlossen

Sie haben Ihren Begriff der Reduktion nicht spezifiziert, daher gehe ich davon aus, dass Sie eine zählbare Klasse von Funktionen auswählen , die für Reduktionen verwendet werden kann (jede Teilmenge der berechenbaren Funktionen würde hier funktionieren). Sei eine beliebige Klasse von Sprachen über einem festen Alphabet , sagen wir . Eine Sprache ist schwer für (bezogen auf ) , wenn für jede existiert derart , dass iff . Wenn auch dann sagen wir, dass $\cal F$ $\cal L$ $\Sigma$ $\Sigma = \{0,1\}$ $K$ $\cal L$ $\cal F$ $L \in \cal L$ $f \in \cal F$ $x \in L$ $f(x) \in K$ $K \in \cal L$ $K$ ist komplett für . $\cal L$

Ich werde jetzt zeigen, dass keine Sprache für schwer ist . Nehmen wir an, dass waren -hard. Sei eine Aufzählung der Funktionen in (eine solche Aufzählung existiert, da sowohl als auch zählbar sind). Definieren Sie eine Sprache durch Da , gibt es eine Funktion so dass für alle , iff . Seit gibt es $\mathsf{ALL}$ $K$ $\mathsf{ALL}$ $f_x : x \in \Sigma^*$ $\cal F$ $\Sigma^*$ $\cal F$ $L$

L = {x : f_{x} (x) \notin K} .

$L = \{x : f_x(x) \notin K \}.$

L \in A L L

$L \in \mathsf{ALL}$

f \in F

$f \in \cal F$

x \in Σ^{*}

$x \in \Sigma^*$

x \in L

$x \in L$

f (x) \in K

$f(x) \in K$

f \in F

$f \in \cal F$

x \in Σ^{*}

$x \in \Sigma^*$ so dass . Für diese besondere , iff . Jedoch definitions iff .

f = f_{x}

$f = f_x$

x

$x$

x \in L

$x \in L$

f_{x} (x) \in K

$f_x(x) \in K$

x \in L

$x \in L$

f_{x} (x) \notin K

$f_x(x) \notin K$

Yuval Filmus
quelle

Interessantes Kardinalitätsargument. Was ist mit dem Problem, das ich in der Frage angegeben habe (eine Funktionsbeschreibung gegeben, die Wahrheitstabelle zurückgeben)? Es scheint, dass dieses Problem (das natürlich sehr unentscheidbar ist) es ermöglichen würde, jedes Problem zu lösen (die Wahrheitstabelle aus dem Orakel holen und dann das Problem nachschlagen). Können Sie erklären, wo meine Argumentation falsch ist, abgesehen von der Tatsache, dass (offensichtlich) kein solches Orakel existiert?

Demi

Es ist deine Intuition, die schief geht. Sie können kein "Problem" eingeben, da Probleme im Allgemeinen keine endlichen Beschreibungen haben.

Yuval Filmus

Im Grunde genommen ist sogar ein allmächtiges Orakel (das jede gestellte Frage beantworten könnte) immer noch nicht ausreichend, um einige Probleme zu lösen, weil es keine Möglichkeit gibt, dem Orakel die erforderlichen Informationen zu geben?

Demi

Genau aus diesem Grund gibt es kein allmächtiges Orakel. Der Beweis der Unentscheidbarkeit des Halteproblems kann erweitert werden, um zu zeigen, dass bei jedem Orakel das Problem der Entscheidung, ob eine Turing-Maschine mit Zugang zu anhält, selbst bei Zugang zu unentscheidbar bleibt . Auf der anderen Seite können wir ein Orakel konstruieren, das entweder nach "umleiten" oder das Halteproblem für Maschinen mit Zugriff auf lösen kann . Das Orakel ist mächtiger als .

O

$O$

O

$O$

O

$O$

O

$O$

O

$O$

O

$O$

Yuval Filmus

Ah okay. Der Grund dafür, dass es keine allmächtigen Orakel gibt, während , ist, dass der Rat von einer unendlichen Menge an Informationen über das Problem abhängen kann?

E X P / e x p = A L L

$EXP/exp = ALL$

Demi

Problem für die Klasse ALLER Sprachen abgeschlossen

Antworten: