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

  • Gregory Chaitin, "Proving Darwin"

    Одна постоянная посетительница этого журнала не любит теорию эволюции, считая ее шарлатанством и сомнительной выдумкой. И я, кажется, догадываюсь,…

  • Steve Keen. "Debunking Economics: The Naked Emperor of the Social Sciences"

    Если вы играли в Angry Birds, то знаете, что там есть такие черные птицы-бомбы, которые мало того что с легкостью ломают даже бетонные стены, так…

  • Страх и ужас

    С книгами как с женщинами - с возрастом интересных становится все меньше и меньше. Проклятый опыт мешает - открываешь и сразу видишь, что там в сотый…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 88 comments

  • Gregory Chaitin, "Proving Darwin"

    Одна постоянная посетительница этого журнала не любит теорию эволюции, считая ее шарлатанством и сомнительной выдумкой. И я, кажется, догадываюсь,…

  • Steve Keen. "Debunking Economics: The Naked Emperor of the Social Sciences"

    Если вы играли в Angry Birds, то знаете, что там есть такие черные птицы-бомбы, которые мало того что с легкостью ломают даже бетонные стены, так…

  • Страх и ужас

    С книгами как с женщинами - с возрастом интересных становится все меньше и меньше. Проклятый опыт мешает - открываешь и сразу видишь, что там в сотый…