gatoazul (gatoazul) wrote,
gatoazul
gatoazul

Category:

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

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

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

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

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

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

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

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

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

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

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

print does_halt(liar)

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

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

  • О том, что происходит

    Нехорошо оставлять милую девушку в беде. К счастью, объяснить ей, что происходит в РФ, совсем несложно. Для этого не нужно вывалить ей на голову…

  • Бессмертные

    Вот что меня крайне поражает в "новых русских" и их позднейших инкарнациях. Они построили или на вырученные от них деньги построили…

  • Как пройдет ковид-19

    Вероятных варианта два. Первый. В одно прекрасное утро мы проснемся и с изумлением обнаружим, что "эпидемия" ковида закончилась. Резко и…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 88 comments

  • О том, что происходит

    Нехорошо оставлять милую девушку в беде. К счастью, объяснить ей, что происходит в РФ, совсем несложно. Для этого не нужно вывалить ей на голову…

  • Бессмертные

    Вот что меня крайне поражает в "новых русских" и их позднейших инкарнациях. Они построили или на вырученные от них деньги построили…

  • Как пройдет ковид-19

    Вероятных варианта два. Первый. В одно прекрасное утро мы проснемся и с изумлением обнаружим, что "эпидемия" ковида закончилась. Резко и…