Удивительные числа Вселенной полностью

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

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

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

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

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

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

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

В реальности нет интуитивно ясного способа осознать, почему TREE(3) настолько велико. Какой-то намек можно получить, взглянув на варианты игры, которые мы использовали поначалу. В игре с двумя типами семян мы были вынуждены использовать белые семена, начиная со второго круга. Однако если у нас остается всего один цвет, есть огромный риск обнаружить одно дерево внутри другого, и игре суждено быстро закончиться. А вот при игре с тремя видами семян ко второму кругу у нас остается целых два вида допустимых вариантов. Большая разница: мы можем играть с комбинациями, открывая все больше путей для новых экзотических узоров из деревьев. В конце концов мы исчерпаем все возможности, но это будет нескоро.

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