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

Предположим, что мы нашли множество 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, и так далее. Именно эта «монотонность» или однонаправленность — отсутствие игры между укорачивающими и удлиняющими правилами — позволила нам уловить суть простых чисел. И именно этой потенциальной сложностью формальных систем, могущих вместить сколько угодно взаимодействий между движением вперед и назад, объясняются такие ограничивающие результаты как Теорема Гёделя и Проблема Остановки Тюринга, как и тот факт, что не все рекурсивно счетные множества рекурсивны.

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

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

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

Ахилл: Феноменально! Вы, Черепахи, никогда не перестанете удивлять меня своей любовью к собиранию бумерангов.

Черепаха: Шутить изволите? Да страсть к коллекционированию этого оружия у нас в крови. А сейчас, не угодно ли пройти в гостиную?

Ахилл: Только после Вас, как обычно, госпожа Черепаха. (Следуя за Черепахой, Ахилл входит в гостиную и направляется в угол комнаты.) Я вижу, что у вас также неплохое собрание пластинок. Какую музыку вы предпочитаете?

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

Ахилл: Да? Что же это за музыка?

Черепаха: Такая, о которой вы, скорее всего, никогда не слыхали. Я называю ее «разбивальная музыка».

Ахилл: Едва ли не самая поразительная вещь, которую я слыхал от вас за последнее время. Что значит это необычное название?

Черепаха: Рада удовлетворить ваше любопытство. Эта музыка — для разбивания патефонов.

Ахилл: О ужас!

Черепаха: Вы полагаете?

Ахилл: С ума сойти! Воображаю, как вы, пританцовывая с кувалдой в руке, сокрушаете один патефон за другим под звуки «Битвы при Виттории» Бетховена.

Черепаха: Какое у вас образное мышление! Должна вас разочаровать, эта музыка не совсем то, что вы предполагаете. Однако ее истинная природа тоже любопытна. Могу дать вам кое-какие разъяснения…

Ахилл: Интересно… Я весь внимание!

Черепаха: Йоркширский мой приятель, старый Краб (вы с ним, часом, не знакомы?) пришел ко мне однажды с визитом…

Ахилл: Архибольшая умница, этот Краб. Я много о нем наслышан, но сам с ним никогда не встречался. Уверен, что знакомство со стариком принесло бы мне немалое удовольствие.

Черепаха: Конечно, он личность незаурядная. Надо бы мне устроить вашу встречу; может быть, мы все как-нибудь увидимся в парке на прогулке. Думаю, что вы понравитесь друг другу!

Ахилл: Расчудесная идея! Буду ждать этого с нетерпением… Однако мы отклонились от темы вы, кажется, хотели объяснить мне, что такое разбивальная музыка?

Черепаха: Ох, да, чуть не забыла. Так вот, пришел, значит, Краб ко мне в гости. Вы, наверное, слыхали, что у него всегда была страсть ко всяческим машинкам и приспособлениям; в то время он прямо-таки сходил с ума по патефонам. Он тогда только что приобрел свой первый патефон и, будучи наивным и доверчивым покупателем, поверил во всю ту белиберду, что нам обычно говорят усердные клерки в надежде сбыть свой товар. На этот раз клерк объявил, что понравившийся Крабу патефон может верно воспроизвести любой звук. Короче говоря, Краб уверился в том, что он купил Идеальный Патефон.