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

132

ФЕРМА? [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 имеет свойство Черепахи». Таким образом, в смысле выразительной мощи ТТЧ — это именно то, что нам требуется.

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

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

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

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

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

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

Следовательно, вопрос в том, можно ли найти потолок для любого цикла — или же теории натуральных чисел присуща некая беспорядочность, мешающая нам предсказать заранее длину некоторых вычислений? Удивительно то, что верно второе, и сейчас мы увидим, почему. Наверное, именно такой тип рассуждений свел с ума Пифагора, впервые доказавшего иррациональность корня из двух. В нашем доказательстве мы будем использовать знаменитый диагональный метод, изобретенный основателем теории множеств Георгом Кантором.

Клуб Б, номера-индексы и Белые Программы

Для начала представим себе забавное понятие: некий клуб, членами которого являются все возможные программы Блупа. Нет нужды говорить, что число членов этого клуба (назовем его клубом Б) бесконечно. Рассмотрим часть этого клуба, так сказать, подклуб, полученный после трех последовательных фильтрующих операций. Первый фильтр оставит нам только программы без вызова. Из этого подклуба мы уберем все тесты, оставив только функции. (Кстати, последняя процедура программ без вызова определяет, является ли программа тестом или функцией.) Третий фильтр удержит только функции с единственным входным параметром. Что у нас остается?

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

Назовем такие специальные функции Белыми Программами.

Следующим шагом будет установление для каждой Белой Программы определенного номера-индекса. Как это можно сделать? Легче всего составить список Белых Программ согласно их длине: самая короткая возможная программа будет #1, вторая по длине — #2 и т. д. Разумеется, некоторые программы окажутся одинаковой длины — в этом случае мы будем пользоваться также алфавитным порядком. Термин «алфавитный порядок» здесь употребляется в широком смысле: алфавит включает как кириллические, так и латинские буквы, а также все специальные символы Блупа в неком произвольно установленном порядке, как, например, следующий:

А Б В Г Д Е Ж З И Й К Л М Н О П

Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Э Ь Ю Я

A B C D E F G H I J K L M N

O P Q R S T U V W X Y Z + Х

1 0 2 3 4 5 6 7 8 9