• Так что же такое теорема Гёделя? В 1930 году на конференции в Кенигсберге блестящий молодой математик Курт Гёдель произвел немалое впечатление на ведущих математиков и логиков со всего мира, представив их вниманию теорему, которая впоследствии получила его имя. Ее довольно быстро признали в качестве фундаментального вклада в основы математики — быть может, наиболее фундаментального из всех возможных, — я же, в свою очередь, утверждаю, что своей теоремой Гёдель также положил начало важнейшему этапу развития философии разума.

Среди положений, которые со всей неоспоримостью доказал Гёдель, имеется следующее: нельзя создать такую формальную систему логически обоснованных математических правил доказательства, которой было бы достаточно, хотя бы в принципе, для доказательства всех истинных теорем элементарной арифметики. Уже и это само по себе в высшей степени удивительно, однако это еще не все. Многое говорит за то, что результаты Гёделя демонстрируют нечто большее, — а именно, доказывают, что способность человека к пониманию и постижению сути вещей невозможно свести к какому бы то ни было набору вычислительных правил. Иными словами, нельзя создать такую систему правил, которая оказалась бы достаточной для доказательства даже тех арифметических положений, истинность которых, в принципе, доступна для человека с его интуицией и способностью к пониманию, а это означает, что человеческие интуицию и понимание невозможно свести к какому бы то ни было набору правил. Последующие мои рассуждения отчасти имеют целью убедить читателя в том, что вышеприведенное утверждение действительно следует из теоремы Гёделя; более того, именно на теореме Гёделя основывается мое доказательство неизбежности наличия в человеческом мышлении составляющей, которую никогда не удастся воспроизвести с помощью компьютера (в том смысле, который мы вкладываем в этот термин сегодня).

Думаю, нет необходимости давать в рамках основного доказательства определение «формальной системы» (если такая необходимость все же есть, то см. §2.7). Вместо этого я воспользуюсь фундаментальным вкладом Тьюринга, который приблизительно в 1936 году описал класс процессов, которые мы сейчас называем «вычислениями» или «алгоритмами» (аналогичные результаты были получены независимо от Тьюринга некоторыми другими математиками, среди которых следует, в первую очередь, упомянуть Черча и Поста). Такие процессы эффективно эквивалентны процедурам, реализуемым в рамках любой математической формальной системы, поэтому для нас не имеет особого значения, что именно понимается под термином «формальная система», коль скоро мы обладаем достаточно ясным представлением о том, что обозначают термины «вычисление» или «алгоритм». Впрочем и для составления такого представления математически строгое определение нам не понадобится.

Те из вас, кто читал мою предыдущую книгу «Новый разум короля» (см. НРК, глава 2), возможно, припомнят, что алгоритм там определяется как процедура, которую способна выполнить машина Тьюринга, или, если угодно, математически идеализированная вычислительная машина. Такая машина функционирует в пошаговом режиме, причем каждый ее шаг полностью задается нанесенной на рабочую «ленту» меткой, которую (метку) машина «считывает» в соответствующий момент времени, и «внутренним состоянием» машины (дискретно определенным) на этот момент. Количество различных разрешенных внутренних состояний конечно, общее число меток на ленте также должно быть конечным, хотя сама лента по длине не ограничена. Машина начинает работу с какого-то определенного состояния, которое мы обозначим, например, нулем «0», команды же подаются на ленте в виде, скажем, двоичного числа (т.е. последовательности нулей «0» и единиц «1»). Далее машина начинает считывать эти команды, передвигая ленту (либо, что то же самое, перемещаясь вдоль ленты) некоторым определенным образом, согласно встроенным пошаговым инструкциям, при этом действие машины на каждом этапе работы определяется ее внутренним состоянием и конкретным символом, считываемым на данном этапе с ленты. Руководствуясь все теми же встроенными инструкциями, машина может стирать имеющиеся метки или ставить новые. В таком духе машина продолжает работать до тех пор, пока не достигнет особой команды «STOP», — именно в этот момент (и никак не раньше) машина прекращает работу, а мы можем увидеть на ленте ответ на выполнявшееся вычисление. Вот и все, можно задавать машине новую задачу.

