Сокращение с $HALT$ до $A_{TM}$
-
29-09-2020 - |
Вопрос
Я знаю сокращение до от $A_{TM}$ к $ОСТАНОВКА$.Но является ли следующее сокращение от $ОСТАНОВКА$ к $A_{TM}$ правильно?
Мы ищем полную вычислимую функцию $f$ отображение из $ОСТАНОВКА$ к $A_{TM}$.Следующая ТМ $F$ вычисляет уменьшение $f$.
F = on input <T, w>
create the following TM T':
T' = on input v:
start T on v
if T accepts or rejects, *accept*
return <T',w>
Я думаю, что линия if T accepts or rejects, *accept*
это правильно, но было бы здорово, если бы кто-нибудь мог это проверить.
Редактировать:Я нашел следующие слайды, но я не думаю, что конструкция там правильная: http://slideplayer.com/slide/13791105/
Решение
Существует множество понятий "редукции". Вы правильно описали сокращение "много-один" от $ОСТАНОВКА$ к $A_{TM}$.Сокращение, на которое вы ссылались (более конкретная ссылка здесь) вместо этого является сокращение таблицы истинности.Это более общие объекты (так что ваш результат будет более сильным).Каждое из них, в свою очередь, подпадает под гораздо более широкое понятие Сокращение Тьюринга.
В то время как сокращения по принципу "много-один", как правило, являются понятием по умолчанию в теории сложности, сокращения по Тьюрингу и результирующие структура степени являются стандартными в теории вычислимости.Обратите внимание, что если все, что я хочу сделать, это доказать неразрешимость некоторого множества, то достаточно сокращения по Тьюрингу из некоторого заведомо неразрешимого множества.
Во-первых, давайте четко вспомним определения задействованных языков:
$A_{TM}=\{\langle M,w angle:М$ останавливает и принимает при вводе $w\}$.
$HALT=\{\langle M,w angle:М$ останавливается при вводе $w\}$.
Предлагаемое вами сокращение $ОСТАНОВКА$ к $A_{TM}$ является правильный:подаренный $М$, мы можем вычислимо построить новую машину $\шляпа{M}$ который принимает именно те строки, на которых $М$ останавливается.(По сути, просто замените все состояния "отклонить" в $М$ по состояниям "принять".)
Теперь давайте посмотрим на другое сокращение, на которое вы ссылались (более конкретная ссылка здесь).
По сути, вместо перехода к "все состояния остановки принимаются" связанный аргумент рассматривается отдельно:
оригинальная машина, и
"противоположная" машина, которая принимает именно то, что отвергает исходная, и наоборот.
Утвердительный ответ в любом случае в $A_{TM}$ обеспечивает положительный ответ для исходной машины в $ОСТАНОВКА$.
На первый взгляд я не вижу причин делать это вместо того, чтобы следовать вашим аргументам, особенно потому, что это дает более слабый результат, но это правильно и достаточно, чтобы доказать более широкое утверждение на слайдах, а именно, что $A_{TM}$ неразрешимо.