haltingproblem Доказательство противоречия

Сначала позвольте мне вернуться к самому доказательству.

HALT_TM неразрешим

Предположим, что любая машина имеет описание в виде строки. Пусть HALT_TM = {<M, w>| M is a TM and M halts on input w} и A_TM = {<M,w>| M is a TM and accepts w}. Здесь я предполагаю, что мы знаем, что A_TM неразрешимо (доказательство может быть выполнено путем диагонализации и понимания того, что, поскольку существует больше языков, чем машин Тьюринга, и поскольку данная ТМ решает только один язык, то некоторые языки не определены).

Предположим от противного, что HALT_TM разрешимо, а это означает, что мы располагаем решающим устройством D для этого языка. Тогда мы сможем построить машину M, которая решает A_TM. На входе <M', w> M делает следующее:

• Запустите D на входе <M',w>
• Если D отклонить, отклонить, иначе запустить M' на w (пока не остановится, что мы знаем, потому что D не отклонил!)
• Если M' принимает, принимайте, если отклоняет, отклоняйте.

Здесь мы видим противоречие с нашим предположением

Универсальные машины Тьюринга

Теперь суть вашего вопроса: вы на самом деле передаете M любое действительное описание машины M', не обязательно <M> себя. Помните, что TM и «программа» на самом деле эквивалентны: см. этот хороший ответ для более подробной информации. Цитируя тот же ответ: «Машина Тьюринга — это формальный аналог алгоритма». Одна из возможностей машин Тьюринга заключается в том, что они могут быть закодированы в виде строки, что позволяет другой машине Тьюринга (называемой «универсальной Машина Тьюринга"), чтобы выполнить их. Поскольку данная машина представляет собой алгоритм, вы видите, что фактически вводите в свою ТМ «верхнего уровня» программу и входные данные по вашему выбору.