"универсальная логическая машина" и теоремы Гёделя
Многие из читателей ЖЖ интересовались вопросами, связанными со знаменитыми теоремами Гёделя о неполноте. О них часто пишут в разного рода популярных изданиях, что не удивительно, так как эти теоремы имеют общенаучный смысл. Я решил осуществить давно намеченный план популярного (т.е. понятного неспециалисту) изложения сути дела. Трудность состоит в том, что сами теоремы непросто даже сформулировать: этому должны предшествовать весьма длинные определения и описания разных понятий из области математической логики. Однако можно пойти по другому пути. Дело в том, что можно рассмотреть другие ничуть не менее ценные факты (тесно связанные с теоремами Гёделя), которые формулируются намного проще, а их общепознавательная составляющая ничуть не меньше. Кроме того, вместо работы с исчислениями наподобие формальной арифметики, можно работать с гораздо более близкими широкому читателю вещами -- алгоритмическими языками программирования. Какое-то представление о них имеет каждый, кто посещал уроки информатики в школе.
Собственно о теоремах Гёделя речь тоже пойдёт, но во второй части текста.
Мыслители прошлого не раз задумывались над возможностью создания такой машины, которая, грубо говоря, давала бы ответы на все вопросы, интересующие человечество. Речь могла идти как о математических, так и о философских "истинах". Определённые успехи в области естествознания делали этот проект не столь уж фантастическим в глазах современников. Лейбниц мечтал о том времени, когда философские споры будут разрешаться посредством вычислений. Итак, в чём же может состоять сам проект? В том, что человечество, постигая мир, постепенно открывает для себя некий набор основных "истин" (наподобие аксиом геометрии), при помощи которых далее можно будет чисто логически доказать любое представляющее интерес новое "истинное" положение. Известна, например, попытка Спинозы предложить аксиоматический подход в области этики.
Итак, чего бы нам хотелось, если говорить о создании такой "универсальной логической машины"? Например, можно ставить вопрос о создании компьютерной программы, которая давала бы ответ на любой осмысленный вопрос в форме "да" или "нет". Уточнение того, что следует понимать под "осмысленностью", здесь не является первостепенной задачей, так как круг вопросов можно (хотя бы для начала) искусственно сузить. Мы не будем мучить предполагаемую машину вопрсами типа "что первично: материя или сознание" или "что было раньше: яйцо или курица". Уместно сосредоточиться на вопросах из области математики или даже арифметики (теории чисел), так как здесь не наблюдается значительных расхождений в понимании самих вопросов. Тем, кто считает, что арифметика -- очень простая наука, полезно будет ознакомиться с примерами задач (относящихся к свойствам натуральных чисел), которые не решены по сей день и считаются весьма сложными.
1) Рассмотрим натуральный ряд: 1, 2, 3, 4, 5, 6, 7, 8, ... и так далее. Про каждое из чисел можно спросить, сколько у него имеется делителей (среди натуральных чисел). При этом сразу станет ясно, что каждое из чисел ряда 2, 3, 5, 7, 11, 13, 17, 19, 23, ... имеет ровно два делителя -- единицу и само себя. Такие числа, как многим должно быть известно, называются простыми. Ряд простых чисел бесконечен, что известно со времён Евклида. Обратим внимание на то, что некоторые простые числа отличаются ровно на 2 -- таковы 11 и 13, 17 и 19, 29 и 31, 41 и 43. Такие пары простых чисел принято называть близнецами. Никто не знает, конечно ли количество пар-близнецов. В ответе на этот вопрос состоит хорошо известная старая проблема.
2) Вот пример второй знаменитой проблемы, относящейся к простым числам -- это проблема Гольдбаха -- Эйлера. Формулируется она так: всякое ли чётное число, начиная с 4, можно представить в виде суммы двух простых? Мы легко видим, что 4=2+2, 6=3+3, 8=3+5, 10=3+7=5+5 (т.е. для одного числа может быть несколько разных представлений) и так далее. Но никто не знает, распространяется ли эта закономерность на все дальнейшие чётные числа.
3) Вот менее известный, но эффектный пример. Вопрос таков: какие натуральные числа можно представить в виде суммы кубов трёх целых чисел? То есть при каких натуральных a уравнение x^3+y^3+z^3=a имеет хотя бы одно решение в целых числах (здесь x,y,z могут принимать не только натуральные, но и отрицательные значения, а также быть равными нулю). Сравнительно несложно доказать, что при a=4, 5, 13, 14, 22, 23, ... -- это все числа, дающие при делении на 9 в остатке 4 или 5 -- уравнение решений не имеет. С другой стороны, не известно, имеет ли решение уравнение для всех остальных значений a. Некоторое время был открытым вопрос о числе a=30, и даже в ряде сборников олимпиадных задач по математике встречалось упоминание на сей счёт. Однако сравнительно недавно было выяснено, что уравнение x^3+y^3+z^3=30 обладает решениями. Вот конкретный пример тройки чисел, удовлетворяющих уравнению: x=2220422932, y=-2218888517, z=-283059965. Желающие могут подставить и проверить :)
Наименьшим числом, для которого вопрос пока открыт, является a=33. Интересующиеся могут найти дополнительную информацию здесь:
http://www.asahi-net.or.jp/~kc2h-msm/mathland/math04/cube01.htm
Обращает на себя внимание тот факт, что многие решения найдены совсем недавно.
4) Следующий пример мне очень нравится с давних пор. Каждому натуральному числу n сопоставим число, обозначаемое через f(n), по такому правилу. Если n делится на 3, то полагаем f(n)=2*(n/3). В противном случае рассмотрим дробь (4*n)/3. Здесь f(n) есть округление этой дроби до ближайшего целого. Во втором случае надо просто заменить число 4*n, не делящееся на 3, на одно из соседних, которое делится на три. Например, надо найти f(10). Поскольку 10 на 3 не делится, рассмотрим дробь 40/3. В числителе заменяем 40 на 39 и получаем f(10)=13.
Возьмём какое-то число n и начнём выписывать последовательность n, f(n), f(f(n)), ... -- каждое следующее число получается из предыдущего применением функции f. Что может произойти с этой последовательностью? Возможны два случая. Либо числа возникают всё новые и новые (и тогда последовательность "уходит в бесконечность"), либо где-то произойдёт повторение числа, уже встречавшегося ранее. В последнем случае последовательность "зациклится". Например, если мы начнём с n=1, то получим последовательность из одних единиц. При n=2 мы получим последовательность из чередующихся двоек и троек. Чуть более интересен случай n=4. Здесь возникнет последовательность 4, 5, 7, 9, 6, 4, 5, 7, 9, 6, ... -- здесь периодически повторяется группа из пяти чисел. Наименьшее число, которое пока что отсутствовало -- это n=8. Вот что мы получим в этом случае:
8, 11, 15, 10, 13, 17, 23, 31, 41, 55, 73, 97, 129, 86, 115, 153, 102, 68, 91, 121, 161, 215, 287, 383, 511, 681, 454, 605, 807, 538, 717, 478, 637, 849, 566, 755, 1007, 1343, 1791, 1194, 796, 1061, 1415, 1887, 1258, 1677, 1118, 1491, 994, 1325, 1767, 1178, 1571, 2095, 2793, 1862, 2483, 3311, 4415, 5887, 7849, 10465, 13953, 9302, 12403, ... и так далее.
Какова у этой последовательности дальнейшая "судьба"? (Хороший вопрос для "гадалок", "магов" и прочих представителей мира "экстрасенсорики".) Легко понять, что это процесс полностью детерминированный: его поведение однозначно задаётся выбранным начальным значением. Более того, процесс этот может быть однозначно продолжен не только в будущее, но и в прошлое (это несложное упражнение). Например, перед числом 8 может стоять только 12, перед ним -- 18, перед ним -- 27 и так далее. Вот как выглядит "недалёкое прошлое" процесса перед числом 8:
..., 962, 1283, 1711, 2281, 3041, 4055, 5407, 7209, 4806, 3204, 2136, 1424, 1899, 1266, 844, 1125, 750, 500, 667, 889, 1185, 790, 1053, 702, 468, 312, 208, 277, 369, 246, 164, 219, 146, 195, 130, 173, 231, 154, 205, 273, 182, 243, 162, 108, 72, 48, 32, 43, 57, 38, 51, 34, 45, 30, 20, 27, 18, 12, 8
Весь процесс можно себе представить как некую "траекторию", пролегающую через отметку 8. Эта траектория может быть либо "замкнутой", либо нет. Как обстоит дело в реальности -- никто не знает. На современных компьютерах можно пронаблюдать судьбу процесса на много ходов вперёд, но при этом "зацикливания", т.е. возврата к началу, не наблюдается. Однако из этого ничего не следует. Кто знает, а вдруг ещё немного терпения, и мы в ходе вычислений обнаружим наличие цикла? Для иллюстрации полезно убедиться в том, что циклы на самом деле могут возникать. Скажем, если взять n=44, то даже вручную можно установить, что процесс является периодическим (повторение наступает через 12 шагов).
Итак, мы привели несколько примеров трудных вопросов из области арифметики, чтобы показать, что таковые бывают. Поэтому построение пусть не универсальной, но хотя бы "универсально-арифметической" машины представляло бы интерес. Однако математики сумели ДОКАЗАТЬ, что даже такой машины В ПРИНЦИПЕ НЕ СУЩЕСТВУЕТ. Тем самым вопрос об "универсальной логической машине" автоматически снимается с повестки дня. Разумеется, попытки создавать "машины", решающие более узкие классы задач, не лишены смысла. Также из сказанного не следует, что какая-либо из задач, рассмотренных выше, "неразрешима" в каком-то принципиальном смысле. Однако "вся арифметика" никакой "машине" не по зубам. Об этом пойдёт речь ниже.
Итак, я ставлю себе цель разъяснить, почему это так, а также показать связь между несуществованием означенной "машины" и теоремами Гёделя. Прежде всего надо понять, чего же именно не существует. Нам хотелось бы иметь компьютерную программу (алгоритм), при помощи которой мы могли бы получить ответ на любой интересующий нас вопрос из области арифметики. Вопросы должны задаваться в форме, понятной для машины, то есть на определённом символическом языке. Для этой цели вполне подошёл бы язык формул математической логики, использующих логические символы (логические связки наподобие "и", "или", "не", "влечёт", а также логические кванторы -- "для всех" и "существует"). Давно известно, что этих фрагментов естественного языка вместе с символами арифметических операций достаточно для того, чтобы любой арифметический вопрос смочь выразить на языке символов. Машина, получив вопрос, должна после некоторых вычислений (возможно, долгих) выдать нам правильный ответ на поставленный вопрос в виде "да" или "нет". Заметим, что мы облегчаем работу машине в том плане, что не рассматриваем никакого другого формата ответа. Скажем, мы можем спросить, "конечно ли количество пар-близнецов", "зацикливается ли процесс из примера 4" (после перевода этих вопросов на символический язык). Однако мы не можем задать вопрос из примера 3 "какие числа могут быть представлены...". Зато мы имеем право спросить, может ли число 33 быть представлено в виде суммы кубов трёх целых чисел. Дело в том, что уже с таким кругом вопросов ("да" -- "нет") машина не справится.
Здесь полезно заметить, что "машина" должна уметь давать ответ на ВСЕ описанные выше вопросы из области арифметики. Если мы сосредоточимся на каком-то одном вопросе, то можно сконструировать две простейшие машины, одна из которых всегда говорит "да", а вторая всегда говорит "нет". Ясно, что ровно одна из них ответит на любой конкретный вопрос правильно. Поэтому мы говорим о машинах (или программах, алгоритмах), при помощи которых можно решать целый класс задач; в таких случаях принято говорить о решении некой массовой проблемы.
Для написания компьютерной программы требуется алгоритмический язык. В качестве него можно взять практически любой из уже существующих или придумать какой-то свой. Можно пользоваться упрощённым вариантом одного из уже имеющихся языков. Конечный ответ от этого не зависит. Мы, разумеется, считаем, что ресурсы памяти компьютера потенциально бесконечны -- даже при этом условии требуемую машину построить не удастся. Итак, сейчас надо определиться и зафиксировать для дальнейшего какой-либо алгоритмический Язык. Например, можно взять нечто наподобие "Бейсика", в котором все команды программы имеют метки (номера), а в качестве команд разрешены обычные арифметические операции, условный оператор (if ... then ... else ...) и оператор безусловного перехода на заданную метку (goto). Помимо этого, нам надо внести некую ясность насчёт процедур ввода-вывода.
Можно рассматривать программы, в которых никакой ввод не предусмотрен (процедуры вывода также можно не использовать). Такие программы я буду называть программами без параметров. В них мы, однако, предусматриваем специальную команду stop, выполнение которой останавливает процесс исполнения программы. В качестве важного примера программы без параметров мы рассмотрим такую, которая легко возникает из Примера 4. Она является весьма короткой, и её полный текст легко можно написать. Однако в этом нет необходимости, поэтому мы просто опишем, что эта программа должна делать.
Начиная со значения n=8, машина вычисляет значение f(n) и полагает n равным f(n). Далее она проверяет, равно ли n восьми. Если да, то программа переходит к команде stop. Если нет, то программа возвращается к команде, в которой предписано вычислить f(n). Для большей наглядности напишем всё-таки текст, считая, что функция f(n) у нас "вмонтирована" (её легко реализовать при помощи подпрограммы). Метки будут принимать значения 10, 20, 30. Итак:
10 n:=8
20 n:=f(n)
30 if n=8 then stop else goto 20
Что делает эта программа? Легко видеть, что она останавливается тогда и только тогда, когда процесс, описанный в Примере 4 (при n=8) зацикливается. В противном случае программа работает бесконечно. О чём это говорит? О том, что если бы мы располагали способом определить по тексту программы без параметров, останавливается она когда-либо или же работает бесконечно, то мы бы смогли легко ответить на вопрос из Примера 4. Это же можно сказать и про вопрос из Примера 3 (детали мы опустим). Итак, мы приходим к формулировке следующей проблемы, известной как проблема остановки. Дана программа без параметров. Требуется определить, останавливается ли эта программа за конечное число шагов или же работает бесконечно долго.
Фактически требуется определить "судьбу" исполнения написанной программы, то есть судьбу некоторого детерминированного процесса. Мы можем начать исполнение программы вручную, следуя инструкциям, или же можем заставить компьютер исполнять эту программу. Понятно, что если мы дождёмся остановки, то вопрос о "судьбе" нам станет известен. Но если программа работает очень долго, и у нас иссякает терпение, то мы не знаем, стоит ли прервать вычисления или надо подождать ещё немного.
Каждый, наверное, согласится с тем, что вопрос об остановке той или иной конкретной программы относится к области математики. Несколько менее очевидно, хотя и правдоподобно, что вопрос об остановке программы может быть сформулирован на языке теории чисел. В это легко поверить, так как программа работает с числами по неким жёстко заданным законам. Строгое доказательство того факта, что язык формальной арифметики достаточно богат для выражения подобных утверждений, на самом деле является весьма нетривиальным. Можно сказать, что это есть существенная часть доказательства теорем Гёделя. Однако для "общенаучного" подхода свойства отдельных формальных математических систем не столь важны; важнее то, что не существует "универсальной логической машины". Поэтому мы сейчас просто покажем, что никакая машина не может решать такую математическую задачу (на самом деле задачу из области арифметики) как проблема остановки. В таких случаях принято говорить, что проблема остановки алгоритмически неразрешима. Это утверждение (о существовании алгоритмически неразрешимых проблем) само по себе представляет большую ценность.
Прежде всего нам следует уточнить формулировку. Итак, что должна представлять собой машина (программа, алгоритм), претендующая на решение проблемы остановки? Нужно написать такую компьютерную программу (на любом приемлемом алгоритмическом языке), которая делала бы следующее. В программе должна быть предусмотрена команда ввода, и при этом на вход мы подаём текст той программы без параметров, которую мы хотим протестировать на предмет остановки. Наша гипотетическая Программа (будем далее именовать её с большой буквы) должна выдать нам ответ на вопрос: останавливается ли в будущем та программа без параметров, текст которой мы ввели? Если нет, то мы хотим получить значение 0 на "выходе"; если да, то мы хотим получить значение 1. Итак, на вход мы подаём файл (текст), а на выходе хотим получить 0 или 1. Чтобы не отягощать себя отдельной процедурой вывода, можно заранее ввести обозначение для переменной (например, s), которое после окончания работы Программы становится равно 0 или 1. Мы считаем, что Программа работает правильно, если для любой тестриуемой программы P без параметров мы получим в итоге s=1 в случае, если программе P суждено остановиться и s=0, если P по природе своей такова, что никогда не остановится.
Так что же значит, что проблема остановки алгоритмически неразрешима? Это значит, что ЛЮБАЯ программа, претендующая на то, чтобы стать Программой, то есть претендующая на решение проблемы остановки, обязательно ошибается. То есть найдётся опровергающий пример: такая программа P без параметров, о судьбе которой "кандидат в Программы" даёт заведомо неверный ответ.
Итак, ситуация следующая. Кто-то утверждает: я умею решать проблему остановки и готов предъявить соответствующую Программу. Что она делает? У неё есть один входной параметр -- это программа (точнее, её текст), который надо протестировать на предмет остановки. Составитель Программы рассчитывает на то, она способна пройти через все тесты. Мы же хотим это опровергнуть, то есть нам надо предъявить конкретный тест, который Программа не проходит. Тестом является подходящая программа P без параметров. Она либо останавливается, и тогда Программа говорит нам, что P работает бесконечно, либо P на самом деле работает бесконечно, но Программа свидетельствует об обратном.
Чтобы разработать опровергающий тест P, нам надо иметь в распоряжении уже написанную и предъявленную Программу (если бы тест был составлен заранее, то составитель Программы имел бы возможность под него специально подстроиться). Прежде чем описать принцип составления опровергающего теста, нам придётся немножко отвлечься и поговорить о нумерации текстов.
Каждая программа, написанная на нашем Языке, представляет собой текст, то есть конечную последовательность символов определённого алфавита. В нашем случае в алфавит входят строчные латинские буквы, цифры, символ пробела, знаки пунктуации и т.п. Все эти символы можно для начала упорядочить (например, в соответствии с их порядком следования в стандартной кодовой таблице). Теперь мы можем выписать все тексты, присваивая каждому тексту его порядковый номер. Сначала мы пишем в алфавитном порядке все тексты из одной буквы. Их имеется ровно M -- по числу символов нашего алфавита. Далее выписываем в алфавитном порядке все тексты из двух символов; последних имеется ровно M^2. Теперь настаёт черёд текстов из трёх символов (у нас только латинские буквы, так что ничего страшного :)), которых будет M^3 и так далее. В итоге мы получаем пронумерованный полный список всех текстов. Если бы наш алфавит состоял, к примеру, из трёх символов x, y, z, то нумерация текстов получилась бы такая:
1. x
2. y
3. z
4. xx
5. xy
6. xz
7. yx
и так далее. Ясно, что имеется простейший алгоритм, который по тексту определяет, какой текст будет следующим по списку. Тем самым, зная текст, легко найти его номер (выписывая все тексты по порядку, пока не наткнёмся на заданный). Также по данному номеру легко восстановить идущий под этим номером текст. Обе операции реализуются при помощи очень простых алгоритмических процедур (с вводом в виде текста и выводом в виде номера).
Теперь вспомним о том, что всякая программа, написанная на заданном алгоритмическом языке, представляет собой текст, удовлетворяющий некоторым чисто синтаксическим требованиям. Всякий, кто писал программы под "оболочками" вроде Turbo Basic, Turbo Pascal и др., знает, что в таких пакетах имеется встроенная проверка программ на синтаксическую правильность. Обычно люди допускают опечатки при написании текстов, и встроенная проверка помогает выявить и исправить синтаксические ошибки. Для написания программы, проверяющей синтаксис Языка, требуется лишь его явное описание. Такие описания имеются для всех используемых на практике алгоритмических языков. Написать такую программу -- работа не то чтобы очень сложная, но довольно кропотливая, требующая затрат времени. Тем не менее, вряд ли кто-то сомневается, что она может быть осуществлена. Поэтому мы далее будем считать, что в нашем распоряжении имеется готовый программный продукт, проверяющий любой заданный текст на предмет того, является ли последний синтаксически верно составленной программой на нашем Языке.
Выше мы рассматривали класс программ без входных параметров. Сейчас мы хотим сосредоточить внимание на довольно типичном классе программ, которые работают с одним входным параметром, являющимся натуральным числом. Такого рода программа может проверять число на предмет того, обладает ли оно каким-то свойством (например, является чётным, является простым, представимо в виде суммы кубов трёх целых чисел и т.д.). Мы можем дополнительно потребовалать, чтобы первой командой в такой программе была команда ввода параметра, записываемая, к примеру, в виде input(n), где n -- переменная, которой присваивается подаваемое на вход значение. Все программы только что описанного класса мы будем для удобства называть далее программами с одним входом.
Легко понять, что среди всех синтаксически правильно составленных программ очень просто выявить программы с одним входом (учитывая то, что мы сказали насчёт первой команды). Тем самым мы можем представить себе список всех текстов, о котором говорилось выше, а затем выделить в нём те тексты, которые являются программами с одним входом. Эти тексты будут встречаться в списке относительно редко, но их будет бесконечно много, и всем этим текстам можно присвоить новые номера в соответствии с порядком их следования. То есть можно сказать, что мы удаляем из списка текстов все те, которые не представляют собой программы с одним входом. Получается полный список программ с одним входом, и им даются новые номера по порядку. Далее, говоря о нумерации программ с одним входом, мы всегда будем иметь в виду не их (старые) номера, как номера текстов, а их новые номера. При этом каждая программа с одним входом получит свой индивидуальный номер, а каждому номеру соответствует какая-то из означенных программ. Более того, в силу сказанного выше, мы располагаем эффективными (алгоритмическими) процедурами восстановления текста программы с одним входом по её номеру (и наоборот).
Теперь пришло время создать некоторую вспомогательную программу A с одним входом. Опишем словесно процесс её построения. Сначала мы пишем команду input(n). Программа тем самым получит на вход некое натуральное число и присвоит его значение переменной n. Заметим, что после исполнения команды ввода, программа будет располагать конкретной записью введённого числа; нам будет удобно обозначить эту запись через t, имея в виду, что это текст. Далее при помощи имеющейся у нас процедуры мы находим ту программу с одним входом, которая имеет номер n. После чего мы располагаем в явном виде её текстом. Наша задача -- подать на вход этой программы в качестве параметра её номер. Для этого нужно в тексте программы заменить команду ввода, имеющую стандартный вид input(n), на команду n:=t, которая придаёт параметру нужное нам значение в явном виде. В итоге получится программа без параметров, которую мы обозначим через P. Эту программу можно подать на вход Программы, несостоятельность которой мы имеем намерение продемонстрировать. Мы располагаем текстом Программы, стало быть, имеем возможность включить её в состав той программы A, которую мы составляем. Это означает, что мы просто вписываем себе текст Программы, работающей со значением P, которое нам дано. (Маленькое замечание состоит в том, что при этом, возможно, потребуется как-то следить за изменением меток и согласованием используемых нами переменных, но это техническая тонкость.) Итак, представим себе, что наша программа A (которую мы ещё не дописали до конца) продолжает исполняться. В итоге Программа протестирует P на предмет остановки. Мы (составители программы A) понятия не имеем о том, останавливается программа P или нет в реальности (проблему остановки в общем случае мы не умеем решать). Но мы знаем, какое мнение на сей счёт высказала нам Программа. Напомним, что в ней имеется переменная s, принимающая значение 1 или 0 в соответствии с тем, останавливается ли P по мнению Программы. И вот теперь, располагая этим "мнением", т.е. значением переменной s, мы можем придать поведению нашей программы A противоположный характер. А именно: если s=0, то мы заставим программу A выполнить команду stop; если же s=1, то мы искусственно загоним программу в непрекращающийся цикл, то есть на некоторую метку L, которая соответствует команде goto L. В целом окончание программы будет выглядеть так:
(метка) if s=0 then stop else goto L
L goto L
Итак, мы описали способ построения программы A с одним входом. Каким свойством она обладает, согласно построению? Если на вход подать число n, то программа остановится в том и только в том случае, когда Программа считает, что не остановится программа с одним входом, имеющая номер n, при условии, что на её вход последней подан номер n. Теперь вспомним, что сама программа A, являясь программой с одним входом, имеет некоторый вполне конкретный номер N. Что будет, если его подать на вход программы A? Будет то же самое, что и в случае, если в программе A заменить команду ввода input(n) на оператор присваивания n:=N, где N -- конкретное число. То есть "судьба" программы A (в смысле "остановится" -- "не остановится") будет та же, что и программы T без параметров, которая получилась заменой команды ввода на оператор присваивания. Таким образом, имеем следующую цепочку рассуждений, в которой длинный оборот "тогда и только тогда, когда" для краткости заменён на "iff":
программа T останавливается iff программа A останавливается при вводе в неё числа N в качестве параметра iff Программа считает, что не остановится программа с одним входом, имеющая номер N, при условии, что на вход последней подан номер N.
Однако, при расшифровке того, что написано курсивом, мы сразу поймём, что речь идёт о программе A (ведь N -- это её индивидуальный номер), на вход которой подан номер N. Остановка такой программы равносильна остановке программы T, то есть окончательно мы имеем следующее:
программа T останавливается iff Программа считает, что T не останавливается.
Это как раз и означает, что Программа даёт неверный ответ на вопрос о поведении программы T. Тем самым составители Программы посрамлены, и алгоритмическая неразрешимость проблемы остановки доказана.
Итак, на данный момент мы знаем, что никакая компьютерная программа не способна верно решать все математические задачи (даже из довольно узкого класса таких задач). Из этого можно сделать вывод о невозможности создания "универсальной логической машины". Причём следует заметить, что мы не только уверены в этом, но знаем готовый рецепт, как опровергнуть любую из попыток представить проект подобного устройства на суд общественности. То есть доказательство является в определённом смысле "конструктивным" (далеко не все математические рассуждения таковы).
На самом деле, на этом можно было бы и закончить, так как те, кто интересуются общенаучным смыслом теорем Гёделя, могли бы вполне быть удовлетворены вышесказанным. Однако имеет смысл всё-таки показать, какова связь между наличием алгоритмически неразрешимых проблем и теоремами Гёделя. Я хочу продемонстрировать следующее: из существования алгоритмически неразрешимых проблем вытекает (первая) теорема Гёделя о неполноте. Это аргумент в пользу того, что мы на самом деле рассмотрели более (или, как минимум, не менее) сильное утверждение. Надо заметить, что нижеследующее рассуждение вовсе не нужно проводить на строго формальном уровне, так как речь идёт лишь о сравнительной силе двух утверждений. (То есть это не столько чисто математическое рассуждение, сколько попытка убедить читателя, что он "ничего не теряет".)
ПРОДОЛЖЕНИЕ СЛЕДУЕТ
Собственно о теоремах Гёделя речь тоже пойдёт, но во второй части текста.
Мыслители прошлого не раз задумывались над возможностью создания такой машины, которая, грубо говоря, давала бы ответы на все вопросы, интересующие человечество. Речь могла идти как о математических, так и о философских "истинах". Определённые успехи в области естествознания делали этот проект не столь уж фантастическим в глазах современников. Лейбниц мечтал о том времени, когда философские споры будут разрешаться посредством вычислений. Итак, в чём же может состоять сам проект? В том, что человечество, постигая мир, постепенно открывает для себя некий набор основных "истин" (наподобие аксиом геометрии), при помощи которых далее можно будет чисто логически доказать любое представляющее интерес новое "истинное" положение. Известна, например, попытка Спинозы предложить аксиоматический подход в области этики.
Итак, чего бы нам хотелось, если говорить о создании такой "универсальной логической машины"? Например, можно ставить вопрос о создании компьютерной программы, которая давала бы ответ на любой осмысленный вопрос в форме "да" или "нет". Уточнение того, что следует понимать под "осмысленностью", здесь не является первостепенной задачей, так как круг вопросов можно (хотя бы для начала) искусственно сузить. Мы не будем мучить предполагаемую машину вопрсами типа "что первично: материя или сознание" или "что было раньше: яйцо или курица". Уместно сосредоточиться на вопросах из области математики или даже арифметики (теории чисел), так как здесь не наблюдается значительных расхождений в понимании самих вопросов. Тем, кто считает, что арифметика -- очень простая наука, полезно будет ознакомиться с примерами задач (относящихся к свойствам натуральных чисел), которые не решены по сей день и считаются весьма сложными.
1) Рассмотрим натуральный ряд: 1, 2, 3, 4, 5, 6, 7, 8, ... и так далее. Про каждое из чисел можно спросить, сколько у него имеется делителей (среди натуральных чисел). При этом сразу станет ясно, что каждое из чисел ряда 2, 3, 5, 7, 11, 13, 17, 19, 23, ... имеет ровно два делителя -- единицу и само себя. Такие числа, как многим должно быть известно, называются простыми. Ряд простых чисел бесконечен, что известно со времён Евклида. Обратим внимание на то, что некоторые простые числа отличаются ровно на 2 -- таковы 11 и 13, 17 и 19, 29 и 31, 41 и 43. Такие пары простых чисел принято называть близнецами. Никто не знает, конечно ли количество пар-близнецов. В ответе на этот вопрос состоит хорошо известная старая проблема.
2) Вот пример второй знаменитой проблемы, относящейся к простым числам -- это проблема Гольдбаха -- Эйлера. Формулируется она так: всякое ли чётное число, начиная с 4, можно представить в виде суммы двух простых? Мы легко видим, что 4=2+2, 6=3+3, 8=3+5, 10=3+7=5+5 (т.е. для одного числа может быть несколько разных представлений) и так далее. Но никто не знает, распространяется ли эта закономерность на все дальнейшие чётные числа.
3) Вот менее известный, но эффектный пример. Вопрос таков: какие натуральные числа можно представить в виде суммы кубов трёх целых чисел? То есть при каких натуральных a уравнение x^3+y^3+z^3=a имеет хотя бы одно решение в целых числах (здесь x,y,z могут принимать не только натуральные, но и отрицательные значения, а также быть равными нулю). Сравнительно несложно доказать, что при a=4, 5, 13, 14, 22, 23, ... -- это все числа, дающие при делении на 9 в остатке 4 или 5 -- уравнение решений не имеет. С другой стороны, не известно, имеет ли решение уравнение для всех остальных значений a. Некоторое время был открытым вопрос о числе a=30, и даже в ряде сборников олимпиадных задач по математике встречалось упоминание на сей счёт. Однако сравнительно недавно было выяснено, что уравнение x^3+y^3+z^3=30 обладает решениями. Вот конкретный пример тройки чисел, удовлетворяющих уравнению: x=2220422932, y=-2218888517, z=-283059965. Желающие могут подставить и проверить :)
Наименьшим числом, для которого вопрос пока открыт, является a=33. Интересующиеся могут найти дополнительную информацию здесь:
http://www.asahi-net.or.jp/~kc2h-msm/mathland/math04/cube01.htm
Обращает на себя внимание тот факт, что многие решения найдены совсем недавно.
4) Следующий пример мне очень нравится с давних пор. Каждому натуральному числу n сопоставим число, обозначаемое через f(n), по такому правилу. Если n делится на 3, то полагаем f(n)=2*(n/3). В противном случае рассмотрим дробь (4*n)/3. Здесь f(n) есть округление этой дроби до ближайшего целого. Во втором случае надо просто заменить число 4*n, не делящееся на 3, на одно из соседних, которое делится на три. Например, надо найти f(10). Поскольку 10 на 3 не делится, рассмотрим дробь 40/3. В числителе заменяем 40 на 39 и получаем f(10)=13.
Возьмём какое-то число n и начнём выписывать последовательность n, f(n), f(f(n)), ... -- каждое следующее число получается из предыдущего применением функции f. Что может произойти с этой последовательностью? Возможны два случая. Либо числа возникают всё новые и новые (и тогда последовательность "уходит в бесконечность"), либо где-то произойдёт повторение числа, уже встречавшегося ранее. В последнем случае последовательность "зациклится". Например, если мы начнём с n=1, то получим последовательность из одних единиц. При n=2 мы получим последовательность из чередующихся двоек и троек. Чуть более интересен случай n=4. Здесь возникнет последовательность 4, 5, 7, 9, 6, 4, 5, 7, 9, 6, ... -- здесь периодически повторяется группа из пяти чисел. Наименьшее число, которое пока что отсутствовало -- это n=8. Вот что мы получим в этом случае:
8, 11, 15, 10, 13, 17, 23, 31, 41, 55, 73, 97, 129, 86, 115, 153, 102, 68, 91, 121, 161, 215, 287, 383, 511, 681, 454, 605, 807, 538, 717, 478, 637, 849, 566, 755, 1007, 1343, 1791, 1194, 796, 1061, 1415, 1887, 1258, 1677, 1118, 1491, 994, 1325, 1767, 1178, 1571, 2095, 2793, 1862, 2483, 3311, 4415, 5887, 7849, 10465, 13953, 9302, 12403, ... и так далее.
Какова у этой последовательности дальнейшая "судьба"? (Хороший вопрос для "гадалок", "магов" и прочих представителей мира "экстрасенсорики".) Легко понять, что это процесс полностью детерминированный: его поведение однозначно задаётся выбранным начальным значением. Более того, процесс этот может быть однозначно продолжен не только в будущее, но и в прошлое (это несложное упражнение). Например, перед числом 8 может стоять только 12, перед ним -- 18, перед ним -- 27 и так далее. Вот как выглядит "недалёкое прошлое" процесса перед числом 8:
..., 962, 1283, 1711, 2281, 3041, 4055, 5407, 7209, 4806, 3204, 2136, 1424, 1899, 1266, 844, 1125, 750, 500, 667, 889, 1185, 790, 1053, 702, 468, 312, 208, 277, 369, 246, 164, 219, 146, 195, 130, 173, 231, 154, 205, 273, 182, 243, 162, 108, 72, 48, 32, 43, 57, 38, 51, 34, 45, 30, 20, 27, 18, 12, 8
Весь процесс можно себе представить как некую "траекторию", пролегающую через отметку 8. Эта траектория может быть либо "замкнутой", либо нет. Как обстоит дело в реальности -- никто не знает. На современных компьютерах можно пронаблюдать судьбу процесса на много ходов вперёд, но при этом "зацикливания", т.е. возврата к началу, не наблюдается. Однако из этого ничего не следует. Кто знает, а вдруг ещё немного терпения, и мы в ходе вычислений обнаружим наличие цикла? Для иллюстрации полезно убедиться в том, что циклы на самом деле могут возникать. Скажем, если взять n=44, то даже вручную можно установить, что процесс является периодическим (повторение наступает через 12 шагов).
Итак, мы привели несколько примеров трудных вопросов из области арифметики, чтобы показать, что таковые бывают. Поэтому построение пусть не универсальной, но хотя бы "универсально-арифметической" машины представляло бы интерес. Однако математики сумели ДОКАЗАТЬ, что даже такой машины В ПРИНЦИПЕ НЕ СУЩЕСТВУЕТ. Тем самым вопрос об "универсальной логической машине" автоматически снимается с повестки дня. Разумеется, попытки создавать "машины", решающие более узкие классы задач, не лишены смысла. Также из сказанного не следует, что какая-либо из задач, рассмотренных выше, "неразрешима" в каком-то принципиальном смысле. Однако "вся арифметика" никакой "машине" не по зубам. Об этом пойдёт речь ниже.
Итак, я ставлю себе цель разъяснить, почему это так, а также показать связь между несуществованием означенной "машины" и теоремами Гёделя. Прежде всего надо понять, чего же именно не существует. Нам хотелось бы иметь компьютерную программу (алгоритм), при помощи которой мы могли бы получить ответ на любой интересующий нас вопрос из области арифметики. Вопросы должны задаваться в форме, понятной для машины, то есть на определённом символическом языке. Для этой цели вполне подошёл бы язык формул математической логики, использующих логические символы (логические связки наподобие "и", "или", "не", "влечёт", а также логические кванторы -- "для всех" и "существует"). Давно известно, что этих фрагментов естественного языка вместе с символами арифметических операций достаточно для того, чтобы любой арифметический вопрос смочь выразить на языке символов. Машина, получив вопрос, должна после некоторых вычислений (возможно, долгих) выдать нам правильный ответ на поставленный вопрос в виде "да" или "нет". Заметим, что мы облегчаем работу машине в том плане, что не рассматриваем никакого другого формата ответа. Скажем, мы можем спросить, "конечно ли количество пар-близнецов", "зацикливается ли процесс из примера 4" (после перевода этих вопросов на символический язык). Однако мы не можем задать вопрос из примера 3 "какие числа могут быть представлены...". Зато мы имеем право спросить, может ли число 33 быть представлено в виде суммы кубов трёх целых чисел. Дело в том, что уже с таким кругом вопросов ("да" -- "нет") машина не справится.
Здесь полезно заметить, что "машина" должна уметь давать ответ на ВСЕ описанные выше вопросы из области арифметики. Если мы сосредоточимся на каком-то одном вопросе, то можно сконструировать две простейшие машины, одна из которых всегда говорит "да", а вторая всегда говорит "нет". Ясно, что ровно одна из них ответит на любой конкретный вопрос правильно. Поэтому мы говорим о машинах (или программах, алгоритмах), при помощи которых можно решать целый класс задач; в таких случаях принято говорить о решении некой массовой проблемы.
Для написания компьютерной программы требуется алгоритмический язык. В качестве него можно взять практически любой из уже существующих или придумать какой-то свой. Можно пользоваться упрощённым вариантом одного из уже имеющихся языков. Конечный ответ от этого не зависит. Мы, разумеется, считаем, что ресурсы памяти компьютера потенциально бесконечны -- даже при этом условии требуемую машину построить не удастся. Итак, сейчас надо определиться и зафиксировать для дальнейшего какой-либо алгоритмический Язык. Например, можно взять нечто наподобие "Бейсика", в котором все команды программы имеют метки (номера), а в качестве команд разрешены обычные арифметические операции, условный оператор (if ... then ... else ...) и оператор безусловного перехода на заданную метку (goto). Помимо этого, нам надо внести некую ясность насчёт процедур ввода-вывода.
Можно рассматривать программы, в которых никакой ввод не предусмотрен (процедуры вывода также можно не использовать). Такие программы я буду называть программами без параметров. В них мы, однако, предусматриваем специальную команду stop, выполнение которой останавливает процесс исполнения программы. В качестве важного примера программы без параметров мы рассмотрим такую, которая легко возникает из Примера 4. Она является весьма короткой, и её полный текст легко можно написать. Однако в этом нет необходимости, поэтому мы просто опишем, что эта программа должна делать.
Начиная со значения n=8, машина вычисляет значение f(n) и полагает n равным f(n). Далее она проверяет, равно ли n восьми. Если да, то программа переходит к команде stop. Если нет, то программа возвращается к команде, в которой предписано вычислить f(n). Для большей наглядности напишем всё-таки текст, считая, что функция f(n) у нас "вмонтирована" (её легко реализовать при помощи подпрограммы). Метки будут принимать значения 10, 20, 30. Итак:
10 n:=8
20 n:=f(n)
30 if n=8 then stop else goto 20
Что делает эта программа? Легко видеть, что она останавливается тогда и только тогда, когда процесс, описанный в Примере 4 (при n=8) зацикливается. В противном случае программа работает бесконечно. О чём это говорит? О том, что если бы мы располагали способом определить по тексту программы без параметров, останавливается она когда-либо или же работает бесконечно, то мы бы смогли легко ответить на вопрос из Примера 4. Это же можно сказать и про вопрос из Примера 3 (детали мы опустим). Итак, мы приходим к формулировке следующей проблемы, известной как проблема остановки. Дана программа без параметров. Требуется определить, останавливается ли эта программа за конечное число шагов или же работает бесконечно долго.
Фактически требуется определить "судьбу" исполнения написанной программы, то есть судьбу некоторого детерминированного процесса. Мы можем начать исполнение программы вручную, следуя инструкциям, или же можем заставить компьютер исполнять эту программу. Понятно, что если мы дождёмся остановки, то вопрос о "судьбе" нам станет известен. Но если программа работает очень долго, и у нас иссякает терпение, то мы не знаем, стоит ли прервать вычисления или надо подождать ещё немного.
Каждый, наверное, согласится с тем, что вопрос об остановке той или иной конкретной программы относится к области математики. Несколько менее очевидно, хотя и правдоподобно, что вопрос об остановке программы может быть сформулирован на языке теории чисел. В это легко поверить, так как программа работает с числами по неким жёстко заданным законам. Строгое доказательство того факта, что язык формальной арифметики достаточно богат для выражения подобных утверждений, на самом деле является весьма нетривиальным. Можно сказать, что это есть существенная часть доказательства теорем Гёделя. Однако для "общенаучного" подхода свойства отдельных формальных математических систем не столь важны; важнее то, что не существует "универсальной логической машины". Поэтому мы сейчас просто покажем, что никакая машина не может решать такую математическую задачу (на самом деле задачу из области арифметики) как проблема остановки. В таких случаях принято говорить, что проблема остановки алгоритмически неразрешима. Это утверждение (о существовании алгоритмически неразрешимых проблем) само по себе представляет большую ценность.
Прежде всего нам следует уточнить формулировку. Итак, что должна представлять собой машина (программа, алгоритм), претендующая на решение проблемы остановки? Нужно написать такую компьютерную программу (на любом приемлемом алгоритмическом языке), которая делала бы следующее. В программе должна быть предусмотрена команда ввода, и при этом на вход мы подаём текст той программы без параметров, которую мы хотим протестировать на предмет остановки. Наша гипотетическая Программа (будем далее именовать её с большой буквы) должна выдать нам ответ на вопрос: останавливается ли в будущем та программа без параметров, текст которой мы ввели? Если нет, то мы хотим получить значение 0 на "выходе"; если да, то мы хотим получить значение 1. Итак, на вход мы подаём файл (текст), а на выходе хотим получить 0 или 1. Чтобы не отягощать себя отдельной процедурой вывода, можно заранее ввести обозначение для переменной (например, s), которое после окончания работы Программы становится равно 0 или 1. Мы считаем, что Программа работает правильно, если для любой тестриуемой программы P без параметров мы получим в итоге s=1 в случае, если программе P суждено остановиться и s=0, если P по природе своей такова, что никогда не остановится.
Так что же значит, что проблема остановки алгоритмически неразрешима? Это значит, что ЛЮБАЯ программа, претендующая на то, чтобы стать Программой, то есть претендующая на решение проблемы остановки, обязательно ошибается. То есть найдётся опровергающий пример: такая программа P без параметров, о судьбе которой "кандидат в Программы" даёт заведомо неверный ответ.
Итак, ситуация следующая. Кто-то утверждает: я умею решать проблему остановки и готов предъявить соответствующую Программу. Что она делает? У неё есть один входной параметр -- это программа (точнее, её текст), который надо протестировать на предмет остановки. Составитель Программы рассчитывает на то, она способна пройти через все тесты. Мы же хотим это опровергнуть, то есть нам надо предъявить конкретный тест, который Программа не проходит. Тестом является подходящая программа P без параметров. Она либо останавливается, и тогда Программа говорит нам, что P работает бесконечно, либо P на самом деле работает бесконечно, но Программа свидетельствует об обратном.
Чтобы разработать опровергающий тест P, нам надо иметь в распоряжении уже написанную и предъявленную Программу (если бы тест был составлен заранее, то составитель Программы имел бы возможность под него специально подстроиться). Прежде чем описать принцип составления опровергающего теста, нам придётся немножко отвлечься и поговорить о нумерации текстов.
Каждая программа, написанная на нашем Языке, представляет собой текст, то есть конечную последовательность символов определённого алфавита. В нашем случае в алфавит входят строчные латинские буквы, цифры, символ пробела, знаки пунктуации и т.п. Все эти символы можно для начала упорядочить (например, в соответствии с их порядком следования в стандартной кодовой таблице). Теперь мы можем выписать все тексты, присваивая каждому тексту его порядковый номер. Сначала мы пишем в алфавитном порядке все тексты из одной буквы. Их имеется ровно M -- по числу символов нашего алфавита. Далее выписываем в алфавитном порядке все тексты из двух символов; последних имеется ровно M^2. Теперь настаёт черёд текстов из трёх символов (у нас только латинские буквы, так что ничего страшного :)), которых будет M^3 и так далее. В итоге мы получаем пронумерованный полный список всех текстов. Если бы наш алфавит состоял, к примеру, из трёх символов x, y, z, то нумерация текстов получилась бы такая:
1. x
2. y
3. z
4. xx
5. xy
6. xz
7. yx
и так далее. Ясно, что имеется простейший алгоритм, который по тексту определяет, какой текст будет следующим по списку. Тем самым, зная текст, легко найти его номер (выписывая все тексты по порядку, пока не наткнёмся на заданный). Также по данному номеру легко восстановить идущий под этим номером текст. Обе операции реализуются при помощи очень простых алгоритмических процедур (с вводом в виде текста и выводом в виде номера).
Теперь вспомним о том, что всякая программа, написанная на заданном алгоритмическом языке, представляет собой текст, удовлетворяющий некоторым чисто синтаксическим требованиям. Всякий, кто писал программы под "оболочками" вроде Turbo Basic, Turbo Pascal и др., знает, что в таких пакетах имеется встроенная проверка программ на синтаксическую правильность. Обычно люди допускают опечатки при написании текстов, и встроенная проверка помогает выявить и исправить синтаксические ошибки. Для написания программы, проверяющей синтаксис Языка, требуется лишь его явное описание. Такие описания имеются для всех используемых на практике алгоритмических языков. Написать такую программу -- работа не то чтобы очень сложная, но довольно кропотливая, требующая затрат времени. Тем не менее, вряд ли кто-то сомневается, что она может быть осуществлена. Поэтому мы далее будем считать, что в нашем распоряжении имеется готовый программный продукт, проверяющий любой заданный текст на предмет того, является ли последний синтаксически верно составленной программой на нашем Языке.
Выше мы рассматривали класс программ без входных параметров. Сейчас мы хотим сосредоточить внимание на довольно типичном классе программ, которые работают с одним входным параметром, являющимся натуральным числом. Такого рода программа может проверять число на предмет того, обладает ли оно каким-то свойством (например, является чётным, является простым, представимо в виде суммы кубов трёх целых чисел и т.д.). Мы можем дополнительно потребовалать, чтобы первой командой в такой программе была команда ввода параметра, записываемая, к примеру, в виде input(n), где n -- переменная, которой присваивается подаваемое на вход значение. Все программы только что описанного класса мы будем для удобства называть далее программами с одним входом.
Легко понять, что среди всех синтаксически правильно составленных программ очень просто выявить программы с одним входом (учитывая то, что мы сказали насчёт первой команды). Тем самым мы можем представить себе список всех текстов, о котором говорилось выше, а затем выделить в нём те тексты, которые являются программами с одним входом. Эти тексты будут встречаться в списке относительно редко, но их будет бесконечно много, и всем этим текстам можно присвоить новые номера в соответствии с порядком их следования. То есть можно сказать, что мы удаляем из списка текстов все те, которые не представляют собой программы с одним входом. Получается полный список программ с одним входом, и им даются новые номера по порядку. Далее, говоря о нумерации программ с одним входом, мы всегда будем иметь в виду не их (старые) номера, как номера текстов, а их новые номера. При этом каждая программа с одним входом получит свой индивидуальный номер, а каждому номеру соответствует какая-то из означенных программ. Более того, в силу сказанного выше, мы располагаем эффективными (алгоритмическими) процедурами восстановления текста программы с одним входом по её номеру (и наоборот).
Теперь пришло время создать некоторую вспомогательную программу A с одним входом. Опишем словесно процесс её построения. Сначала мы пишем команду input(n). Программа тем самым получит на вход некое натуральное число и присвоит его значение переменной n. Заметим, что после исполнения команды ввода, программа будет располагать конкретной записью введённого числа; нам будет удобно обозначить эту запись через t, имея в виду, что это текст. Далее при помощи имеющейся у нас процедуры мы находим ту программу с одним входом, которая имеет номер n. После чего мы располагаем в явном виде её текстом. Наша задача -- подать на вход этой программы в качестве параметра её номер. Для этого нужно в тексте программы заменить команду ввода, имеющую стандартный вид input(n), на команду n:=t, которая придаёт параметру нужное нам значение в явном виде. В итоге получится программа без параметров, которую мы обозначим через P. Эту программу можно подать на вход Программы, несостоятельность которой мы имеем намерение продемонстрировать. Мы располагаем текстом Программы, стало быть, имеем возможность включить её в состав той программы A, которую мы составляем. Это означает, что мы просто вписываем себе текст Программы, работающей со значением P, которое нам дано. (Маленькое замечание состоит в том, что при этом, возможно, потребуется как-то следить за изменением меток и согласованием используемых нами переменных, но это техническая тонкость.) Итак, представим себе, что наша программа A (которую мы ещё не дописали до конца) продолжает исполняться. В итоге Программа протестирует P на предмет остановки. Мы (составители программы A) понятия не имеем о том, останавливается программа P или нет в реальности (проблему остановки в общем случае мы не умеем решать). Но мы знаем, какое мнение на сей счёт высказала нам Программа. Напомним, что в ней имеется переменная s, принимающая значение 1 или 0 в соответствии с тем, останавливается ли P по мнению Программы. И вот теперь, располагая этим "мнением", т.е. значением переменной s, мы можем придать поведению нашей программы A противоположный характер. А именно: если s=0, то мы заставим программу A выполнить команду stop; если же s=1, то мы искусственно загоним программу в непрекращающийся цикл, то есть на некоторую метку L, которая соответствует команде goto L. В целом окончание программы будет выглядеть так:
(метка) if s=0 then stop else goto L
L goto L
Итак, мы описали способ построения программы A с одним входом. Каким свойством она обладает, согласно построению? Если на вход подать число n, то программа остановится в том и только в том случае, когда Программа считает, что не остановится программа с одним входом, имеющая номер n, при условии, что на её вход последней подан номер n. Теперь вспомним, что сама программа A, являясь программой с одним входом, имеет некоторый вполне конкретный номер N. Что будет, если его подать на вход программы A? Будет то же самое, что и в случае, если в программе A заменить команду ввода input(n) на оператор присваивания n:=N, где N -- конкретное число. То есть "судьба" программы A (в смысле "остановится" -- "не остановится") будет та же, что и программы T без параметров, которая получилась заменой команды ввода на оператор присваивания. Таким образом, имеем следующую цепочку рассуждений, в которой длинный оборот "тогда и только тогда, когда" для краткости заменён на "iff":
программа T останавливается iff программа A останавливается при вводе в неё числа N в качестве параметра iff Программа считает, что не остановится программа с одним входом, имеющая номер N, при условии, что на вход последней подан номер N.
Однако, при расшифровке того, что написано курсивом, мы сразу поймём, что речь идёт о программе A (ведь N -- это её индивидуальный номер), на вход которой подан номер N. Остановка такой программы равносильна остановке программы T, то есть окончательно мы имеем следующее:
программа T останавливается iff Программа считает, что T не останавливается.
Это как раз и означает, что Программа даёт неверный ответ на вопрос о поведении программы T. Тем самым составители Программы посрамлены, и алгоритмическая неразрешимость проблемы остановки доказана.
Итак, на данный момент мы знаем, что никакая компьютерная программа не способна верно решать все математические задачи (даже из довольно узкого класса таких задач). Из этого можно сделать вывод о невозможности создания "универсальной логической машины". Причём следует заметить, что мы не только уверены в этом, но знаем готовый рецепт, как опровергнуть любую из попыток представить проект подобного устройства на суд общественности. То есть доказательство является в определённом смысле "конструктивным" (далеко не все математические рассуждения таковы).
На самом деле, на этом можно было бы и закончить, так как те, кто интересуются общенаучным смыслом теорем Гёделя, могли бы вполне быть удовлетворены вышесказанным. Однако имеет смысл всё-таки показать, какова связь между наличием алгоритмически неразрешимых проблем и теоремами Гёделя. Я хочу продемонстрировать следующее: из существования алгоритмически неразрешимых проблем вытекает (первая) теорема Гёделя о неполноте. Это аргумент в пользу того, что мы на самом деле рассмотрели более (или, как минимум, не менее) сильное утверждение. Надо заметить, что нижеследующее рассуждение вовсе не нужно проводить на строго формальном уровне, так как речь идёт лишь о сравнительной силе двух утверждений. (То есть это не столько чисто математическое рассуждение, сколько попытка убедить читателя, что он "ничего не теряет".)
ПРОДОЛЖЕНИЕ СЛЕДУЕТ