Für jede Sprache

Ich versuche, einen Beweis für Folgendes zu finden:

Für jede Sprache gibt es eine Sprache so dass aber B . $A$ $B$ $A \le_{\mathrm{T}} B$ $\nleq_{\mathrm{T}} A$

Ich dachte zu lassen seine , aber ich merke , dass nicht alle Sprachen sind Turing - reduzierbar auf , also nicht halten würde. Welche andere Wahl von habe ich, die es mir ermöglichen würde, ein TM zu schreiben, das ein Orakel für , um zu entscheiden ? $B$ $A_{\mathrm{TM}}$ $A_{\mathrm{TM}}$ $A \le _T B$ $B$ $B$ $A$

Vielen Dank!

computability reductions undecidability user1354784
quelle

Wie wäre es mit

B = N P^{A}

$B = NP^A$

Eugene

Denken Sie an das Halteproblem auf Maschinen mit Orakel - Turing

A

$A$

Willard Zhan

A

$A$

α \in Σ^{*}

$\alpha\in\Sigma^*$

M_{α}

$M_\alpha$

A

$A$

@DavidRicherby Ja, aber B ist nicht behoben, es wird gebaut, um zu wissen, was A ist. Wenn wir etwas A erhalten, bauen wir ein B, das jedes Orakel TM akzeptiert, mit einem Orakel für dieses spezifische A, das Zeichenfolgen in A akzeptiert. Wenn wir ein anderes A erhalten, ist die Liste der TMs in B anders.

user1354784

B = A_{T M}

$B=A_{\mathrm{TM}}$

Antworten:

$B=A'$ $A$

Bjørn Kjos-Hanssen
quelle

$X$ $X'$ $X<_TX'$

Cantor hat gezeigt, dass es unzählige Sprachen gibt.
$A$ $A$

Tatsächlich wissen wir also, ohne ernsthafte Arbeit zu leisten, dass:

$A$ $B$ $B\not\le_TA$

$X,Y$ $X\oplus Y$ $X$ $Y$ $X$ $Y$ $X\oplus Y=\{2i: i\in X\}\cup\{2i+1: i\in Y\}$ $X\oplus Y\ge_TX,Y$ $\le_T$

Wir können also das oben Gesagte anwenden, um Folgendes zu erhalten:

$A$ $B$ $A<_TA\oplus B$

Dies wirft dann die Frage auf, einen nicht dummen Beweis zu liefern, nämlich einen natürlichen Weg, eine Sprache zu produzieren, die streng komplizierter ist als eine gegebene, und dafür ist der Turing-Sprung gedacht; Es lohnt sich jedoch, dieses nichtkonstruktive Argument allein zu verstehen.

Noah Schweber
quelle