Даглас Хофштадтер - ГЕДЕЛЬ, ЭШЕР, БАХ: эта бесконечная гирлянда

• Название: ГЕДЕЛЬ, ЭШЕР, БАХ: эта бесконечная гирлянда
• Автор: Даглас Хофштадтер
• Издательство: Издательский Дом «Бахрах-М», 2001.
• Жанр: Математика
• Год: 2001
• ISBN: ISBN 5-94648-001-4

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

Выдающийся американский ученый изобретает остроумные диалоги, обращается к знаменитым парадоксам пространства и времени, находит параллели между картинами Эшера, музыкой Баха и такими разными дисциплинами, как физика, математика, логика, биология, нейрофизиология, психология и дзен-буддизм.

Автор размышляет над одной из величайших тайн современной науки: каким образом человеческое мышление пытается постичь самое себя. Хофштадтер приглашает в мир человеческого духа и «думающих» машин. Это путешествие тесно связано с классическими парадоксами, с революционными открытиями математика Курта Геделя, а также с возможностями языка, математических систем, компьютерных программ и предметного мира говорить о самих себе с помощью бесконечных отражений.

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

Переведенная на 17 языков, книга потрясла мировое интеллектуальное сообщество и сразу стала бестселлером. Теперь и русский читатель получил доступ к одной из культовых книг XX века.

---

Блуп — язык для определения предсказуемо конечных вычислений. Стандартное название функций, которые можно просчитать на Блупе, — примитивно-рекурсивные функции; стандартное название свойств, которые можно обнаружить с помощью тестов на Блупе, — примитивно-рекурсивные предикаты. Так, функция 23n — примитивно-рекурсивная функция, а утверждение «n — простое число» — примитивно-рекурсивный предикат.

Интуиция подсказывает нам, что свойство Гольдбаха — примитивно-рекурсивное; чтобы сделать это яснее, я приведу определение процедуры Блупа, которая показывает, как можно проверить наличие или отсутствие этого свойства:

ОПРЕДЕЛИТЬ ПРОЦЕДУРУ «ГОЛЬДБАХ?» [N]:

БЛОК 0: НАЧАЛО

     ЯЧЕЙКА(О) <= 2;

     ПОВТОРИТЬ ЦИКЛ НЕ БОЛЬШЕ N РАЗ;

     БЛОК 1: НАЧАЛО

          ЕСЛИ {ПРОСТОЕ? [ЯЧЕЙКА(О)]

              И ПРОСТОЕ? [МИНУС [N, ЯЧЕЙКА(0)]]},

                ТОГДА:

          БЛОК 2:НАЧАЛО

                 ВЫХОД 2: <= ДА;

                 ВЫЙТИ ИЗ БЛОКА 0;

          БЛОК 2: КОНЕЦ

          ЯЧЕЙКА(0) <= ЯЧЕЙКА(0) + 1;

     БЛОК 1:КОНЕЦ;

БЛОК 0: КОНЕЦ.

Как обычно, мы предполагаем, что выходом будет НЕТ, если не доказано обратное, и мы просто ищем при помощи «грубой силы» такие пары чисел, которые в сумме дают N. Если они оба — простые числа, то мы выходим из внешнего блока; в противном случае, мы пробуем снова, пока не исчерпаем все возможности.

(Внимание: тот факт, что свойство Гольдбаха — примитивно-рекурсивное, не означает, что вопрос «все ли числа обладают свойством Гольдбаха» прост. Это далеко не так!)

Рис. 72. Структура программы без вызова в Блупе. Чтобы такая программа была самодостаточная, каждое определение процедуры может вызывать только те процедуры, определенные выше него.

Предлагаемые упражнения

Сможете ли вы написать похожую процедуру Блупа, которая проверяла бы наличие у числа свойства Черепахи (или Ахилла)? Попытайтесь! Если вам это не удается, то только лишь потому, что вы не знаете, какой будет верхняя граница? Возможно ли, что существует какое-то фундаментальное препятствие, вообще не позволяющее формулировать подобные алгоритмы в Блупе? А что, если задать те же вопросы касательно свойства интересности, определенного в Диалоге?

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

