Обманывает ли доказательство неразрешимости проблемы Прекращения путем обращения результатов?

У меня проблемы с пониманием проблемы остановки Тьюринга.

Его доказательство предполагает, что существует магическая машина которая может определить, будет ли компьютер останавливаться или зацикливаться навсегда для данного ввода. Затем мы подключаем другую машину, которая обращает вывод, и у нас есть противоречие, и поэтому не может существовать.$H$$H$

Я обеспокоен тем, что кажется, что мы говорим, что ответ неправильный, потому что мы изменили его. Как аналогия, если есть машина с именем , которая выдает правильный ответ на определенные входы и неправильный ответ на другие. Затем мы присоединяем другую машину, которая инвертирует результат поэтому комбинация двух машин противоречит определениюОбе машины теперь генерирует неправильные ответы для входов , которые определяются для вывода правильных ответов и выводят правильные ответы на входы , которые определяются для вывода неправильных ответов. Будет ли это называться противоречием, и, следовательно, не существует машины, которая выводит правильный ответ на некоторые входные данные и неправильные ответы на другие?A A A $A$$A$$A$$A$$A$

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

Длинная версия : Сначала мы набросаем доказательство (или хотя бы одну его версию - их много).

1. Предположим, что у нас есть машина Тьюринга которая решает, останавливается ли машина Тьюринга на входе или нет.М $\mathrm{HALT}(\langle M\rangle, x)$$M$$x$
2. Используя мы создаем машину которая использует чтобы проверить, останавливается ли на или нет, затем делает обратное, то есть, если останавливается на , зацикливается, если не останавливается на , останавливается.Р Л Я Р ( ⟨ М ⟩ , х ) Н л Т М х М х Ж Л Я Р М х F L I $\mathrm{HALT}$$\mathrm{FLIP}(\langle M\rangle, x)$$HALT$$M$$x$$M$$x$$\mathrm{FLIP}$$M$$x$$\mathrm{FLIP}$
3. Наконец, мы создаем TM (у меня закончились хорошие имена), который берет описание TM и запускает с вводом , выводит все, что выводит .Р Л Я Р ( ⟨ М ⟩ , ⟨ М ⟩ ) Р л я $\mathrm{C}(\langle M \rangle)$$\mathrm{FLIP}$$(\langle M \rangle, \langle M \rangle)$$\mathrm{FLIP}$

Важно отметить, что до тех пор, пока существует decider , каждый из этих шагов прост в реализации; просто должен использовать чтобы проверить, что делать, и просто дублирует свой ввод для передачи в .F L I P H A L T C F L I $\mathrm{HALT}$$\mathrm{FLIP}$$\mathrm{HALT}$$\mathrm{C}$$\mathrm{FLIP}$

Противоречие возникает, когда мы смотрим на то, что происходит, когда мы запускаем . Либо останавливается, когда задается как ввод, либо нет. решит это:С Н Л $\mathrm{C}(\langle\mathrm{C}\rangle)$$\mathrm{C}$$\mathrm{HALT}$

• Если останавливается на входе , скажет , но тогда будет зацикливаться, поэтому будет зацикливаться противоречащий . ⟨ С ⟩ Н Л Т Y Е сек Р л я Р С Н Л $\mathrm{C}$$\langle\mathrm{C}\rangle$$\mathrm{HALT}$$\mathsf{Yes}$$\mathrm{FLIP}$$\mathrm{C}$$\mathrm{HALT}$
• Если зацикливается на входе , скажет , но тогда остановится, поэтому также будет остановка, противоречащая . ⟨ C ⟩ Н Л Т Н О Р Л Я Р C H A L $\mathrm{C}$$\langle\mathrm{C}\rangle$$\mathrm{HALT}$$\mathsf{No}$$\mathrm{FLIP}$$\mathrm{C}$$\mathrm{HALT}$

Поскольку каждый из этапов в построении является четким, мы можем только заключить, что не может существовать; мы построили случай, когда независимо от того, что он говорит, не может решить, что выводить, то есть проблема неразрешима. Просто чтобы немного поразмыслить над этим, не может существовать - то есть не может быть ТМ, решающего проблему остановки - потому что есть хотя бы один случай, который мы явно создали, где нет логически возможный ответ. Помните, что решающее лицо не может выводить неправильный ответ и должно что-то выводить, но в случае, если мы построили, оба возможных ответа неверны.H A L T H A L $\mathrm{HALT}$$\mathrm{HALT}$$\mathrm{HALT}$

Вы обсуждаете два разных значения «противоречить».

По вашей аналогии, машина A и ее перевернутая модификация противоречат друг другу только в том смысле, что их выходы всегда различны. (Например, они могут реализовать две тестовые функции на целых числах: « x ≤ 5?» И « x > 5?»). Это, безусловно, означает, что «противоречие» может означать в повседневном использовании, но это не то, что подразумевается под логическим доказательства.

В логических доказательствах это означает нечто более сильное: то, что просто невозможно. Например, функция, которая возвращает «true» на всех входах больше 5 и «false» на всех входах меньше 10 - это противоречиво в этом более сильном смысле, потому что, скажем, для 7, ее вывод должен быть «истинным» и «ложь», но это не одно и то же. Аргумент Тьюринга показывает, что программа остановки противоречива в более сильном смысле: если предположить, что она приводит к чему-то невозможному или уже известному как ложное.

Вот еще одно доказательство того, что проблема остановки неразрешима. Мы говорим, что программа выводит строку если она останавливается, и выводит . (Если программа никогда не останавливается, то она не выводит никакой строки.) Определите как длину самой длинной строки, которая выводится программой C длиной не более .$x$$x$$f(n)$$n$

Предположим, что проблема остановки была разрешима. Тогда может быть вычислено программой на C:$f(m)$

На входе запустите все программы остановки C длиной не более и определите их выход; вернуть длину максимального выхода.$m$$m$

Это означает, что для каждого мы можем написать программу которая выводит ноль. Какова длина ? Существует фиксированный шаблон C-программы с заполнителем, который реализует ; заполнитель должен быть заполнен константой . Задание занимаетсимволов (здесь - длина десятичного представления ), где . Шаблон занимает некоторое фиксированное число символов , поэтому длина равна . Если мы выберем$m$$P_m$$f(m)+1$$P_m$$P_m$$m$$m$$|m|$$|m|$$m$$|m| \approx \log_{10} m$$T$$P_m$$T + \log_{10} m$$m$ достаточно большой ( ), у нас будет , и, таким образом, будет по крайней мере размером строки, выводимой , т. е. . Мы достигли противоречия.$m=2T$$T + \log_{10} m \leq m$$f(m)$$P_m$$f(m) \geq f(m) + 1$