Можно представить себе некую особую машину Тьюринга, которая способна имитировать действие любой возможной машины Тьюринга. Такие машины Тьюринга называют универсальными. Иными словами, любая отдельно взятая универсальная машина Тьюринга оказывается в состоянии выполнить любое вычисление (или алгоритм), какое нам только может прийти в голову. Хотя внутреннее устройство современного компьютера весьма отличается от устройства описанной выше конструкции (а его внутренняя «рабочая область», пусть и очень велика, все же не бесконечна, в отличие от идеализированной ленты машины Тьюринга), все современные универсальные компьютеры представляют собой, в сущности, универсальные машины Тьюринга.

2.2. Вычисления

В этом разделе мы поговорим о вычислениях. Под вычислением (или алгоритмом) я подразумеваю действие некоторой машины Тьюринга, или, иными словами, действие компьютера, задаваемое той или иной компьютерной программой. Не следует забывать и о том, что понятие вычисления включает в себя не только выполнение обычных арифметических действий — таких, например, как сложение или умножение чисел, — но и некоторые другие процессы. Так, частью вычислительной процедуры могут стать и вполне определенные логические операции. В качестве примера вычисления можно рассмотреть следующую задачу:

(А) Найти число, не являющееся суммой квадратов трех чисел.

Под «числом» в данном случае я подразумеваю «натуральное число», т.е. число из ряда

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ….

Под квадратом числа понимается результат умножения натурального числа на само себя, т.е. число из ряда

0, 1, 4, 9, 16, 25, 36, …;

представленные в этом ряду числа получены следующим образом:

0 × 0 = 0², 1 × 1 = 1², 2 × 2 = 2², 3 × 3 = 3², 4 × 4 = 4², 5 × 5 = 5², 6 × 6 = 6², ….

Такие числа называются «квадратами», поскольку их можно представить в виде квадратных матриц (пустой матрицей в начале строки обозначен 0):

С учетом вышесказанного решение задачи (А) может происходить следующим образом. Мы поочередно проверяем каждое натуральное число, начиная с 0, на предмет того, не является ли оно суммой трех квадратов. При этом, разумеется, рассматриваются только те квадраты, величина которых не превышает самого числа. Таким образом, для каждого натурального числа необходимо проверить некоторое конечное количество квадратов. Отыскав тройку квадратов, составляющих в сумме данное число, переходим к следующему натуральному числу и снова ищем среди квадратов (не превышающих по величине рассматриваемое число) такие три, которые дают в сумме это самое число. Вычисление завершается лишь тогда, когда мы находим натуральное число, которое невозможно получить путем сложения любых трех квадратов. Попробуем применить описанную процедуру на практике и начнем наше вычисление с нуля. Нуль равен 0² + 0² + 0², что, безусловно, является суммой трех квадратов. Далее рассматриваем единицу и находим, что она не равна 0² + 0² + 0², однако равна 0² + 0² + 1². Переходим к числу 2 и выясняем, что оно не равно ни 0² + 0² + 0², ни 0² + 0² + 1², но равно 0² + 1² + 1². Затем следует число 3 и сумма 3 = 1² + 1² + 1²; далее — число 4 и сумма 4 = 0² + 0² + 2²; после 5 = 0² + 1² + 2² и 6 = 1² + 1² + 2² переходим к 7, и тут обнаруживается, что ни одна из троек квадратов (всех возможных троек квадратов, каждый из которых не превышает 7)

0² + 0² + 0² 0² + 0² + 1² 0² + 0² + 2² 0² + 1² + 1² 0² + 1² + 2²

0² + 2² + 2² 1² + 1² + 1² 1² + 1² + 2² 1² + 2² + 1² 2² + 2² + 2²

не дает в сумме 7. На этом этапе вычисление завершается, а мы делаем вывод: 7 есть одно из искомых чисел, так как оно не является суммой квадратов трех чисел.

