Проблема Халтинга - это проблема компьютерной науки. Проблема заключается в том, чтобы посмотреть на компьютерную программу и выяснить, будет ли она работать вечно или нет. Мы говорим, что программа "решает проблему останова", если она может посмотреть на любую другую программу и сказать, будет ли эта другая программа работать вечно или нет.

Например, такая программа:

 пока Правда: продолжай;

зациклится навсегда, но программа

 пока Ложь: продолжай;

останавливается очень быстро.

Есть ли программа, которая решает проблему остановки? Оказывается, нет. Мы доказываем этот факт, показывая, что если есть программа, которая решает проблему остановки, то происходит что-то невозможное. Так что на данный момент мы будем действовать так, как будто на самом деле есть программа, которая решает проблему остановки. Здесь 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 году.