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

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

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

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

существуют такие формальные системы, чье негативное пространство (множество не-теорем) не является позитивным пространством никакой другой формальной системы.

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

Существуют рекурсивно счетные множества, не являющиеся рекурсивными.

Выражение «рекурсивно счетные» (часто сокращаемое как р.с.) — математическое соответствие нашему художественному понятию «курсивно рисуемые», а рекурсивный — соответствие «рекурсивным». Множество строчек является р. с., когда все они могут быть выведены путем применения типографских правил — например, множество теорем типа S или множество теорем системы MIU; на самом деле, это определение приложимо ко множеству теорем любой формальной системы. Оно сравнимо с понятием о «рисунке» как о «множестве линий, которые могут быть произведены в соответствии с художественными правилами» (что бы это последнее не означало!). А «рекурсивное множество» подобно рисунку, чей фон, в свою очередь, также является рисунком — в таком случае не только рисунок, но и его дополнение будут р. с. Из этого вытекает следующий результат:

Существуют такие формальные системы, у которых нет типографского алгоритма разрешения.

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

Предположим, что мы нашли множество R («R» — рисунок) натуральных чисел, которое мы можем вывести каким-либо формальным путем — вроде множества составных чисел. Предположим, что его дополнением является множество F («F» — фон) — простые числа. Вместе взятые, R и F дают все натуральные числа. Мы знаем правило, позволяющее вывести все числа множества R, для чисел множества F такого правила не существует. Важно, что если числа R выводятся исключительно в возрастающем порядке, то мы всегда можем охарактеризовать F. Трудность заключается в том, что многие р. с. множества производятся при помощи таких методов, которые выводят элементы в произвольном порядке, так что не известно, появится ли какое-либо число, до сих пор пропускаемое, если подождать еще чуть-чуть.

На вопрос «Все ли рисунки рекурсивны?» мы ответили отрицательно. Теперь мы видим что придется ответить отрицательно и на аналогичный вопрос математиков «Все ли множества рекурсивны?» Имея это в виду, давайте вернемся к этому расплывчатому понятию «формы». Обратимся снова к нашим множествам R — рисунки и F — фон. Легко согласиться с тем, что все числа во множестве R имеют какую-то общую «форму» — но можно ли сказать то же самое о числах множества F? Странный вопрос. С самого начала имея дело с бесконечным множеством всех натуральных чисел, весьма сложно прямо и четко определить «дырки», остающиеся в списке после изъятия оттуда неких чисел. Таким образом, возможно что на самом деле у этих дырок нет никаких общих характеристик «формы». Неясно, стоит ли вообще использовать здесь такое соблазнительное словечко как «форма». Может быть лучше не определять этого понятия оставив ему некую интуитивную гибкость.

Вот вам еще одна головоломка, над которой вы можете поразмыслить в связи с изложенным выше Можете ли вы охарактеризовать следующее множество чисел (или его негативное пространство)?

1 3 7 12 18 26 35 45 56 69

Чем данная последовательность напоминает рисунок РИСУНОК-РИСУНОК?

Как же насчет формальной системы для вывода простых чисел? Как это сделать? Способ состоит в том чтобы, не останавливаясь на умножении, обратиться прямо к неделимости, представив ее позитивно. Ниже дана схема аксиом и правило вывода теорем, представляющих понятие числа, не являющегося делителем других чисел (ND = не делитель).

СХЕМА АКСИОМ:  xyNDx, где x и у — строчки тире

Например, -----ND--, где x заменен на «--» и y — на «---»

ПРАВИЛО: Если xNDy является теорема, то xNDxу также будет теоремой

Приложив это правило дважды, вы можете вывести теорему

-----ND------------

которая интерпретируется как «5 не делитель 12». Однако ---ND------ не является теоремой. В чем будет ошибка, если вы попытаетесь вывести эту строчку?

Чтобы определить, что данное число простое, у нас должны быть какие-то сведения о его свойствах неделимости. В частности, мы хотим знать, что это число не делится на 2, 3, 4, и т. д., до числа, меньшего его на единицу. Однако в формальных системах мы не можем позволить себе таких расплывчатых формулировок как «и так далее». Здесь нужна исчерпывающая точность. Нам бы хотелось иметь возможность сказать на языке системы: «число Z свободно от делителей до X» (SOD = свободно от делителей), имея в виду, что не одно число между 2 и X не является делителем Z. Это можно сделать, но здесь есть небольшой трюк. Если хотите, можете попытаться найти его.

Решение заключается в следующем:

ПРАВИЛО: Если --NDz является теоремой, то zSOD-- также будет теоремой.

ПРАВИЛО: Если zSODx и x-NDz являются теоремами, то zSODx также будет теоремой.

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

ПРАВИЛО: Если z-SODz является теоремой, то Pz- также будет теоремой.

Не будем забывать, что 2 — тоже простое число!

АКСИОМА: P--

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

Акростиконтрапунктус

Ахилл: Хорошая у вас коллекция бумерангов, я такой нигде не видал!

Черепаха: Обыкновенная, не преувеличивайте, пожалуйста. У любой Черепахи можно увидеть коллекцию ничуть не хуже.