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

Ахилл : «Бесконечное совпадение»? В царстве натуральных чисел НИЧТО не бывает случайно — любое событие там основано на некой регулярности, скрытой или явной. Возьмите вместо триллиона семерку — она меньше и с ней полегче обращаться. У 7 есть свойство Ахилла.

Черепаха : Вы уверены?

Ахилл : Конечно, и вот почему. Если к 7 добавить 2, то вы получите 9 — число не простое; если же добавить к 7 любое другое простое число, то вы будете складывать два нечетных простых числа, результатом чего будет четное число — так что простого числа снова не получается. Так что здесь, если можно так выразиться, «Ахильность» семерки объясняется не бесконечным числом причин, но всего двумя, что весьма далеко от «бесконечного совпадения». Это только подтверждает то, что я уже сказал: для того, чтобы объяснить какую-либо арифметическую истину, нам никогда не понадобится бесконечное число причин. Если бы существовал такой арифметический факт, который был результатом бесконечного числа не связанных между собой совпадений, то мы никогда не смогли бы найти конечное доказательство этой истины — а это просто смешно.

Рис. 71. М. К. Эшер. «Порядок и хаос» (литография, 1950).

Черепаха : Это звучит вполне разумно, и вы не первый, кто высказывает подобное мнение. Однако —

Ахилл : Неужели есть кто-нибудь, кто не согласен с этой точкой зрения? Такие люди должны верить в «бесконечные совпадения», в наличие хаоса среди самого совершенного, гармонического и прекрасного среди всех творений — системы натуральных чисел.

Черепаха : Может, так они и считают — но задумывались ли вы когда-нибудь о том, что хаос может быть неотъемлемой частью красоты и гармонии?

Ахилл : Хаос — часть совершенства? Порядок и хаос в приятном единении? Да это же ересь!

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

Ахилл : Разумеется.

Черепаха : Пример первого — нехаотичного — вида поиска мы находим в проверке на свойство Гольдбаха. Надо просто перебирать простые числа, меньшие 2N, и если какая-нибудь пара таких чисел при сложении дает 2N, то следовательно 2N обладает свойством Гольдбаха; в противном случае, оно им не обладает. Подобная проверка не только наверняка закончится — вы даже можете предсказать, КОГДА она закончится.

Ахилл : Значит, это ПРЕДСКАЗУЕМО КОНЧАЮЩАЯСЯ проверка. Теперь вы, наверное, скажете мне, что некоторые теоретико-числовые свойства нуждаются в другого рода проверке, которая когда-либо кончится, но неизвестно, когда?

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

Ахилл : Я бы сказал, что об этой проверке просто слишком мало известно. Если как следует поработать, я уверен, что можно было бы определить, как долго она продлится, прежде чем придет к концу. Ведь должен же быть какой-то смысл в структурах целых чисел! Никогда не поверю, что эта система хаотична и непредсказуема.

Черепаха : Ваша интуитивная вера понятна, но не всегда оправдана. Разумеется, во многих случаях вы совершенно правы — если мы чего-то не знаем, из этого еще не следует, что это вообще непознаваемо! Но есть и такие свойства целых чисел, для которых можно доказать существование конечной процедуры проверки, а также — что невозможно заранее определить, как долго эта процедура будет продолжаться.

Ахилл : В это трудно поверить. Словно сам черт забрался в божественно прекрасное здание натуральных чисел!

Черепаха : Может быть, вам будет приятно узнать, что совсем не легко определить свойства, для которых существует конечная, но не ПРЕДСКАЗУЕМО конечная процедура проверки. Большинство «естественных» свойств целых чисел допускают предсказуемо конечные процедуры. Например, так можно проверить, является ли число простым, квадратом или десятой степенью какого-либо числа.

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

Черепаха : Это для меня слишком сложно, в особенности, когда я такая сонная. Лучше приведу вам пример свойства, которое весьма легко определить, но для которого неизвестна конечная процедура проверки. Заметьте, я не хочу сказать, что она никогда не будет открыта, — просто пока она еще не найдена. Для начала надо выбрать какое-нибудь число — предоставляю эту честь вам, Ахилл!

Ахилл : Как насчет 15?

Черепаха : Превосходно. Вы начинаете с вашего числа; если оно НЕЧЕТНО, вы умножаете его на три и прибавляете 1. Если оно ЧЕТНО, вы берете его половину. После этого мы повторяем процесс. Назовем число, которое таким образом рано или поздно превратится в 1, ИНТЕРЕСНЫМ, и число, которое не станет 1, НЕИНТЕРЕСНЫМ.

Ахилл : Интересное ли число 15? Посмотрим:

15 НЕЧЕТНО, так что я превращаю его в 3n + 1: 46

46 ЧЕТНО, так что я делю его на два: 23

23 НЕЧЕТНО, так что я превращаю его в Зn + 1: 70

70 ЧЕТНО, так что я делю его на два: 35

35 НЕЧЕТНО, так что я превращаю его в Зn + 1: 106

106 ЧЕТНО, так что я делю его на два: 53

53 НЕЧЕТНО, так что я превращаю его в Зn + 1: 160

160 ЧЕТНО, так что я делю его на два: 80

80 ЧЕТНО, так что я делю его на два: 40

40 ЧЕТНО, так что я делю его на два: 20

20 ЧЕТНО, так что я делю его на два: 10

10 ЧЕТНО, так что я делю его на два: 5

5 НЕЧЕТНО, так что я превращаю его в Зn + 1: 16

16 ЧЕТНО, так что я делю его на два: 8

8 ЧЕТНО, так что я делю его на два: 4

4 ЧЕТНО, так что я делю его на два: 2

2 ЧЕТНО, так что я делю его на два: 1.

Ух ты! Ничего себе путешествьице, от 15 до 1! Но я все же достиг цели. Это значит, что 15 обладает свойством «интересности». Хотелось бы узнать, какие числа НЕинтересные…

Черепаха : Вы заметили, что в этом простом процессе числа то возрастают, то уменьшаются?

Ахилл : Я особенно удивился, когда после 13 шагов я получил 16 — число, всего на 1 большее того , с которого я начал! В каком-то смысле, я почти вернулся к началу — но в другом смысле, я был весьма далек от начала. Странно и то, что чтобы решить задачку, мне пришлось добраться до 160. Интересно, почему так получилось?

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