Функция TREE

Функция TREE
Темпы роста	>* '"`UNIQ--postMath-00000001-QINU`"'+'"`UNIQ--postMath-00000002-QINU`"'-'"`UNIQ--postMath-00000003-QINU`"'
Автор(ы)	Харви Фридман
Год	2006

Функция TREE (англ. TREE sequence) — быстрорастущая функция TREE(n), возникшая из теории графов, разработанная математическим логиком Харви Фридманом. Фридман доказал, что функция в конечном итоге доминирует над всеми доказуемо тотальными рекурсивными функциями в системе $\text{ACA}_0+\Pi_2^1-\text{BI}$.

Первым значительно большим членом последовательности является знаменитое TREE(3) (на англоязычной гугология вики записывается как TREE[3]), примечательное тем, что это число, встречающееся в серьёзной математике, больше, чем число Грэма.

Определение

TREE(n)

Предположим, у нас есть последовательность n-меченых деревьев T₁, T₂ ... со следующими свойствами:

1. Каждое дерево T_i имеет не более вершин i.
2. Ни одно дерево не сохраняет информацию, а сохранение меток можно встроить в любое дерево, следующее за ним в последовательности.

Теорема Краскала о дереве утверждает, что такая последовательность не может быть бесконечной. Харви Фридман расширил эту тему, задав вопрос: учитывая некоторое n, какова максимальная длина такой последовательности? Эта максимальная длина является функцией n и является определением TREE(n) или функции TREE.

tree(n)

Определим $\text{tree}(n)$, слабую функцию tree, как длину самой длинной последовательности 1-меченных (или немаркированных) деревьев, такой что:

1. Каждое дерево в позиции k (для всех k) имеет не более чем k + n вершин.
2. Ни одно дерево не может быть гомеоморфно вложено в любое дерево, следующее за ним в последовательности.

Дерево в нижнем регистре — слабая функция tree, а TREE, всё в верхнем регистре, – обычная функция.

Анализ

Значения для TREE[n]

Первые два значения: TREE(1) = 1 и TREE(2) = 3. Следующее значение, TREE(3), как известно, очень велико. TREE(3) превышает число Грэма, числа Аккермана, nⁿ⁽⁵⁾(5), G3$\uparrow\uparrow\uparrow\uparrow$3, $tree\left(7\right)^{tree\left(7\right)^{tree\left(7\right)^{tree\left(7\right)^{tree\left(7\right)^{tree\left(7\right)^{8}}}}}}$. Крис Берд утверждал, что $\text{TREE}(3) > \{3, 6, 3 [1 [1 \neg 1,2] 2] 2\}$, в его нотации массива.

Нижние границы слабой tree(n) и TREE(3)

Хотя известно мало результатов, то есть доказанных утверждений о нижних границах tree, японский математик Такаюки Кихара подтвердил, что слабое tree(4) больше числа Грэма. Он представил иерархию $\text{tree}_n$ больших функций, индексированных ординалами $n \leq \omega + 1$, связанных с иерархией двоичных деревьев, снабжённых фиксированным кодированием последовательности натуральных чисел, и точно оценил иерархию с точки зрения быстрорастущей иерархии. Значение его работ состоит в том, что он явно оценивает значения комбинаторных больших функций, в то время как многие гугологи без доказательств грубо говорят о "соответствующих ординалах". Способность tree выражать ординалы не гарантирует сравнения $\text{tree}$ с быстрорастущей иерархией, и, следовательно, многие аргументы, основанные на этом неправильном выводе, бессмысленны. Подробности см. в здесь.

Кроме того, Кихара разработал метод точной оценки иерархии $\text{tree}_n$, расширенной до ординалов $n < \Gamma_0$, связанной с иерархией троичных деревьев, снабжённых фиксированным кодированием иерархии Веблена, и проверил $\text{tree}(4) > f_{\varepsilon_{0}}$($\text{Число Грэма}$) и $\text{tree}(5) > f_{\Gamma_{0}}$($\text{Число Грэма}$) относительно канонической системы фундаментальных последовательностей. В отличие от неверных аргументов относительно темпов роста, результат явно оценивает нижние границы конкретных значений функции tree.