ФАКТОРИАЛ [N] = N! (ФАКТОРИАЛ ОТ N)

      (например, ФАКТОРИАЛ [4] = 24)

ОСТАТОК [M.N] = остаток после деления М на N

      (например, ОСТАТОК [24,7] = 3)

ЦИФРА π [N] = N-ная цифра π после запятой  

      (например, ЦИФРА π [1] = 1, 

                 ЦИФРА π [2] = 4,

                 ЦИФРА π [1 000 000] = 1)

ФИБО[М] = N-ное число ряда Фибоначчи

     (например, ФИБО [9] = 34)

ПРОСТОЕ ЧИСЛО ЗА [N] = наименьшее простое число, следующее за N

     (например, ПРОСТОЕ ЧИСЛО ЗА [33] = 37)

СОВЕРШЕННОЕ [N] = N-ное «совершенное» число, такое как, например, 28, чьи множители в сумме дают само это число: 28 =1+2+4+7+14

     (например, СОВЕРШЕННОЕ [2] = 28)

ПРОСТОЕ? [N] = ДА если N простое число, в противном случае, НЕТ.

СОВЕРШЕННОЕ [N]? = ДА если N совершенное число, в противном случае, НЕТ.

ОБЫКНОВЕННОЕ? [А, В, С, N] = ДА, если A N+ В N= С N верно; в противном случае, НЕТ.

    (например, ОБЫКНОВЕННОЕ ? [3, 4, 5, 2] = ДА,

                      ОБЫКНОВЕННОЕ ? [3, 4, 5, 3] = НЕТ)

ПЬЕР? [А,В,С] = ДА, если A N+ В N= С N верно для N > 1; в противном случае, НЕТ.

     (например, ПЬЕР? [3, 4, 5] = ДА,

                      ПЬЕР? [1,2,3] = НЕТ)

ФЕРМА? [N] == ДА, если А N + В N = С N верно для неких положительных величин А, В, и С; в противном случае, НЕТ.

      (например, ФЕРМА? [2] = ДА)

ЧЕРЕПАШЬЯ ПАРА? [M, N] = ДА если M и M + N простые числа; в противном случае, НЕТ.

     (например, ЧЕРЕПАШЬЯ ПАРА? [5, 1742] = ДА

                      ЧЕРЕПАШЬЯ ПАРА? [5, 100] = НЕТ)

ЧЕРЕПАХА [N] = ДА, если N - разность двух простых чисел, в противном случае, НЕТ.

     (например, ЧЕРЕПАХА [1742] = ДА,

                       ЧЕРЕПАХА [7] = НЕТ)

ХОРОШО СФОРМИРОВАННАЯ MIU? [N] = ДА, если N, в качестве строчки MIU, хорошо сформировано; в противном случае, НЕТ.

      (например, ХОРОШО СФОРМИРОВАННАЯ MIU? [310] = ДА,

                       ХОРОШО СФОРМИРОВАННАЯ MIU? [415] = НЕТ)

ПАРА ДОКАЗАТЕЛЬСТВА MIU? [М, N] = ДА. если М, рассматриваемое как  последовательность  строчек MIU, является деривацией N, рассматриваемого  как строчка системы MIU; в противном случае, НЕТ.

     (например, ПАРА ДОКАЗАТЕЛЬСТВА MIU? [3131131111301, 301] = ДА,

                       ПАРА ДОКАЗАТЕЛЬСТВА MIU? [311130, 30] = НЕТ)

ТЕОРЕМА MIU? [N]= ДА, если N, в качестве строчки MIU, является теоремой; в противном случае, НЕТ.

      (например, ТЕОРЕМА MIU? [311] = ДА,

                       ТЕОРЕМА MIU? [30]= НЕТ,

                       ТЕОРЕМА MIU? [701]= НЕТ)