2.3. Незавершающиеся вычисления

Будем считать, что с задачей (А) нам просто повезло. Попробуем решить еще одну:

(B) Найти число, не являющееся суммой квадратов четырех чисел.

На этот раз, добравшись до числа 7, мы находим, что в виде суммы квадратов четырех чисел его представить вполне возможно: 7 = 1² + 1² + 1² + 2², поэтому мы переходим к числу 8 (сумма 8 = 0² + 0² + 2²+ 2²), далее — 9 (сумма 9 = 0² + 0² + 0² + 3²) и 10 (10 = 0² + 0² + 1² + 3²) и т.д. Вычисления все продолжаются и продолжаются (… 23 = 1² + 2² + 3² + 3², 24 = 0² + 2² + 2² + 4², …, 359 = 1² + 3² + 5² + 18², …) и завершаться, похоже, не собираются. Мы предполагаем, что искомое число, должно быть, невообразимо велико, и для его вычисления нашему компьютеру потребуется чрезвычайно большой промежуток времени и огромный объем памяти. Более того, мы уже начинаем сомневаться, существует ли оно вообще, это самое число. Вычисления все продолжаются и продолжаются, и конца им не видно. Вообще говоря, так оно и есть: описанная вычислительная процедура завершиться в принципе не может. Известна теорема, впервые доказанная в 1770 году великим французским (и отчасти итальянским) математиком Жозефом Луи Лагранжем, согласно которой в виде суммы квадратов четырех чисел можно представить любое число. Теорема эта, кстати, весьма непроста (доказать ее как-то пытался великий современник Лагранжа, швейцарский математик Леонард Эйлер, человек, отличавшийся удивительной математической интуицией, оригинальностью и продуктивностью, однако его постигла неудача).

Я, разумеется, не собираюсь докучать читателю подробностями доказательства Лагранжа, вместо этого рассмотрим одну не в пример более простую задачу:

(C) Найти нечетное число, являющееся суммой двух четных чисел.

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

0, 2, 4, 6, 8, 10, 12, 14, 16, …,

всегда получаются четные же числа; иными словами, никакая пара четных чисел не может дать в сумме нечетное число, т.е. число вида

1, 3, 5, 7, 9, 11, 13, 15, 17, ….

Я привел два примера ((B) и (C)) вычислений, которые невозможно выполнить до конца. Несмотря на то, что в первом случае вычисление и в самом деле никогда не завершается, доказать это довольно непросто, во втором же случае, напротив, бесконечность вычисления более чем очевидна. Позволю себе привести еще один пример:

(D) Найти четное число, большее 2, не являющееся суммой двух простых чисел.

Вспомним, что простым называется натуральное число (отличное от 0 и 1), которое делится без остатка лишь само на себя и на единицу; иными словами, простые числа составляют следующий ряд:

2, 3, 5, 7, 11, 13, 17, 19, 23, ….

Существует довольно высокая вероятность того, что отыскание решения задачи (D) также потребует незавершающейся вычислительной процедуры, однако полной уверенности пока нет. Для получения такой уверенности необходимо прежде доказать истинность знаменитой «гипотезы Гольдбаха», выдвинутой Гольдбахом в письме к Эйлеру еще в 1742 году и до сих пор недоказанной.

2.4. Как убедиться в невозможности завершить вычисление?

Мы установили, что вычисления могут как успешно завершаться, так и вообще не иметь конца. Более того, в тех случаях, когда вычисление завершиться в принципе не может, это его свойство иногда оказывается очевидным, иногда не совсем очевидным, а иногда настолько неочевидным, что ни у кого до сих пор не достало сообразительности однозначно такую невозможность доказать. С помощью каких методов математики убеждают самих себя и всех остальных в том, что такое-то вычисление не может завершиться? Применяют ли они при решении подобных задач какие-либо вычислительные (или алгоритмические) процедуры? Прежде чем мы приступим к поиску ответа на этот вопрос, рассмотрим еще один пример. Он несколько менее очевиден, чем (C), но все же гораздо проще (B). Возможно, нам удастся попутно получить некоторое представление о том, с помощью каких средств и методов математики приходят к своим выводам.