В результате точного рассуждения Кихара получил строгое неравенство $\textrm{tree}(1.0001n+2) > f_{\text{МОВ}}(n)$ для $n \ge 3$, где $\text{МОВ}$ обозначает малый ординал Веблена. Поскольку Кихара утверждает, что TREE(3) намного больше, чем $\text{tree(Число Грэма)}$, из этого следует, что TREE(3) больше, чем $f_{ \text{МОВ}}(\text{Число Грэма})$.

Пользователь англоязычной гугология вики Deedlit11 установил нижнюю границу TREE(3) по дереву. Определите $\text{tree}_2(n)=\text{tree}^n(n)$ и $\text{tree}_3(n)=\text{tree}_2^n(n)$. (Обратите внимание, что она отличается ранее объяснённой от иерархии $\text{tree}_n$.) Затем Deedlit11 заявил $\text{TREE}(3) > \text{tree}_3(\text{tree}_2(\text{tree}(8)))$.

Значения $\text{tree}(n)$

Можно показать, что $\text{tree}(1) = 2, \text{tree}(2) = 5$, $\text{tree(3)} \geq 844,424,930,131,960$, и $\text{tree}(4) > \text{число Грэма}$. $\text{tree}(1)$ использует последовательность (с использованием #Альтернативные обозначения):

(())
()

$\text{tree}(2)$ немного больше, у нас есть две самые длинные последовательности, которые выглядят следующим образом:

((()))
(()()())
(()())
(())
()

В противном случае:

(()())
(((())))
((()))
(())
()

Определить точное значение для $\text{tree}(3)$ гораздо сложнее, поскольку необходимо проверить множество последовательностей, и каждая из них очень длинная. Тем не менее, последовательность была сформулирована и ответ дан.. Последовательность следующая:

(()()())
((()())())
((((()()))))
((((())(()))))
... 4 шага ...
(((()()))) 
((((((()))))((((()))))))) 
... 82 шага ...
((()()))
... много шагов ...
()

Как рассчитано по приведённой выше ссылке, $tree(3) = (3 : 2 \cdot 2^{(46+2)} - 2 \cdot 46 - 6 + 95) \cdot 2 + 1 - 3 = 3 \cdot 2^{48} - 8 = 844,424,930,131,960$.

Фридман определил функцию FFF(k), которая равна tree(k+1), но его предположение о том, что значение FFF(2) (также известное как tree(3)) меньше 100, кажется немного заниженным.

Альтернативные обозначения

(Эта альтернатива ещё требует формальной проверки.)

Деревья сложно визуализировать, не рисуя их, поэтому мы разработаем более компактный способ их представления. Рассмотрим язык, в котором есть различные виды скобок, такие как (), [], {} и т. д. Круглые скобки всегда идут парами и могут быть вложенными друг в друга. Внутри более крупного узла они могут быть объединены. Например, на этом языке допустимы следующие строки:

[]
([])
{[()]()}
[(){[[]]}(){(())[]}]

Предположим, у нас есть строка А. Мы будем называть пару соответствующих скобок узлом, из уважения к оригинальной конструкции дерева. Определите дочерний узел как узел, вложенный на один уровень глубже в исходный узел. Например, возьмём строку {[()()][][()]}; дочерними элементами узла, представленного {}, являются узлы, представленные [], но не узлы, представленные ().

Назовите узел удаляемым, если у него меньше двух дочерних элементов. Например, в строке {[()()][][()] все узлы () являются удаляемыми, как и два последних узла [] узлы, но не первый [] или {}. В строке ([(()())]) узел [] можно удалить.

Мы говорим, что строка A сводима к строке B, если A можно преобразовать в B путём удаления удаляемых узлов. Строка A сводится к строке B тогда и только тогда, когда дерево, представленное B, гомеоморфно вложима в дерево, представленное A.

Имея всё это в виду, мы можем создать функцию, которая должна соответствовать исходному определению TREE(k), при условии, что это обозначение было получено правильно. Предположим, у нас есть последовательность строк со следующими свойствами:

1. Вы можете использовать только скобки типа k.
2. В первой строке не более одной пары скобок, во второй строке не более двух пар скобок, в третьей строке не более трёх пар скобок и т. д.
3. Ни одна строка не может быть сокращена до более ранней строки.

TREE(k) — максимальная длина последовательности.

Для k = 1 оптимальная последовательность имеет только один член: ().

Для k = 2 оптимальная последовательность состоит только из трёх членов: (), затем [[]], затем [] .