Большие числа
(2734 Слов, 16 Минут)Содержание
Введение
Большие числа — они встречаются в жизни часто. Не редко в новостном заголовке можно услышать “миллион”, “миллиард”, “триллион”. Но что же дальше? Как называются числа которые идут дальше и как их получить? В последующих главах об этом будет подробно рассказано.
Гугол и другие
Самый простой способ образовывать большие числа — добавлять нули. Единица с шестью нулями — миллион. С девятью нулями — миллиард. И так далее. Так можно добавить 100 нулей, и получить таким образом гугол. Записать его можно так: \(\begin{align} \text{Гугол}=10^{100} \\ & = 10 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 \\ & 000 000 000 000 000 000 000 000 000 000 000 000 000 000 \end{align}\) Компания Google была названа в честь этого числа, также как и гугология — неофициальный раздел математики о больших числах. Если поставить единицу, а затем гугол нулей, то получится гуголплекс, который также можно записать как $10^\text{Гугол}$ или $10^{10^{100}}$. Если 10 возвести в степень гуголплекса, то получится гуголплексплекс, или гуголдуплекс, потом гуголтриплекс, и так далее. Также существует название для числа $10^{3003}$. Это название — миллиллион. А вот число $10^{3000003}$ называется микриллион, или же милли-миллиллион.
Нотация кнута
Итак, вспомним определение умножения. В особенности, умножения натуральных чисел. Умножение определяется как многократное сложение:
\[ab=\underbrace{a+a+\cdots+a}_\text{b копий a}\]А что насчёт возведения в степень? Возведение в степень это многократное умножение:
\[a^b=\underbrace{a\times a\cdots\times a}_\text{b копий a}\]А что если мы хотим многократно возводить в степень? Такая операция называется тетрация.
\[^ba=\underbrace{a^{a^{{\cdot}^{{\cdot}^{{\cdot}^a}}}}}_\text{b копий a}\]Этот процесс можно продолжать дальше: затем идёт пентация, хексация и так далее. Это называется последовательностью гипероператоров. Но есть способ записать это проще — стрелочная нотация Кну́та. Главным символом в стрелочной нотации кнута является стрелка, указывающая вверх. Если между двумя числами стоит стрелка — то это возведение в степень:
\[a↑b=a^b\]Если две стрелки, то это тетрация:
\[a↑↑b={^ba}=\underbrace{a^{a^{{\cdot}^{{\cdot}^{{\cdot}^a}}}}}_\text{b копий a}\]Если три стрелки, то это пентация:
\[a↑↑↑b=\underbrace{^{^{^{^{^{^a{\cdot}}\cdot}\cdot}}a}a}_\text{b копий a}\]И так далее. То есть, каждая операция является повторением предыдущей. Кстати, в будущем нам понадобится так много стрелок, что их всех просто так не написать. Поэтому можно писать их количество в углу подобно показателю степени:
\[a↑^nb=a\underbrace{↑↑\cdots↑}_\text{n стрелок}b\]А теперь перейдём обратно к числам.
Число Грэма
Если увеличивать количество стрелок, то числа растут очень быстро:
\[\begin{align} & 3↑3=3^3=27 \\ & 3↑↑3={^33}=\underbrace{3^{3^3}}_\text{3 тройки}=3^{27}=7625597484987 \\ & 3↑↑↑3=\underbrace{^{^33}3}_\text{3 тройки}={^{^33}3}={^{7625597484987}3}=\underbrace{3^{3^{{.}^{{.}^{{.}^3}}}}}_\text{7625597484987 троек} \\ & 3↑↑↑↑3=\underbrace{^{^{^{^{^{^3{.}}.}.}}3}3}_\text{3↑↑↑3 троек} \end{align}\]Кстати, число $3↑↑↑3$ называется тритри, а число $3↑↑↑↑3$ называется $g_1$:
\[\text{tritri}=3↑↑↑3\] \[g_1=3↑↑↑↑3\]А теперь поставим $g_1$ стрелочек между двумя тройками, получится $g_2$:
\[g_2=3↑^{g_1}3\]А теперь поставим $g_2$ стрелочек, получится $g_3$:
\[g_3=3↑^{g_2}3\]Так можно продолжать очень долго. Функция, которая выдаёт $n$-ое $g$ называется функцией Грэма и обозначается $G(n)$. Так вот, повторяем пока не получится $g_{64}$, это и есть число Грэма:
\[\text{Число Грэма}=g_{64}=3↑^{g_{63}}3\]Число Грэма является очень известным числом, потому что это самое большое число, которое когда-либо использовалось в математической задаче. Именно в математической задаче, а не в математике вообще. Оно намного больше гугола, гуголплекса, и других чисел представленных ранее. Но это не самое большое число, которое будет здесь рассматриваться.
Быстрорастущая иерархия
Чтобы получить числа ещё больше, понадобится быстрорастущая иерархия. Это семейство быстрорастущих функций, которые отличаются уровнями. Обозначается она так:
\[f_\alpha(n)\]Альфа это уровень функции, а $n$ — аргумент. Быстрорастущая функция уровня ноль определяется так:
\[f_0(n)=n+1\]А следующий уровень функции определяется так:
\[f_{\alpha+1}(n)=f^n_\alpha(n)\]Здесь верхний индекс у функции обозначает что функция применяется повторно определённое колличество раз. Вот так выглядит расшифровка:
\[f_{\alpha+1}(n)=\underbrace{f_\alpha(f_\alpha(...f_\alpha}_\text{n повторений}(n)...))\]Найдём первые три уровня:
\[\begin{align} & f_0(n)=n+1 \\ & f_1(n)=2n \\ & f_2(n)=2^nn \end{align}\]Следующие уровни уже не могут быть выражены через элементарные функции. Тем не менее, их можно вычислить. Например, найдём $f_3(3)$:
\[\begin{align} f_3(3)=f_2(f_2(f_2(3)))=f_2(f_2(2^3\times3))=f_2(f_2(24))=f_2(2^{24}\times24)=f_2(402653184) \\ =2^{402653184}\times402653184≈(\text{Число с 121000000 цифрами}) \end{align}\]Получилось число со 121 миллионом цифр! А ведь уровень и аргумент — всего лишь тройки. Но чтобы достичь ещё более быстрого роста, нужно окунуться в мир бесконечностей.
Трансфинитные ординалы
Омега
Вернёмся как самому началу. Для чего вообще нужны числа? В первую очередь, чтобы считать объекты и давать им номера. Если число обозначает колличество элементов, то оно называется кардиналом, а если номер элемента — то ординалом. Обычно их можно не различать, так как они ведут себя одинаково при сложении, умножении и так далее. Но в мире бесконечностей они буквально являются разными числами. Итак, пусть у нас есть бесконечное количество элементов, например яблок. Все они лежат в коробке, которая имеет бесконечный объем. Если каждому яблоку присвоить номер, то так можно записать все натуральные числа. Но что если мы посчитали все яблоки и хотим присвоить номер яблоку, которое не лежит в коробке? Конечно, можно начать с него и дальше продолжать нумеровать яблоки, которые лежат в коробке, но имеется ввиду что сначала нужно занумеровать все яблоки в коробке. Какой тогда номер получит яблоко которое лежит снаружи? Этот номер обозначается греческой буквой омега и называется первым трансфинитным ординалом:
\[\omega\]Омега не может обозначать колличество, это именно номер элемента который идёт после бесконечности элементов. А именно, счётной бесконечности, которая обозначается как алеф-ноль:
\[\aleph_0\]Она называется счётной бесконечностью, потому что каждому элементу в ней можно дать номер, то есть сопоставить с натуральным числом. Но зачем же нам омега, число которое идёт после бесконечности? Дело в том, что омегу, как и любой другой трансфинитный ординал можно засунуть в индекс уровня быстрорастущей иерархии. Это будет означать, что уровень равен аргументу функции. Это записывается так:
\[f_\omega(n)=f_n(n)\]Например, $f_\omega(3)$ означает $f_3(3)$. Оно обозначается также как и трансфинитный ординал, потому что такая функция растёт быстрее чем любая другая функция у которой уровень не зависит от аргумента. Например, $f_\omega(n)$ растёт быстрее, чем $f_{1000}(n)$. С омегой, как и с любым другим числом можно производить операции. Например, складывать. Попробуем прибавить один. Получается $\omega+1$. Это число не больше, чем омега. Оно идёт после омеги, так как является ординалом. Так можно прибавить к омеге любое натуральное число:
\[\omega,\omega+1,\omega+2,\omega+3,\omega+4 ...\]И так далее до бесконечности. А именно, до $\omega+\omega$, то есть омега умножить на два. Так омегу можно умножать на разные числа:
\[\omega,\omega\times2,\omega\times3,\omega\times4 ...\]И так далее до $\omega\times\omega$, то есть омега в квадрате. Теперь можно возводить омегу в разные степени.
\[\omega,\omega^2,\omega^3,\omega^4 ...\]И так до $\omega^\omega$. А сейчас, просто будет возводить омегу в степень себя же всё больше и больше раз:
\[\omega,\omega^\omega,\omega^{\omega^\omega},\omega^{\omega^{\omega^\omega}} ...\]А что дальше? Мы достигли бесконечной степенной башни из омег. Но на самом деле, это ещё не всё. Вся эта бесконечная башня омег называется эпсилон-ноль:
\[\varepsilon_0=\underbrace{\omega^{\omega^{{.}^{{.}^{{.}^\omega}}}}}_\text{∞ омег}\]Эпсилон
Так как эпсилон-ноль является бесконечной лестницей из омег, если добавить одну омегу в эту башню, то ничего не поменяется, а записать это можно так:
\[\varepsilon_0=\omega^{\varepsilon_0}\]Эпсилон-ноль, как и омегу можно засунуть в индекс уровня быстрорастущей иерархии, но как же можно возводить число в степень себя бесконечное количество раз? Для таких случаев есть специальные последовательности. Суть в том, что нужно использовать последовательность, которая стремится к ординалу при стремлении номера элемента к бесконечности. Другими словами, возьмём последовательность которая нужна что достичь $\varepsilon_0$:
\[\varepsilon_0=[\omega,\omega^\omega,\omega^{\omega^\omega},\omega^{\omega^{\omega^\omega}} ...]\]А теперь возьмём элемент из этого списка с номером, который равен аргументу быстрорастущей функции. Например:
\[f_{\varepsilon_0}(3)=f_{\omega^{\omega^\omega}}(3)=f_{3^{3^3}}(3)=f_{3^{27}}(3)=f_{7625597484987}(3)\]Такие последовательности можно использовать при любом ординале который можно как-либо достичь снизу. Эпсилон-ноль есть, а где эпсилон-один, и другие эпсилоны? Сейчас мы их найдём. Возьмём эпсилон-ноль и прибавим к нему один, а потом возведём омегу в степень этого числа, а потом возведём омегу в степень того, что получилось. Если повторять так бесконечное количество раз, то получится эпсилон-один:
\[\varepsilon_1=[\omega^{\varepsilon_0+1},\omega^{\omega^{\varepsilon_0+1}},\omega^{\omega^{\omega^{\varepsilon_0+1}}} ...]\] \[\varepsilon_1=\underbrace{\omega^{{\cdot}^{{\cdot}^{{\cdot}^{\omega^{\varepsilon_0+1}}}}}}_\text{∞ омег}\]А теперь заменим эпсилон-ноль на эпсилон-один. Получится эпсилон-два:
\[\varepsilon_2=[\omega^{\varepsilon_1+1},\omega^{\omega^{\varepsilon_1+1}},\omega^{\omega^{\omega^{\varepsilon_1+1}}} \cdots]\] \[\varepsilon_2=\underbrace{\omega^{{\cdot}^{{\cdot}^{{\cdot}^{\omega^{\varepsilon_1+1}}}}}}_\text{∞ омег}\]Так можно получить эпсилон третий, эпсилон четвёртый, даже эпсилон омежный, эпсилон эпсилонный, эпсилон-эпсилон-эпсилон-… Вот мы достигли бесконечной лестницы из эпсилонов. Добавляя новые эпсилоны, ничего не изменится. Это называется неподвижная точка, а именно первая из них. Эта конструкция называется дзета-ноль:
\[\zeta_0=\overbrace{\varepsilon_{\varepsilon_{\varepsilon_{{\cdot}_{{\cdot}_{\cdot}}}}}}^{\text{∞ эпсилонов}}\]Дзета
Подобно эпсилонам, дзета-ноль имеет свойства, того что эпсилон с индексом дзета это тоже дзета, а также сохраняется свойство возведения омеги в степень дзеты:
\[\zeta_0=\omega^{\zeta_0}\] \[\zeta_0=\varepsilon_{\zeta_0}\]А вот последовательность для дзеты-ноль, которую можно использовать в качестве индекса уровня быстрорастущей иерархии:
\[\zeta_0=[\varepsilon_0, \varepsilon_{\varepsilon_0},\varepsilon_{\varepsilon_{\varepsilon_0}},\cdots]\]Кстати дзета-ноль также называется ординалом Кантора. Теперь попробуем найти дзеты с другими индексами. Возьмём дзета-ноль и прибавим один, потом найдём эпсилон с таким индексом, потом эпсилон с индексом того, что получилось и так далее. Получится дзета-один:
\[\zeta_1=\overbrace{\varepsilon_{\varepsilon_{{\cdot}_{{\cdot}_{{\cdot}_{\zeta_0+1}}}}}}^{\text{∞ эпсилонов}}\]Так можно получать новые дзеты, потом достичь неподвижной точки подобно эпсилонам и получить эта-ноль, но проблема в том что так у нас могут закончиться буквы греческого алфавита, поэтому нужно придумать какую-нибудь функцию, которая позволит достичь новых ординалов совершенно другим способом.
Функция Веблена
Функция Веблена — это функция от двух (или больше) аргументов. Обозначается она буквой фи. Итак, функция Веблена от нуля и нуля равна единице:
\[\varphi(0,0)=\omega^0=1\]Если второй ноль заменить на $x$, то получится $\omega^x$:
\[\varphi(0,x)=\omega^x\]Если вместо единицы поставить ноль, то получится эпсилон:
\[\varphi(1,x)=\varepsilon_x\]Если поставить два, то получится дзета:
\[\varphi(2,x)=\zeta_x\]Получается, что первый аргумент говорит сколько неподвижных точек мы уже прошли, а второй означает индекс числа. Но ведь можно и не использовать обычные числа. Что насчёт того, что поставить туда омегу? Или эпсилон-ноль? Или дзета-ноль? А чего мелочиться? Можно поставить функцию Веблена в функцию Веблена!
\[\varphi(\varphi(1,0),0)\]А теперь поставим функцию Веблена в функцию Веблена, которая находится в функции Веблена.
\[\varphi(\varphi(\varphi(1,0),0),0)\]Функция Веблена от функции Веблена от функции от функции от функции… Вот мы достигли неподвижной точки. Первый аргумент стал содержать бесконечное количество функций себя в себе. Такой ординал называется гамма-ноль. Буква гамма тут уже большая чтобы показать, что это большое число. Ещё его называют ординалом Фефермана или функцией Веблена от трёх аргументов:
\[\Gamma_0=\varphi(1,0,0)=\varphi(\varphi(\varphi(\varphi(\varphi(\varphi(\varphi(\varphi(\cdots\]Гамма
Если в функции Веблена от трёх аргументов менять третий аргумент, то поменяется индекс гаммы:
\[\Gamma_x=\varphi(1,0,x)\]Если поменять второй ноль на единицу, то получится бесконечная лестница гамм:
\[\overbrace{\Gamma_{\Gamma_{{\cdot}_{{\cdot}_{\cdot}}}}}^\text{∞ гамм}=\varphi(1,1,0)\]Если теперь засунуть функцию Веблена в функцию Веблена бесконечное количество раз вместо первого аргумента, то получится ординал Аккермана, или же функция Веблена от четырёх аргументов. Для него к сожалению стандартной буквы нет.
\[\varphi(1,0,0,0)\]Так можно сделать пять аргументов, шесть аргументов и так до бесконечности. То есть до функции Веблена с бесконечным количеством аргументов. Мы достигли малого ординала Веблена, сокращённо S. V. O. (англ. “Small Veblen Ordinal”):
\[\text{S. V. O.}=\varphi(\underbrace{1,0,0,0,\cdots}_\text{∞ аргументов})\]Ординалы Веблена
Малый ординал Веблена, хоть он и довольно велик, но он всё ещё малый. Возьмём функцию Веблена с эпсилон-ноль аргументов. Потом возьмём функцию Веблена с количеством аргументов, которое равно тому, что получилось, и так будем повторять до бесконечности. Получился большой ординал Веблена, сокращённо L. V. O. (англ. “Large Veblen Ordinal”).
\[\infty \text{ слоёв}\begin{cases} \text{L. V. O. = }\varphi(\underbrace{1,0,...}_{\underbrace{⋮}_{\varphi(1,0)}}) \\ \end{cases}\]На этом обозначения функции Веблена заканчиваются.
Бесконечно коллапсирующая функция
Бесконечно коллапсирующая функция, также известная как пси-функция Бухгольца позволит нам достичь ещё больших ординалов. Обозначается она буквой пси. Суть в том, что изначально у нас есть множество C(0), которое содержит четыре ординала, операции сложения умножения и возведения в степень, которые можно совершать конечное колличество раз (названия операций здесь сокращены до “СУВ”):
\[C(0)=\{0,1,\omega,\Omega, \text{СУВ, конечное}\}\]Здесь заглавная буква омега означает первый счётный недостижимый ординал. Суть бесконечно коллапсирующей функции в том, что она считает наименьшее число, которое нельзя получить из этого набора. Казалось бы, можно получить эпсилон-ноль, но это не так, ведь мы не можем возвести омегу в степень себя же бесконечное количество раз. Поэтому эпсилон ноль является самым маленьким числом которое нельзя получить:
\[\psi(0)=\varepsilon_0\]Чтобы найти значение этой функции от следующего числа, нужно добавить наш ответ в набор, теперь он будет называться C(1):
\[C(1)=\{0,1,\omega,\Omega, \varepsilon_0, \text{СУВ, конечное}\}\]Теперь самое маленькое число которое не получится сконструировать это эпсилон-один, ведь чтобы его получить нужно возвести эпсилон-ноль в степень себя бесконечное количество раз:
\[\psi(1)=\varepsilon_1\]То есть получается, что в множество нужно будет добавлять все предыдущие значения функции. Это можно записать так:
\[C(n)=\{0,1,\omega,\Omega, \psi(0), \psi(1), \psi(2), \psi(3),...\psi(n-1), \text{СУВ, конечное}\}\]Или так:
\[C(m)=\{0,1,\omega,\Omega, \bigcup_{k=0}^{n-1}\psi(k), \text{СУВ, конечное}\}\]Так получается, что аргумент бесконечно коллапсирующей функции равен индексу эпсилона, который она даёт. Как же тогда дойти до дзеты-ноль и дальше? Для этого у нас есть заглавная омега. Поставим же её в аргумент функции. Это будет означать что множество теперь содержит все возможные эпсилоны:
\[C(\Omega)=\{0,1,\omega,\Omega, \varepsilon_0, \varepsilon_1,…\varepsilon_\omega,...\varepsilon_{\varepsilon_0},...,\text{СУВ, конечное}\}\]Получится, что значение бесконечно коллапсирующей функции равно дзете-ноль:
\[\psi(\Omega)=\zeta_0\]А теперь добавим один к аргументу:
\[\psi(\Omega+1)=\varepsilon_{\zeta_0+1}\]Ещё один:
\[\psi(\Omega+2)=\varepsilon_{\varepsilon_{\zeta_0+1}}\]Получается, что число которое мы добавляем равно количеству эпсилонов в полученной лестнице:
\[\psi(\Omega+a)=\overbrace{\varepsilon_{\varepsilon_{\ddots_{\zeta_0+1}}}}^\text{a эпсилонов}\]А что если добавить ещё одну омегу? Это будет означать, что в лестнице бесконечное количество эпсилонов, то есть получается дзета-один:
\[\psi(\Omega+\Omega)=\psi(\Omega\times2)=\zeta_1\]Добавим ещё омегу, получится дзета-два:
\[\psi(\Omega\times3)=\zeta_2\]Получается, что множитель на единицу больше индекса полученной дзеты:
\[\psi(\Omega\times a)=\zeta_{a-1}\]Но если множитель является трансфинитным ординалом, то единицу вычитать не нужно. Если множителем будет ещё одна заглавная омега, то получится бесконечная лестница дзет, также она называется эта-ноль:
\[\psi(\Omega\times\Omega)=\psi(\Omega^2)=\overbrace{\zeta_{\zeta_\ddots}}^\text{∞ дзет}=\eta_0\]Заглавная омега в кубе даёт бесконечную лестницу эт, которую можно записать как функцию Веблена от четырёх и нуля:
\[\psi(\Omega^3)=\overbrace{\eta_{\eta_\ddots}}^\text{∞ эт}=\varphi(4,0)\]Таким образом можно установить связь между бесконечно коллапсирующей функцией и функцией Веблена:
\[\psi(\Omega^a)=\varphi(a+1,0)\]Заглавная омега в степени себя даёт гамму-ноль:
\[\psi(\Omega^\Omega)=\Gamma_0\]Умножим это на число — получим возможность изменять индекс гаммы:
\[\psi(\Omega^\Omega a)=\Gamma_{a-1}\]Если этим числом будет заглавная омега, то получится бесконечная лестница гамм, она же функция Веблена от единицы, единицы и нуля:
\[\psi(\Omega^\Omega\Omega)=\psi(\Omega^{\Omega+1})=\varphi(1,1,0)=\overbrace{\Gamma_{\Gamma_\ddots}}^\text{∞ гамм}\]Если к степени заглавной омеги прибавить число, то оно станет вторым аргументом полученной функции Веблена:
\[\psi(\Omega^{\Omega+a})=\varphi(1,a,0)\]Если не прибавить, а умножить, то получится что число станет первым аргументом функции Веблена:
\[\psi(\Omega^{\Omega a})=\varphi(a,0,0)\]Если этим числом будет заглавная омега, то нужно просто добавить ещё один аргумент к функции Веблена:
\[\psi(\Omega^{\Omega\times\Omega})=\psi(\Omega^{\Omega^2})=\varphi(1,0,0,0)\]Возведём в куб, появился ещё один аргумент:
\[\psi(\Omega^{\Omega^3})=\varphi(1,0,0,0,0)\]В общем, возведя в какую либо степень, у функции Веблена будет на два больше аргументов:
\[\psi(\Omega^{\Omega^a})=\varphi(\underbrace{1,0,…,0,0}_\text{a+2 аргументов})\]Если этой степенью будет строчная омега, то получится малый ординал Веблена:
\[\psi(\Omega^{\Omega^\omega})=\text{S. V. O.}\]А если омега будет заглавная, то получится большой ординал Веблена:
\[\psi(\Omega^{\Omega^\Omega})=\text{L. V. O.}\]Если возводить заглавные омеги в степени себя бесконечное количество раз, то получится ординал Бахмана-Ховарда, сокращённо BHO (англ. “Bachmann-Howard Ordinal”):
\[\psi(\underbrace{\Omega^{\Omega^{{.}^{{.}^{{.}^\Omega}}}}}_\text{∞ омег})=\text{B. H. O.}\]На этом обозначения бесконечно коллапсирующей функции заканчиваются, но это ещё не самый большой ординал, которого можно достичь.
Функция Фефермана
Функция Фефермана, так же известная как тета-функция обозначается буквой тета и является функцией от двух аргументов. Короче, если оба аргумента являются обычными числами, то это тоже самое, что и функция Веблена:
\[\theta(a,b)=\varphi(a,b)\]Если первый аргумент будет заглавной омегой, то первый аргумент в функции Веблена превратится в два аргумента: один и ноль:
\[\theta(\Omega,b)=\varphi(1,0,b)\]Если к заглавной омеге прибавить число, то второй аргумент превратится в это число:
\[\theta(\Omega+a,b)=\varphi(1,a,b)\]А если на число омегу умножить, то в это число превратится первый аргумент:
\[\theta(\Omega a,b)=\varphi(a,0,b)\]Если возвести заглавную омегу в квадрат, то добавится ещё один аргумент:
\[\theta(\Omega^2 a,b)=\varphi(a,0,0,b)\]Если возвести в куб, то добавиться ещё один аргумент:
\[\theta(\Omega^3 a,b)=\varphi(a,0,0,0,b)\]Вот малый ординал Веблена:
\[\theta(\Omega^\omega,0)=\text{S. V. O.}\]Вот большой ординал Веблена:
\[\theta(\Omega^\Omega,0)=\text{L. V. O.}\]Вот ординал Бахмана-Ховарда:
\[\theta(\varepsilon_{\Omega+1},0)=\text{B. H. O.}\]На этом обозначения тета-функции заканчиваются. Любые из вышеперечисленных ординалов можно поместить в индекс уровня быстрорастущей иерархии, чтобы получить очень большие числа. Например, число пентактулхум можно записать как $f_{\Gamma_0}(99)$.
TREE
Существуют и другие быстрорастущие функции помимо быстрорастущей иерархии. Например, TREE (от англ. “дерево”). Функция TREE основывается на построении графов, а именно так называемых деревьев. У функции TREE есть один аргумент. Этот аргумент равен колличеству цветов. Деревья состоят из вершин и рёбер. Каждая вершина может иметь цвет. Также, i-тое дерево не может иметь больше, чем i вершин. Любое дерево не может содержать предыдущее дерево. Это означает, что предыдущее дерево нельзя получить из текущего, удаляя вершины, удаляя рёбра и соединяя две вершины в одну. Если вершины имеют разный цвет, то они считаются разными. Сама функция возвращает колличество деревьев, которые можно получить таким образом. Можно представить, что первый цвет — красный, второй — зелёный, а третий — синий. А теперь, рассмотрим значения $\text{TREE}(n)$ при разных значениях $n$. При $n=1$, функция равна единице, ведь получится одно дерево: это точка первого цвета. Больше деревьев не получится, ведь они будут содержать его. При $n=2$, получится три дерева: первое будет точкой красного цвета, второе будет состоять из двух зелёных вершин. Последнее дерево будет единственной зелёной вершиной. Пока что имеем следующее:
\[\text{TREE}(1)=1\] \[\text{TREE}(2)=3\]А вот при $n=3$ получится много деревьев. Очень много деревьев. Их колличество намного больше числа Грэма. Это число больше, чем все числа, которые можно получить если поместить ординалы, представленные ранее в индекс быстрорастущей иерархии. С помощью TREE можно получить разнообразные абсурдно большие числа, например:
\[\text{TREE}(\text{TREE}(\text{TREE}(g_{64})))\]Но это ещё не самая быстрорастущая функция, которую можно придумать.
Нотация Конвея
Вернёмся назад, к менее быстрым и более примитивным алгоритмам. Один из таких — стрелочная нотация Конве́я. Числа в нотации Конвея записываются с помощью цепей. Цепи — это последовательности чисел, разделённых стрелками, указывающими вправо. Для того, чтобы вычислить значение какой-нибудь цепи, надо придерживаться некоторых правил. Первое правило: цепь из двух чисел означает возведения первого в степень второго.
\[a→b=a^b\]Второе правило: цепь из трёх чисел означает, что нужно поставить то колличество стрелок из нотации Кнута, которое показывает третий элемент между первым и вторым элементом.
\[a→b→c=a\underbrace{↑↑...↑}_\text{c стрелок}b\]Третье правило: единица в конце цепи может быть проигнорирована.
\[a→...→b→1=a→...→b\]Четвёртое правило: если в конце цепи стоит единица, а после ещё один элемент, то они могут быть проигнорированы.
\[a→...→b→1→c=a→...→b\]Пятое правило позволяет рекурсивно производить сами вычисления. Описать его словами будет сложновато, поэтому будет приведена только формула:
\[a→...→b→c→d=a→b→...→(a→...→b→(c-1)→d)→(d-1)\]Важно заметить, что стрелка Конвея, в отличии от стрелки Кнута не является оператором. Это означает, что $a→b→c$ это не $a→(b→c)$ и не $(a→b)→c$. Каждая цепь должна вычисляться полностью, как единый оператор, а не по частям. Таким образом можно попробовать воссоздать различные большие числа. Например, $3→3→3$ это число тритри, а $3→3→4$ это $g_1$.