Число Грэма на пальцах™

[sly2m]

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

Как только ребенок (а это происходит где-то года в три-четыре) понимает, что все числа делятся на три группы "один, два и много", он тут же пытается выяснить: насколько много бывает много, чем много отличается от очень много, и может ли оказаться так

Comments

[salvator_vals]

Я тоже по-русски почти ничего не нашел. Могу кратко объяснить что такое Tree(n). Давайте рассмотрим правильные скобочные выражения, в которых используются n типов скобок. Например такое: [()()] или такое: ([][][](()))
Здесь два типа скобок, причем каждой открывающей скобке соответствует закрывающая скобка той же формы, это и означает, что выражение правильное. На самом деле эти выражения однозначно соответствуют корневым деревьям, у которых вершины помечены числами от 1 до n. Пусть у нас есть два правильных скобочных выражения A и B. Будем говорить, что A>B, если B получается из A удалением нескольких пар отткрывающих-закрывающих скобок. Например (()[])>([])>(). Теперь давайте рассмотрим последовательность скобочных выражений (для фиксированного n) A(i), где в A(i) не более i пар скобок и для любого i>j не верно, что A(i)>A(j). Оказывается, что для любого n такая последовательность всегда конечна. Максимальная длина такое последовательности и есть Tree(n). Давайте посчитаем Tree(1) и Tree(2):
Tree(1)=1
( )
Tree(2)=3
( )
[ [ ] ]
[ ]
А вот Tree(3) уже намного больше числа Грехема. Последовательность может начинаться например так:
{}
[[]]
[()()]
[((()))]
([][][][])
([][][](()))
([][](()()()))
([][](()(())))
([][](((((()))))))
([][]((((())))))
([][](((()))))
([][]((())))
([][](()))
([][]())

[beren_91]

Крайне похоже на описание вот этого:
https://www.proza.ru/2013/02/09/1991
Что то вроде крайне быстрорастущей функции, хотя вот откопал интересную инфу про функцию, которая гарантированно при определенном значении аргумента обгонит любую другую, нужно только подождать :-)

[salvator_vals]

Да, я тоже нашел это текст, но он по-моему несколько невнятный.

> которая гарантированно при определенном значении аргумента обгонит любую другую

Здесь какое-то слово пропущено, так как функция не может обогнать, например, саму себя. Скорее всего имелась ввиду функция, которая обгонит любую вычислимую функцию, то-есть такую, для вычисления которой существует алгоритм. Такую функцию действительно легко построить. Функция Tree(n) является вычислимой, значит и ее обгонит.