ТЕОРЕМА ТТЧ? [N]= ДА, если N, в качестве строчки ТТЧ, является теоремой; в противном случае, НЕТ.

        (например, ТЕОРЕМА ТТЧ? [666111666] = ДА,

                          ТЕОРЕМА ТТЧ?[123666111666] = НЕТ,

                          ТЕОРЕМА ТТЧ? [7014] = НЕТ)

ЛОЖНО? [N)= ДА, если N, в качестве строчки ТТЧ, представляет собой ложное утверждение теории чисел; в противном случае, НЕТ.

       (например,  ЛОЖНО? [666111666]= НЕТ,

                         ЛОЖНО? [223666111666]= ДА,

                         ЛОЖНО? [7014]= НЕТ)

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

Выразимость и представимость

Прежде, чем рассмотреть еще несколько интересных вопросов, касающихся Блупа, и перейти к его родственнику, Флупу, давайте вернемся к тому, зачем нам вообще понадобился Блуп, и к его связи с ТТЧ. Ранее я сказал, что критическая масса, необходимая формальной системе для приложения метода Гёделя, достигается тогда, когда в этой системе представимы все примитивно-рекурсивные понятия. Что это означает? Прежде всего, мы должны различать между понятиями представимости и выразимости. Выразить предикат означает просто перевести его с русского языка на язык формальной системы. Это не имеет ничего общего с теоремностью. С другой стороны, если предикат представлен, это означает, что

(1) Все истинные примеры этого предиката — теоремы;

(2) Все ложные примеры этого предиката — не теоремы.

Под «примером» я имею в виду строчку, которая получается при замене всех свободных переменных на числовые величины. Например, предикат m + n = k представлен в системе рr, поскольку каждый истинный пример этого предиката — теорема, и каждый ложный — не теорема. Таким образом, каждый частный случай сложения, истинный или ложный, переводится в разрешимую строчку системы рr. Однако система pr не способна выразить — и меньше того, представить — никакие другие свойства натуральных чисел. Она была бы слабеньким кандидатом в соревновании систем, способных символизировать теорию чисел.

ТТЧ, со своей стороны, способна выразить практически любой теоретико-численный предикат; например, легко написать строчку ТТЧ, выражающую предикат «b имеет свойство Черепахи». Таким образом, в смысле выразительной мощи ТТЧ — это именно то, что нам требуется.

Однако вопрос «Какие свойства представлены в ТТЧ?» эквивалентен вопросу «Насколько мощной аксиоматической системой является ТТЧ?» Можно ли сказать, что в ней представлены все возможные предикаты? Если это так, то ТТЧ может ответить на любой вопрос теории чисел — то есть она полна.

Примитивно-рекурсивные предикаты представлены в ТТЧ

Хотя вскоре выяснится, что ее полнота не более чем химера, ТТЧ полна, по крайней мере, в отношении примитивно-рекурсивных предикатов. Иными словами, любое высказывание теории чисел, чья истинность или ложность могут быть разрешены компьютером за некое предсказуемое время, разрешимо также в ТТЧ. Иными словами,

Если на Блупе можно написать тест для некого свойства натуральных чисел, то это свойство представлено в ТТЧ.

Есть ли функции, не являющиеся примитивно-рекурсивными?

Свойства чисел, которые можно обнаружить с помощью тестов Блупа, широко варьируются: это простота чисел, их совершенность, наличие у них свойства Гольдбаха, то, является ли число степенью двух и т. д. Логично было бы спросить, всякое ли свойство чисел может быть обнаружено соответствующей программой Блупа. Нас не должно смущать, что мы пока не можем проверить число на его интересность. Это может означать лишь то, что у нас не хватает знаний; возможно, если как следует поискать, нам удалось бы найти верхнюю границу соответствующего цикла. Тогда мы могли бы тут же написать тест Блупа. То же самое можно сказать и о свойстве Черепахи.