Прежде всего позвольте мне вернуться к самому доказательству.
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 не отвергают)
- Run
D на входе <M',w>
- Если
D отклонить, отклонить, иначе запустить M' на w
- Если
M' принимает, признает, отклоняет, отклоняет.
Там мы видим противоречие с предположением
Универсальные машины Тьюринга
Теперь ядро вашего вопроса: вы на самом деле кормить M любое действительное описание машины M', не обязательно <M> сам. Помните, что ТМ и «программа» на самом деле эквивалентны: см. Это приятно answer для более подробной информации. Цитируя этот же ответ: «Машина Тьюринга является формальным аналогом алгоритма». Одной из мощностей машин Тьюринга является то, что они могут быть закодированы в виде строки, позволяя другим машинам Тьюринга (называемым «Universal Turing Machine») выполнять их. Поскольку данный компьютер является алгоритмом, вы видите, что на самом деле вы подаете программу ТМ «топ-уровень» и ввод по вашему выбору.