Сокращение с $HALT$ до $A_{TM}$

cs.stackexchange https://cs.stackexchange.com/questions/125609

  •  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}$ неразрешимо.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с cs.stackexchange
scroll top