Теперь там, где мы не обнаруживаем 0, мы производим все вычисления, как мы это делали на первом шаге, и получаем следующий фрагмент таблицы:
| Вход | 0 | 1 | 2 | 3 |
| Номер матрицы | 0 | 0 | 0 | 0 | 0 |
| 1 | 3 | 0 | 4 | 1 |
| 2 | 1 | 1 | 1 | 1 |
| 3 | 0 | 1 | 0 | 2 |
Поскольку исходная таблица содержит все возможные вычислимые числа, эта таблица тоже содержит все возможные вычислимые числа: здесь может быть много повторений, но это делу не мешает.
Теперь перейдем к финалу. Давайте возьмем числа на диагонали (они выделены жирным шрифтом) и изменим их, прибавляя 1 (что похоже на доказательство Кантора). Мы получаем последовательность вида 1123…. Это вычислимое число (поскольку последовательность шагов, основанная на th и машине Тьюринга, действует в каждом предполагаемом случае), поэтому машина, которая производит это число, уже должна присутствовать где-то в таблице. Однако ее нет: она отличается от первого ряда (поскольку мы заставили первую цифру измениться), она отличается от второго ряда (поскольку мы заставили вторую цифру измениться), и так далее, для всех рядов в таблице. То есть, с одной стороны, ряд 1123… должен быть представлен, но, с другой стороны, его нет. Это противоречие, поэтому предположение о существовании «остановочной машины» th, которое мы использовали, должно быть ложным. Мы доказали (и это подтверждено более строгим и авторитетным доказательством Тьюринга), что не существует ни одной общей универсальной алгоритмической процедуры, которую можно использовать, чтобы судить, придут ли к концу данные вычисления или нет. Это влечет, в свою очередь, то, что не может существовать никакого общего алгоритма для решения математических задач, и поэтому Entscheidungsproblem не имеет решения.
Теперь я перехожу к высшей точке этой главы, к тому, что называют самым красивым достижением логики двадцатого века, к теореме Гёделя. Австрийский логик Курт Гёдель (1906- 1978) родился в Брюнне, Австро-Венгрия (ныне Брно, Республика Чехия), где работал Грегор Мендель, и учился в Венском университете. Хотя он и не был евреем (вопреки утверждению Бертрана Рассела), Гёдель не смог терпимо относиться к нацистским репрессиям и в 1934 г. поехал в США, в 1940 г. эмигрировал туда насовсем и провел оставшуюся часть жизни в Принстоне, где он и Эйнштейн стали большими друзьями. Конечно, в свои последние годы Гёдель внес существенный вклад и в общую теорию относительности, когда обнаружил неожиданное решение уравнений Эйнштейна, позволяющее времени течь в прошлое. По своему облику и образу жизни Гёдель не был человеком, которого можно было считать вполне приемлемым в обществе. Возвратись в Австрию после своей первой поездки в США, он женился на разведенной танцовщице и увез ее в Принстон, где ее не могли хорошо принять из-за преобладавшего в то время снобизма. К концу жизни у него развились классические признаки депрессии и паранойи: он был убежден, что является жертвой тайного общества убийц, что в конце концов привело его к отказу от еды и к ношению лыжной маски, чтобы избежать заражения во время прогулок в опасной и сильно загрязненной, как он считал, атмосфере Принстона. Он скончался, веся лишь 30 кг, от «недоедания и истощения» (вызванных отказом от пищи), явившихся, как гласит заключение о смерти, результатом «душевного расстройства».
Существуют несколько теорем, связанных с именем Гёделя. Здесь мы сосредоточимся на теореме, опубликованной в 1931 г. в статье Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme (О формальной неразрешимости предложений в Principia Mathematica и связанных с ней системах). В этой статье он показал, что в любой системе математических аксиом существуют метаматематические предложения, которые нельзя ни доказать, ни опровергнуть посредством формального вывода, основанного на аксиомах системы.
Это мы и сделаем. Математика представляет собой последовательность предложений, таких как 1 + 1 = 2, и «это является доказательством данного предложения»; первое предложение является математическим, в смысле Гильберта, а второе метаматематическим. Давайте предположим, что мы можем записать все предложения, которые можно вывести из фундаментальных аксиом (например, из аксиом Пеано или более разработанной системы, основанной на усовершенствованной теории типов, которой пользовались Рассел и Уайтхед). Это даст нам предложения p0, p1, p2, … и так далее. Как мы решим пронумеровать предложения, не имеет значения, но несколько изложенных ниже аргументов дадут вам ощутить аромат того, как действовал Гёдель.
В формулировке арифметики, подобной формулировке Пеано, имеется лишь небольшое число символов.
