TREE(3)

TREE(3) — большое число, которое является верхней границей решения определенной математической проблемы в теории графов. Число Грэма в невообразимое количество раз больше, чем другие хорошо известные большие числа, такие, как гугол, гуголплекс и даже больше, чем число Скьюза и число Мозера, а TREE(3) в невообразимое число раз больше числа Грэма. Если число Грэма можно записать с помощью стрелочной нотации Кнута, и совсем просто — с помощью нотации Конвея, то для TREE(3) обе эти нотации лишены смысла.

Книга рекордов Гиннесса утверждает, что число Грэма — самое большое число, которое когда-либо использовалось в серьёзном математическом доказательстве, но эта информация устарела, так как TREE(3) является решением серьёзной математической задачи, и оно несоизмеримо больше числа Грэма.

Проблема теории графов

В теории графов деревом называется граф, в котором все вершины соединены рёбрами (возможно, посредством других вершин) и отсутствуют циклы (последовательности рёбер, соединяющие какую-либо вершину саму с собой). В данном случае деревья являются корневыми, то есть имеют определённую вершину - корень. Это понятное, но неформальное определение дерева. Теорема Краскала утверждает последовательность деревьев TREE(n), описанную следующими законами:

Каждое i-е дерево имеет не более i вершин.

Вершины имеют один из n видов; для TREE(3) удобно называть их «красными», «зелёными» и «синими».

Ни в одном из деревьев, если удалить одну или несколько вершин, не должно получиться какое-либо из уже присутствовавших деревьев.

Не должно быть одинаковых деревьев.

TREE(1) даёт единственное дерево с одной вершиной: если попытаться добавить ещё одно с двумя вершинами, при удалении любой из них получится первая. TREE(2)=3, в этой последовательности дерево с одной «красной» вершиной, с двумя «синими» и с одной «синей». Но начиная с TREE(3), происходит настоящий взрыв длины последовательности; на рисунке справа можно видеть первые 12 деревьев в ней. Тем не менее, теорема Краскала утверждает, что при любом конечном n последовательность не будет бесконечной.

Интересно отметить, что первое дерево имеет одну «красную» вершину, и вне зависимости от n больше ни одно из невообразимого числа деревьев не имеет «красных» вершин. Иначе, при удалении всех вершин, кроме этой «красной», получилось бы первое дерево.

Слабая tree-функция

Определим tree(n), слабую tree-функцию, как длину самой длинной последовательности из деревьев с вершинами одного цвета, описываемой следующими законами:

Каждое i-е дерево имеет не более i+n вершин.

Ни в одном из деревьев, если удалить одну или несколько вершин, не должно получиться какое-либо из уже присутствовавших деревьев.

Известно, что tree(1)=2, tree(2)=5, t r e e ( 3 ) ≥ 844424930131960 {displaystyle tree(3)geq 844424930131960} , но также известно, что TREE(3) намного больше, чем t r e e t r e e t r e e t r e e t r e e 8 ( 7 ) ( 7 ) ( 7 ) ( 7 ) ( 7 ) {displaystyle tree^{tree^{tree^{tree^{tree^{8}(7)}(7)}(7)}(7)}(7)} (верхний индекс в данном случае обозначает итерированную функцию).

Масштаб числа TREE(3)

Число TREE(3) несоизмеримо больше, чем число Грэма, для его представления бесполезны не только башни степеней, но и нотации Кнута и Конвея. В массивной нотации Бёрда TREE(3) можно примерно выразить как { 3 , 6 , 3 [ 1 [ 1 ¬ 1 , 2 ] 2 ] 2 } {displaystyle {3,6,3[1[1 eg 1,2]2]2}} . Общая скорость роста функции TREE(n) оценивается как f θ ( Ω ω ω ) ( n ) {displaystyle f_{ heta left(Omega ^{omega }omega ight)}(n)} в терминах быстрорастущей иерархии.

Тем не менее, TREE(3) всё же меньше, чем SCG(13) и число Лоудера, практически не описанное в русскоязычной литературе, и несоизмеримо меньше, чем числа, заданные с помощью невычислимых функций, такие, как число Райо.