Удивительные числа Вселенной - Антонио Падилья

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

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

Проясним ситуацию еще на одном примере. Вот еще два дерева.

Содержит ли дерево D дерево E? Первое, что нужно проверить: можем ли мы привести в соответствие семена? Закрываем все семена-крестики в дереве D и видим, что можем. Теперь нам нужно задаться вопросом о предках. Обратите внимание на белое и черное семена в верхних ветвях обоих деревьев. Проследив их родословную, мы видим, что в обоих случаях ближайшим общим предком оказывается черное семя, находящееся в корне. Подходит по всем статьям. Дерево D действительно содержит дерево E.

Теперь, когда правила понятны, мы готовы играть. Возьмем вариант, когда нам разрешено пользоваться только черными семенами. Я делаю ход первым. Помните, что это первое дерево, поэтому в нем может быть максимум одно семя. Изобразим его так.

Ваш ход. И у вас сразу же неприятности. Поскольку это второе дерево в лесу, в нем может быть не больше двух семян. Существует только два возможных дерева, которые вы можете изобразить: либо еще одно дерево из одного семени, либо дерево из двух семян.

Однако очевидно, что мое дерево содержится в обоих ваших возможных деревьях. Какое бы из них вы ни посадили, лес умрет. Избежать этого невозможно, поэтому игра заканчивается после первого же хода. Если использовать только один тип семян, лес может состоять только из единственного дерева, состоящего из одного семени.

Теперь давайте поиграем, когда разрешены два различных типа семян. Игра гарантированно закончится после трех ходов.

Какое бы дерево вы ни посадили дальше, оно обязательно уничтожит лес. Я догадываюсь, что вы не слишком впечатлены. Кому захочется играть в игру, которая обязательно закончится после трех жалких ходов?

Но подождите.

Пришло время сыграть с семенами трех видов — черные, белые и крестики. Давайте попробуем сделать несколько ходов.

Дела идут хорошо — лес все еще жив. Но сколько ходов мы можем сделать? Мы знаем, что в какой-то момент игра гарантированно завершится (это доказал Краскал). Но когда именно? Через сто ходов? Через гуголплекс? Когда число ходов будет равно числу Грэма?

Гораздо позже.

В этой книге мы уже читали истории о числовых исполинах — числах непостижимых размеров. Но эти колоссы — ничто по сравнению с нашим следующим левиафаном. Число, которое обозначают TREE(3), — гигантское предельное число ходов в игре с тремя семенами. Оно входит в крайне экстравагантную последовательность TREE(n). Если вы играете в Игру деревьев с n различными семенами, то игра закончится через TREE(n) ходов. Взгляните, как неспешно она начинается.

TREE(1) = 1 (поскольку игра с одним семенем продлится всего один ход),

TREE(2) = 3 (поскольку игра с двумя семенами продлится максимум три хода),

а потом бабах!

TREE(3) — это число, достаточно огромное, чтобы поглотить и гуголплекс, и число Грэма.

Все ваши представления превратились в ничто. Вы можете перейти к еще большим числам: TREE(4) получается при игре с четырьмя семенами, TREE(5) — при игре с пятью и т. д. Однако достаточно уже TREE(3). Умопомрачительного, невообразимого и безумного.

Первоначальная гипотеза Важони и последующее доказательство Краскала сообщают нам, что Игра деревьев рано или поздно закончится, пока вы играете с конечным числом семян. Американский математик и философ Харви Фридман понял, что она может порождать заодно чрезвычайно большие числа. Талант Фридмана к логике проявился уже в очень раннем возрасте. Когда ему было всего четыре или пять лет, он нашел словарь и спросил у матери, что это. «Книга со значениями слов», — ответила мать. Через несколько дней мальчик оспорил это утверждение. Он сказал, что словари бесполезны, потому что ходят по кругу. Слово «большой» они определяют через слова «крупный», «значительный», а те — через слово «большой». Как вообще можно узнать, что на самом деле что-либо означает? Примерно через десяток лет его ранние таланты обеспечили ему место в Книге рекордов Гиннесса — как самому молодому университетскому профессору: в возрасте 18 лет он получил в Стэнфордском университете звание ассистент-профессора[77].

Фридман заметил, что число TREE(3) невероятно велико. Математик не мог точно определить его, но сумел показать, что оно больше — гораздо больше, — чем любое другое число, которое вы найдете в этой книге. Он дал оценку — снизу — в терминах огромных чисел, известных как числа Аккермана. Чтобы ощутить их размер, нужно вернуться к лестнице Грэма. Возможно, вы помните, что первая ступенька g1 = 3 ↑ ↑ ↑ ↑ 3 была уже чудовищно велика, а дальше числа принимали совершенно неконтролируемый характер. Вторую ступень мы строили с помощью g1 стрелок: g2 = 3 ↑g1 3, третью — с помощью g2 стрелок: g3 = 3 ↑g2 3 и т. д., пока не дошли до шестьдесят четвертой ступеньки и числа Грэма. Но предположим, что вы продолжаете подниматься: на шестьдесят пятую ступеньку, когда число стрелок равно числу Грэма, на шестьдесят шестую, шестьдесят седьмую, на гуголную ступень этой лестницы. Предположим, что вы не отдыхали, пока не поднялись вот на такое количество ступеней:

2 ↑ 187 195187 196.

В этой формуле 187 195 стрелок Кнута. Это невероятно большое число, но оно всего лишь говорит о количестве ступенек лестницы Грэма! Всего шестьдесят четыре ступени вверх по этой лестнице привели вас к числу Грэма. Можете ли вы хотя бы начать осознавать, куда вас приведут 2 ↑ 187 195187 196 ступеней? Этот настоящий гигант похож на предложенную Фридманом оценку числа TREE(3), но не питайте иллюзий: это сильно заниженная оценка. На самом деле TREE(3) гораздо больше, этот левиафан среди левиафанов доминирует над всем, с чем мы сталкивались в нашем путешествии по большим числам.

В реальности нет интуитивно ясного