В предлагаемом примере участвуют числа, называемые шестиугольными:

1, 7, 19, 37, 61, 91, 127, …,

иными словами, числа, из которых можно строить шестиугольные матрицы (пустую матрицу на этот раз мы не включаем):

Каждое такое число, за исключением начальной единицы, получается добавлением к предыдущему числу соответствующего числа из ряда кратных 6:

6, 12, 18, 24, 30, 36, ….

Это легко объяснимо, если обратить внимание на то, что каждое новое шестиугольное число получается путем окружения предыдущего числа шестиугольным кольцом

причем число горошин в этом кольце обязательно будет кратно 6, а множитель при каждом увеличении шестиугольника на одно кольцо будет возрастать ровно на единицу.

Вычислим последовательные суммы шестиугольных чисел, увеличивая каждый раз количество слагаемых на единицу, и посмотрим, что из этого получится.

1 = 1, 1 + 7 = 8, 1 + 7 + 19 = 27, 1 + 7 + 19 + 37 = 64, 1 + 7 + 19 + 37 + 61 = 125.

Что же особенного в числах 1, 8, 27, 64, 125? Все они являются кубами. Кубом называют число, умноженное само на себя трижды:

1 = 1³ =1 × 1 × 1, 8 = 2³ = 2 × 2 × 2, 27 = 3³ = 3 × 3 × 3, 64 = 4³ = 4 × 4 × 4, 125 = 5³ = 5 × 5 × 5, ….

Присуще ли это свойство всем шестиугольным числам? Попробуем следующее число. В самом деле,

1 + 7 + 19 + 37 + 61 + 91 = 216 = 6 × 6 × 6 = 6³.

Всегда ли выполняется это правило? Если да, то никогда не завершится вычисление, необходимое для решения следующей задачи:

(E) Найти последовательную сумму шестиугольных чисел, начиная с единицы, не являющуюся кубом.

Думается, я сумею убедить вас в том, что это вычисление и в самом деле можно выполнять вечно, но так и не получить искомого ответа.

Прежде всего отметим, что число называется кубом не просто так: из соответствующего количества точек можно сложить трехмерный массив в форме куба (такой, например, как на рис. 2.1). Попробуем представить себе построение такого массива в виде последовательности шагов: вначале разместим где-нибудь угловую точку, а затем будем добавлять к ней, одну за другой, особые конфигурации точек, составленные из трех «плоскостей» — задней стенки, боковой стенки и потолка, как показано на рис. 2.2.

Рис. 2.1. Сферы, уложенные в кубический массив.

Рис. 2.2. Разберем куб на части — каждая со своей задней стенкой, боковой стенкой и потолком.

Посмотрим теперь на одну из наших трехгранных конфигураций со стороны, т. е. вдоль прямой, соединяющей начальную точку построения и точку, общую для всех трех граней. Мы увидим шестиугольник, подобный тому, что изображен на рис. 2.3. Точки, из которых складываются эти увеличивающиеся в размере шестиугольники, представляют собой, в сущности, те же точки, что образуют полный куб. То есть получается, что последовательное сложение шестиугольных чисел, начиная с единицы, всегда будет давать число кубическое. Следовательно, можно считать доказанным, что вычисление, требуемое для решения задачи (E), никогда не завершится.

Рис. 2.3. Каждую часть построения можно рассматривать как шестиугольник.

Кто-то, быть может, уже готов упрекнуть меня в том, что представленные выше рассуждения можно счесть в лучшем случае интуитивным умозаключением, но не формальным и строгим математическим доказательством. На самом же деле, перед вами именно доказательство, и доказательство вполне здравое, а пишу все это я отчасти и для того, чтобы показать, что осмысленность того или иного метода математического обоснования никак не связана с его «формализованностью» в соответствии с какой-либо заранее заданной и общепринятой системой правил. Напомню, кстати, о еще более элементарном примере геометрического обоснования, применяемого для получения одного общего свойства натуральных чисел, — речь идет о доказательстве истинности равенства a × b = b × a, приведенном в §1.19. Тоже вполне достойное «доказательство», хотя формальным его назвать нельзя.

