Покажите, что для каждого языка существует более сложный язык

Question

Я столкнулся с этой проблемой, которую никак не мог разгадать...Для каждого языка $A$, предполагается , что должен существовать язык $B$ такой , что:

$$ A \leq_T B $$

но:

$$ B ot \leq_T A $$

Если это так $A \leq_TB$ и $B \leq_T A$, это легко, так как мы можем просто позволить $B := \bar{A}$, но для всего вышесказанного я ничего не мог придумать.Какая - нибудь помощь ?

Answer 1

Есть несколько способов подойти к этому.

Вы можете использовать аргумент подсчета, чтобы показать, что для каждого $A$ существует $B$ такой , что $B leq_T A$.Пусть $L_A=\{B| B\le_T A\}$ обозначим множество всех языков, сводимых к $A$.Покажи это $f:L_A ightarrow \mathbb{N}$ это сопоставляет языки $B\in L_A$ Для $n$ такой , что $M_n$ является сокращением от $B$ Для $A$ является инъекцией и приходит к выводу, что существует язык вне $L_A$.Далее, вы хотите сделать его сравнимым с $A$.Мы можем получить такой язык с помощью оператора join:

$A\sqcup B=\{0 Вт|вт\в A\}\cup\{1 Вт|Вт\в B\}$.

Я предоставляю вам самим показать это $A\sqcup B$ является наименьшей верхней границей для $A,B$, т. е. $A,B\le_T A\sqcup B$ и дополнительно для каждого $L$ такой , что $A,B\le_T L$ у нас есть $A\sqcup B\le L$ (вас волнует только первое).Покажите, что если $B leq_T A$ тогда $A\sqcup B leq_T A$.

Другой способ доказать это - использовать оператор прыжка.Нам нужно ввести понятие машины oracle, а затем покажите , что $B=\left\{\left(M^A,w ight)| \текст{$M ^A$ останавливается на $w $} ight\}$ это строго более сложный язык.Доказательство идентично неразрешимости стандартной задачи остановки, только теперь мы показываем более сильное свойство, к которому не имеет доступа ни одна машина с oracle $A$ могу решить $B$.

Вы также можете напрямую сконструировать такой язык с помощью диагонализации.определить $B=\left\{n | M_n(n) otin ight\}$.Мы построили $B$ такой , что любая вычислимая функция $M_n$ не может быть сокращением от $B$ Для $A$ по крайней мере, на одном входе (в частности, на кодировке сокращения).Теперь вы можете использовать оператор объединения, чтобы сделать их сопоставимыми.