Проблема остановки
Проблема Халтинга - это проблема компьютерной науки. Проблема заключается в том, чтобы посмотреть на компьютерную программу и выяснить, будет ли она работать вечно или нет. Мы говорим, что программа "решает проблему останова", если она может посмотреть на любую другую программу и сказать, будет ли эта другая программа работать вечно или нет.
Например, такая программа:
пока Правда: продолжай;зациклится навсегда, но программа
пока Ложь: продолжай;останавливается очень быстро.
Есть ли программа, которая решает проблему остановки? Оказывается, нет. Мы доказываем этот факт, показывая, что если есть программа, которая решает проблему остановки, то происходит что-то невозможное. Так что на данный момент мы будем действовать так, как будто на самом деле есть программа, которая решает проблему остановки. Здесь P - это функция, которая будет оценивать функцию F (вызываемую с аргументом I) и возвращать true, если она работает вечно, и false иначе.
def P(F, I): если F(I) работает вечно: верните True; иначе: верните False;P может посмотреть на любую программу и узнать, будет ли она работать вечно или нет. Мы используем P, чтобы сделать новую программу, которую мы будем называть Q. Что Q делает, так это смотрит на другую программу и затем отвечает на следующий вопрос: "Если мы запустим эту программу и заставим её посмотреть на копию самой себя, будет ли она выполняться вечно?". Мы можем сделать Q, потому что у нас есть P. Все, что нам нужно сделать, это сказать Q, чтобы он создал новую программу, которая является старой программой, смотрящей на себя, а затем использовать P, чтобы узнать, будет ли новая программа работать вечно или нет.
Def Q(F): вернуть P(F, F);Теперь мы делаем другую программу, и R. R смотрит на другую программу и спрашивает Q о ее ответе на эту программу. Если Q отвечает "да, если мы запустим эту программу и заставим её посмотреть на копию самой себя, она будет выполняться вечно", то R останавливается. Если Q отвечает "нет, если мы запустим эту программу и заставим её посмотреть на копию самой себя, она не будет работать вечно", то R входит в бесконечный цикл и работает вечно.
def R(F): if Q(F): return; // termination else: while True: continue; //loop foreverТеперь мы посмотрим, что произойдет, если мы заставим R взглянуть на копию самого себя. Могут произойти две вещи: он либо остановится, либо будет работать вечно.
Если запуск R и заставить его посмотреть на копию самой себя не выполняется навсегда, то Q ответил "да, если мы запустим эту программу и заставим его посмотреть на копию самой себя, то он будет выполняться навсегда". Но Кью сказал это, когда смотрел на саму R. Итак, что В на самом деле сказал: "Да, если мы запустим R и заставим его посмотреть на копию самого себя, он будет работать вечно". Итак: Если R, запущенный на копии самого себя, не будет работать вечно, то он будет работать вечно. Это невозможно.
Если запустить R и заставить его посмотреть на копию самой себя, то Q ответил "нет, если мы запустим эту программу и заставим её посмотреть на копию самой себя, то она не будет запущена навсегда". Но Кью сказал это, когда смотрел на саму R. Итак, что Кью на самом деле сказал: "Нет, если мы запустим R и заставим его посмотреть на копию самого себя, то он не будет работать вечно". Итак: Если R, запущенный на копии самого себя, работает вечно, то он не будет работать вечно. Это также невозможно.
Что бы ни случилось, мы получаем невозможную ситуацию. Мы сделали что-то не так, и мы должны выяснить, что это было. Большинство вещей, которые мы делали, не были неправильными. Мы не можем сказать, что "заставлять программу смотреть на копию самой себя - это неправильно" или "смотреть на то, что сказала другая программа, а потом зацикливаться, если она сказала одну вещь, и останавливаться, если она сказала другую вещь" - это неправильно. Нет смысла говорить, что нам не позволено делать такие вещи. Единственное, что мы сделали, что выглядит так, как будто это может быть неправильно, - это то, что мы притворились, что такая программа, как P, существует в первую очередь. И поскольку это единственное, что может быть неправильным, и что-то должно быть неправильным, то это оно. Это доказательство того, что такой программы, как П, не существует. Нет программы, которая решает проблему остановки.
Это доказательство было найдено Аланом Тьюрингом в 1936 году.
Вопросы и ответы
В: Что такое проблема Халтинга?
О: Проблема Халтинга - это проблема в информатике, которая рассматривает компьютерную программу и определяет, будет ли эта программа выполняться вечно или нет.
В: Как узнать, решает ли программа проблему Халтинга?
О: Мы говорим, что программа "решает проблему остановки", если она может посмотреть на любую другую программу и сказать, будет ли эта программа работать вечно или нет.
В: Есть ли способ доказать, что такой программы не существует?
О: Да, доказав, что если бы такая программа существовала, то произошло бы нечто невозможное. Это доказательство было найдено Аланом Тьюрингом в 1936 году.
В: Что делает P?
О: P - это функция, которая оценивает другую функцию F (вызываемую с аргументом I) и возвращает true, если она выполняется вечно, и false в противном случае.
В: Что делает Q?
О: Q рассматривает другую программу, а затем отвечает на вопрос, приведет ли выполнение этой же программы на самой себе к бесконечному циклу. Он делает это, используя P для оценки заданной функции F.
В: Что делает R?
О: R смотрит на другую программу и спрашивает у Q ответ по этой конкретной программе. Если Q отвечает "да, если мы запустим эту программу и заставим ее посмотреть на копию самой себя, она будет работать вечно", то R останавливается; однако, если Q отвечает "нет, если мы запустим эту программу и заставим ее посмотреть на копию самой себя, она не будет работать вечно", то R входит в бесконечный цикл и работает вечно.
В: Что произойдет, если Вы заставите R посмотреть на себя?
О: Могут произойти две вещи - либо R остановится, либо будет работать вечно - но оба результата невозможны согласно тому, что было доказано о несуществовании программ, подобных P, поэтому что-то должно было пойти не так где-то на пути, ведущем к тому, чтобы заставить R посмотреть на себя.
