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

Проблема останова - одно из понятий информатики. Это вопрос, который формулируется очень просто: возможно ли взять какую-то программу и определить по ее тексту, что она не зациклится (т.е. остановится она когда-нибудь или нет)?

Ответ на него отрицательный: сделать этого нельзя. Нужно только запускать программу и тестировать, да и то это ничего не доказывает. Если программа отработала год и не остановилась, то она вполне может еще остановиться на следующий день.

В учебниках по дискретной математике невозможность решения проблемы останова формально доказывается, но, как по мне, слишком сложно и непонятно.

У Грегори Чейтина я нашел гораздо более простое доказательство и чуть его переписал, чтобы оно стало еще проще. Оно похоже на парадокс лжеца.

Предположим, что мы написали супер-мега-функцию, которая по тексту другой может сказать, остановится та или нет.

function does_halt(program)
{
  // здесь идет очень сложный алгоритм анализа
}

Теперь сочиним функцию-лжеца:

function liar()
{
  if (does_halts(liar))
  {
    while() {}
  }
}

Она спрашивает у супер-анализатора: я остановлюсь? И если тот отвечает "да", то она говорит - фиг вам, и зацикливается. Если он отвечает "нет", то она тоже говорит фиг вам, и назло останавливается.

А теперь спросим у анализатора

print does_halt(liar)

То есть, зацикливается ли функция liar ? И что он должен ответить? Если он скажет "да" - это вранье, потому что она остановится. Если ответит "нет" - тоже вранье, потому что тогда она зациклится.

Получили противоречие. Это означает, что функцию does_halt написать нельзя, проблема останова в принципе нерешаема.