Для любого языка существует такой, что но

Я пытаюсь придумать доказательство для следующего:

Для любого языка $A$ , существует язык $B$ такие , что $A \le_{\mathrm{T}} B$ , но B $\nleq_{\mathrm{T}} A$ .

Я думал о том, чтобы позволить $B$ быть $A_{\mathrm{TM}}$ , но я понимаю, что не все языки Тьюринга сводимы к $A_{\mathrm{TM}}$ , поэтому $A \le _T B$ не будет выполняться. Какой другой выбор $B$ у меня есть, который позволил бы мне написать TM, который использует оракула для $B$ чтобы решить $A$ ?

Спасибо!

computability reductions undecidability user1354784
источник

Как насчет ?

B = N P^{A}

$B = NP^A$

Евгений

Подумайте о Проблеме Остановки на машинах Тьюринга с оракулом .

A

$A$

Уиллард Жан

@ user1354784 Можно перечислить машины Тьюринга с оракуломТак что попробуйте использовать стандартный диагонализацию, где единственным изменением является то , что для каждого , представляет оракул TM с оракулом вместо нормального ТМ.

A

$A$

α \in Σ^{*}

$\alpha\in\Sigma^*$

M_{α}

$M_\alpha$

A

$A$

Уиллард Жан

@DavidRicherby Да, но B не исправлен, он построен, зная, что такое A. Если нам дают немного A, мы строим B, который принимает каждого оракула TM с оракулом для этого конкретного A, который принимает строки в A. Если нам дают другой A, список TM в B будет другим.

user1354784

@ user1354784 Точно. Я имел в виду этот комментарий как еще одно объяснение того, почему мы не можем принять как вы предложили (и уже отклонили по другой причине) в своем вопросе. Я забыл объяснить, что это было то, о чем я говорил - извините за путаницу там.

B = A_{T M}

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

Дэвид Ричерби

Ответы:

Пусть , Тьюринг скачок . Это основной результат в теории степеней Тьюринга. $B=A'$ $A$

Бьёрн Кьос-Ханссен
источник

Прежде чем углубиться в хороший ответ, а именно в то, что мы можем релятивизировать проблему остановки, чтобы назначить каждому языку язык такой, что (среди прочего) - стоит посмотреть глупый ответ: $X$ $X'$ $X<_TX'$

Кантор показал, что существует бесчисленное множество языков.
Но каждый конкретный язык может вычислять только исчисляемое количество языков: одна машина Тьюринга может дать только одно сокращение от заданного языка , и существует только счетное количество машин Тьюринга. $A$ $A$

Итак, на самом деле мы знаем, не делая никакой серьезной работы, что:

Для каждого языка , большинство (= все , но счетное число) языков удовлетворяют условию . $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$

Таким образом, мы можем применить вышеизложенное, чтобы получить:

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

Тогда возникает вопрос о предоставлении не глупых доказательств, а именно о естественном способе создания языка, более сложного, чем данный, и для этого нужен переход Тьюринга; но стоит понять этот неконструктивный аргумент сам по себе.

Ной Швебер
источник