Новый ум короля: О компьютерах, мышлении и законах физики | страница 8

Особенно впечатляющий пример попался мне на глаза уже после того, как была опубликована эта книга (а также «Тени разума»). Это произошло на лекции Дэна Исааксона в 1996 году. Речь шла об известной теореме Гудстейна[14]. Данный пример кажется мне настолько поучительным, что я хотел бы рассмотреть его здесь целиком, дабы читатель имел возможность непосредственно познакомиться с теоремами геделевского типа[15].

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

581 = 2^>9 + 2^>6 + 2^>2 + 1.

(Такая процедура применяется для формирования двоичного представления числа 581, а именно, приведения его к виду 1001000101, где единицы соответствуют тем степеням двойки, которые присутствуют в таком представлении, а нули — тем степеням, которых нет.) Далее можно заметить, что «показатели» в этом выражении — т. е. 9,6 и 2 — могут быть, в свою очередь, представлены аналогичным образом (9 = 2^>3 + 1, 6 = 2^>2 + 2^>1, 2 = 2^>1); и тогда мы получим (вспоминая, что 2^>1 = 2)

Здесь все еще есть показатель больший, чем двойка — в данном случае это «3», — для которого тоже можно написать разложение

3 = 2^>1 + 1, так что в конце концов мы будем иметь

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

(а) увеличивать «основание» на единицу,

(б) вычитать единицу.

Под «основанием» здесь понимается просто число «2», фигурирующее в исходном выражении, но мы можем сделать то же самое и с большими основаниями: 3, 4, 5, 6…..

Давайте посмотрим, что произойдет при применении операции (а) к последнему разложению числа 581, в результате которой двойки становятся тройками:

(что дает — если выписать его в обычной форме — сороказначное число, начинающееся с 133027946…). После этого мы применяем (б) и получаем

(т. е. по-прежнему сорокозначное число, начинающееся с 133027946…). Далее мы выполняем (а) еще раз и получаем

(это уже значительно большее число, состоящее из 618 знаков, которое начинается с 12926802…). Следующая операция — вычитание единицы — приводит к выражению

(где тройки получаются по той же причине, что и девятки в обычной десятичной записи, когда мы получаем 9999, вычитая 1 из 10 000). После чего операция (а) дает нам

(число, которое имеет 10923 знака и начинается с 1274…). Обратите внимание, что коэффициенты «3», которые возникают при этом, с необходимостью меньше, чем основание (в данном случае 5), и не изменяются с возрастанием последнего. Применяя