Представленное выше рассуждение о суммировании последовательных шестиугольных чисел можно при желании заменить более формальным математическим доказательством. В основу такого формального доказательства можно положить принцип математической индукции, т.е. процедуру установления истинности утверждения в отношении всех натуральных чисел на основании одного-единственного вычисления. По существу, этот принцип позволяет заключить, что некое положение P(n), зависящее от конкретного натурального числа n (например, такое: «сумма первых n шестиугольных чисел равна n³»), справедливо для всех n, если мы можем показать, во-первых, что оно справедливо для n = 0 (или, в нашем случае, для n = 1), и, во-вторых, что из истинности P(n) следует истинность и P(n+1). Думаю, нет необходимости описывать здесь в деталях, как можно с помощью математической индукции доказать невозможность завершить вычисление (E); тем же, кого данная тема заинтересовала, рекомендую попытаться в качестве упражнения выполнить такое доказательство самостоятельно.

Всегда ли для установления факта действительной незавершаемости вычисления достаточно применить некие четко определенные правила — такие, например, как принцип математической индукции? Как ни странно, нет. Это утверждение, как мы вскоре увидим, является одним из следствий теоремы Гёделя, и для нас крайне важно попытаться его правильно понять. Причем недостаточной оказывается не только математическая индукция. Недостаточным будет какой угодно набор правил, если под «набором правил» подразумевать некую систему формализованных процедур, в рамках которой возможно исключительно вычислительным путем проверить корректность применения этих правил в каждом конкретном случае. Такой вывод может показаться чересчур пессимистичным, ибо он, по-видимому, означает, что, несмотря на то, что вычисления, которые нельзя завершить, существуют, сам факт их незавершаемости строго математически установить невозможно. Однако смысл упомянутого следствия из теоремы Гёделя заключается вовсе не в этом. На самом деле, все не так уж и плохо: способность понимать и делать выводы, присущая математикам — как, впрочем, и всем остальным людям, наделенным логическим мышлением и воображением, — просто-напросто не поддается формализации в виде того или иного набора правил. Иногда правила могут стать частичной заменой пониманию, однако в полной мере такая замена не представляется возможной.

• Вы понимаете что это значит Валентина

• Да мы не сможем никогда договориться по каким то вопросам.. если мы не сможем выразить своё понимание то теорема Гёделя это поистине теорема самого Сатаны... - сказала я ощутив холодный пот на спине.

• Вот откуда растёт религия.... но отсюда и возникает необходимость во власти.

  Священник помолчал и потом добавил

• Вы не очень точно мыслите Валентина. Правильный вывод такой понимание не поддаётся никаким правилам. Мы можем договариваться по каким то вопросам. Но эта способность не поддаётся описанию.. это похоже на мистический опыт. Это способность к творчеству...

• интересно

• Какой звук от хлопка одной руки, разрешите этот коан.

• Я не смогу разрешить его дайте другой

• У нас такой богатый выбор.. Обладает ли собака приро­дой Будды?

• Нет!

• Вся про­блема здесь заключается в том, что, согласно уче­нию дзэн, любое существо, включая собаку, обла­дает природой Будды. Тогда почему наставник ответил «нет»? Собеседник заметил: «Но ведь приро­да Будды проницает все существа, от будд до муравьев. Как же можно сказать, что у собаки ее нет?» Чжаочжоу ответил: «Собаке свойственно проводить различия». В другой раз Чжаочжоу дал утвердительный ответ на тот же вопрос. «От­чего же существо, обладающее природой Будды, родилось в столь неприглядном обличье?» — спросил собеседник Чжао­чжоу. «Оно приняло заблуждения за истину», — последовал ответ.