Представление о BEAF

BEAF, или функция расширяющегося массива Бауэрса — гугологическая функция, созданная Джонатаном Бауэрсом. Эта статья представляет собой пошаговое руководство, постепенно знакомящее с функцией, призванное дать интуитивное представление о том, как она работает.

Стрелочная нотация

Прежде чем мы сможем понять BEAF, мы должны понять расширенные операторы в его основе. Стрелочная нотация описывает набор операторов, введённых Дональдом Кнутом:

$a\uparrow b=a^b$.

$a\uparrow \uparrow b=\underbrace {a\uparrow a\uparrow \ldots \uparrow a\uparrow a} _{\text{b копий числа a}}={^{b}}a=\underbrace {a^{a^{a^{.^{.^{.}}}}}} _{\text{b копий числа a}}$. Гугологи называют это тетрацией; стрелки должны решаться справа налево.

$a\uparrow \uparrow \uparrow b=\underbrace {a\uparrow \uparrow a\uparrow \uparrow \ldots \uparrow \uparrow a\uparrow \uparrow a} _{\text{b копий числа a}}$. Также известно как пентация.

В общем случае,

$a\uparrow ^{n}b=\underbrace {a\uparrow ^{n-1}a\uparrow ^{n-1}\ldots \uparrow ^{n-1}a\uparrow ^{n-1}a} _{\text{b копий числа a}}$, где $a\uparrow ^{n}b=a\underbrace {\uparrow \uparrow \uparrow \cdots \uparrow \uparrow \uparrow } _{\text{n стрелок}}b$.

Вот несколько примеров:

$3\uparrow 4=3^{4}=81$ (3 в 4 степени)

$2\uparrow \uparrow 4=2\uparrow 2\uparrow 2\uparrow 2=2\uparrow 2\uparrow 4=2\uparrow 16=65536$ (2, тетрированная с 4)

$4 \uparrow\uparrow 4$ = 2361022671...5261392896, что содержит около $8,0723\cdot 10^{153}$ цифр (4, тетрированная с 4)

$3\uparrow \uparrow \uparrow 3=3\uparrow \uparrow 3\uparrow \uparrow 3=3\uparrow \uparrow 3^{3^{3}}=3\uparrow \uparrow 7,625,597,484,987$ (3, пентированная с 3)

Операторная нотация

Бауэрс разработал обобщение стрелочной нотации, которое он называет операторной нотацией:

$a\ \{n\}\ b=a\uparrow ^{n}b$

то есть: $a\ \{1\}\ b=a^{b}$

и $a\ \{n\}\ b=\underbrace {a\ \{n-1\}\ a\ \{n-1\}\ \ldots \ \{n-1\}\ a\ \{n-1\}\ a} _{b}$

Например, $3\ \{4\}\ 5=3\uparrow \uparrow \uparrow \uparrow 5$.

Эта форма операторной нотации является просто сокращением для стрелочной нотации. Однако Бауэрс делает ещё один шаг вперёд, заключая n в две пары фигурных скобок вместо одной:

$a\ \{\{1\}\}\ b=\underbrace {a\ \{a\ \{\ldots a\ \{a} _{b}\}\ a\ldots \}\ a\}\ a$

Бауэрс называет это a, расширенная с b. Здесь b — количество "слоёв", включая внешний, или (количество a + 1) / 2. (Для компьютерных специалистов: расширение не является примитивно-рекурсивным. Вы не можете запрограммировать его, используя только циклы с предварительно вычисленными пределами.)

Пример:

$3\ \{\{1\}\}\ 3=3\ \{3\ \{3\}\ 3\}\ 3=3\ \{3\ \{2\}\ 7,625,597,484,987\}\ 3$

Если мы изменим n на 2, мы получим умножацию.

$a\ \{\{2\}\}\ b=\underbrace {a\ \{\{1\}\}\ a\ \{\{1\}\}\ \ldots \ \{\{1\}\}\ a\ \{\{1\}\}\ a} _{b}$

Можно использовать более высокие значения для n:

$a\ \{\{3\}\}\ b=\underbrace {a\ \{\{2\}\}\ a\ \{\{2\}\}\ \ldots \ \{\{2\}\}\ a\ \{\{2\}\}\ a} _{b}$ (степеннация)

$a\ \{\{4\}\}\ b=\underbrace {a\ \{\{3\}\}\ a\ \{\{3\}\}\ \ldots \ \{\{3\}\}\ a\ \{\{3\}\}\ a} _{b}$ (расширотетрация)

расширопентация, расширохексация, и т.д.

Все эти операторы правоассоциативны и работают так же, как и нижние гипероператоры.

Использование трёх фигурных скобок вместо двух даёт нам подрывация:

$a\ \{\{\{1\}\}\}\ b=\underbrace {a\ \{\{a\ \{\{\ldots a\ \{\{a\}\}\ a\ldots \}\}\ a\}\}\ a} _{b}$

$a\ \{\{\{2\}\}\}\ b=\underbrace {a\ \{\{\{1\}\}\ a\ \{\{\{1\}\}\}\ \ldots \ \{\{\{1\}\}\}\ a\ \{\{\{1\}\}\}\ a} _{b}$ (умножедрынация)

$a\ \{\{\{3\}\}\}\ b=\underbrace {a\ \{\{\{2\}\}\}\ a\ \{\{\{2\}\}\}\ \ldots \ \{\{\{2\}\}\}\ a\ \{\{\{2\}\}\}\ a} _{b}$ (степендрынация)

$a\ \{\{\{4\}\}\}\ b=\underbrace {a\ \{\{\{3\}\}\}\ a\ \{\{\{3\}\}\}\ \ldots \ \{\{\{3\}\}\}\ a\ \{\{\{3\}\}\}\ a} _{b}$ (подрывотетрация)

подрывопентация, подрывохексация и т. д.

Четыре набора скобок — детонация (умножетонация, степентонация, детонатетрация и т. д.), а пять — пентонация (уножепентонация, степенпентонация, пентонотетрация и т. д.). Затем у нас есть хексонация, хептонация и т. д.

В нашей операторной нотации теперь четыре аргумента:

$a\ \{1\}\ b=a^{b}$

$a\ \{1\}^{d}\ b=\underbrace {a\ \{a\ \{\ldots a\ \{a\}^{d-1}\ a\ldots \}^{d-1}\ a\}^{d-1}\ a} _{b}$

$a\ \{c\}^{d}\ b=\underbrace {a\ \{c-1\}^{d}\ a\ \{c-1\}^{d}\ \ldots \ \{c-1\}^{d}\ a\ \{c-1\}^{d}\ a} _{b}$

Здесь верхний индекс d указывает количество фигурных скобок, заключённых вокруг c. Например, $\{c\}^{4}$ — сокращение для $\{\{\{c\}\}\}\}$. Эта конкретная нотация не использовалась Джонатаном Бауэрсом.

Гуголог Крис Берд доказал, что эта 4-аргументальная нотация примерно такая же быстрорастущая, как цепная нотация стрел. Однако мы едва коснулись поверхности BEAF!

Линейная нотация массива

Операторная нотация начинает трещать по швам. Более простой способ записать $a\ \{c\}^{d}\ b$ — $\{ a , b , c , d \}$. Наша новая запись:

• $\{a,b,1,1\}=a^{b}$
• $\{a,b,1,d\}=\underbrace {\{a,a,\{a,a,\ldots \{a,a,a,d-1\}\ldots ,d-1\},d-1\}} _{b}$ если $d > 1$
• $\{a,b,c,d\}=\underbrace {\{a,\{a,\ldots \{a,a,c-1,d\}\ldots ,c-1,d\},c-1,d\}} _{b}$ если $c > 1$

Единицы считаются значениями по умолчанию, поэтому мы можем отсечь конец массива, если он состоит только из единиц. Например, $\{a,b,1,1\}$ можно просто записать $\{a,b\} = a^b$.

Мы можем несколько упростить правила 2 и 3, полагаясь на их рекурсивную природу:

$\{a,b,1,d\}=\underbrace {\{a,a,\{a,a,\ldots \{a,a,a,d-1\}\ldots ,d-1\},d-1\}} _{b}$

$=\{a,a,\underbrace {\{a,a,\ldots \{a,a,a,d-1\}\ldots ,d-1\}} _{b-1},d-1\}=\{a,a,\{a,b-1,1,d\},d-1\}$

$\{a,b,c,d\}=\underbrace {\{a,\{a,\ldots \{a,a,c-1,d\}\ldots ,c-1,d\},c-1,d\}} _{b}$

$=\{a,\underbrace {\{a,\ldots \{a,a,c-1,d\}\ldots ,c-1,d\}} _{b-1},c-1,d\}=\{a,\{a,b-1,c,d\},c-1,d\}$

Но вы заметите проблему с этим рефакторингом. Мы указали индуктивное правило, но не базовый случай, поэтому в обоих случаях $b$ будет уменьшаться вечно! Мы приводим правило, объясняющее, что происходит, когда $b$ достигает $1$:

$\{a,1,c,d\}=a$

Этот шаг очень важен для определения BEAF. Если вам это непонятно, попробуйте решить это на бумаге.

Пять записей и более

Давайте подведем итоги и рассмотрим наш текущий набор правил:

• $\{a,b,1,1\}=\{a,b\}=a^{b}$
• $\{a,1,c,d\}=a$
• $\{a,b,1,d\}=\{a,a,\{a,b-1,1,d\},d-1\}$, $b,d>1$
• $\{a,b,c,d\}=\{a,\{a,b-1,c,d\},c-1,d\}$, $b,c>1$

С нашим новым упрощением, в последних двух примерах едва заметна закономерность. Вооружившись этими знаниями, мы попытаемся добавить пятую запись:

• $\{a,b\} = a^b$
• $\{a,1,c,d,e\}=a$
• $\{a,b,1,1,e\}=\{a,a,a,\{a,b-1,1,1,e\},e-1\}$, $b,e>1$
• $\{a,b,1,d,e\}=\{a,a,\{a,b-1,1,d,e\},d-1,e\}$, $b,d>1$
• $\{a,b,c,d,e\}=\{a,\{a,b-1,c,d,e\},c-1,d,e\}$, $b,c>1$

Добавление пятой записи было, к счастью, простым. Мы можем продолжить шаблон и добавить шестую:

• $\{a,b\} = a^b$
• $\{a,1,c,d,e,f\}=a$
• $\{a,b,1,1,1,f\}=\{a,a,a,a,\{a,b-1,1,1,1,f\},f-1\}$, $b,f>1$
• $\{a,b,1,1,e,f\}=\{a,a,a,\{a,b-1,1,1,e,f\},e-1,f\}$, $b,e>1$
• $\{a,b,1,d,e,f\}=\{a,a,\{a,b-1,1,d,e,f\},d-1,e,f\}$, $b,d>1$
• $\{a,b,c,d,e,f\}=\{a,\{a,b-1,c,d,e,f\},c-1,d,e,f\}$, $b,c>1$

Мы должны обобщить это на произвольное количество членов. Чтобы сделать это кратким, мы введём некоторую терминологию. Первая запись $a$ — база, а вторая $b$ — штрих. После штриха первая не-1 запись — пилот; запись непосредственно перед ней — второй пилот, а все записи до этих — пассажиры. Значение массива записывается как $v(A)$. Используя эти термины, мы можем полностью описать линейную нотацию массива.

Линейная нотация массива

Пусть $b$ будет базой, а $p$ — штрихом.

1. Основное правило. Если пилота нет (то есть все записи после штриха равны 1), то $v(A) = b^p$.
2. Правило штриха. Если штрих равен 1, то $v(A) = b$.
3. Катастрофическое правило. В противном случае...
   1. Заменить второго пилота копией исходного массива, но с штрихом, уменьшенным на единицу.
   2. Уменьшить значение пилота на 1.
   3. Переместить всех пассажиров в $b$.

(конец определения)

Это воссоздание классической нотации массива Бауэрса, описанной около 2002 года. В оригинале использовалось пять правил, но нам удалось сократить его до трёх в соответствии с современным BEAF.

Примеры

Теперь мы полностью решили линейные массивы и приведём несколько примеров, чтобы получить более наглядное представление.

${\begin{matrix}\{3,3,1,1,1,3\}&=&\{3,3,3,3,\{3,2,1,1,1,3\},2\}\\&=&\{3,3,3,3,\{3,3,3,3,3,2\},2\}\\&=&\{3,3,3,3,\{3,\{3,2,3,3,3,2\},2,3,3,2\},2\}\\&=&\{3,3,3,3,\{3,\{3,\{3,1,3,3,3,2\},2,3,3,2\},2,3,3,2\},2\}\\&=&\{3,3,3,3,\{3,\{3,3,2,3,3,2\},2,3,3,2\},2\}\\&=&\{3,3,3,3,\{3,\{3,\{3,2,2,3,3,2\},1,3,3,2\},2,3,3,2\},2\}\\&=&\{3,3,3,3,\{3,\{3,\{3,\{3,1,2,3,3,2\},1,3,3,2\},1,3,3,2\},2,3,3,2\},2\}\\&=&\{3,3,3,3,\{3,\{3,\{3,3,1,3,3,2\},1,3,3,2\},2,3,3,2\},2\}\\&=&\{3,3,3,3,\{3,\{3,\{3,3,\{3,2,1,3,3,2\},2,3,2\},1,3,3,2\},2,3,3,2\},2\}\\&=&\{3,3,3,3,\{3,\{3,\{3,3,\{3,3,\{3,1,1,3,3,2\},2,3,2\},2,3,2\},1,3,3,2\},2,3,3,2\},2\}\\&=&\{3,3,3,3,\{3,\{3,\{3,3,\{3,3,3,2,3,2\},2,3,2\},1,3,3,2\},2,3,3,2\},2\}\end{matrix}}$

Если все записи в массиве одинаковы, мы можем преобразовать его в более простой массив более высокого порядка:

Три записи преобразуются в четыре:

• $\{a,a,a\}=\{a,2,1,2\}$
• $\{a,a,\{a,a,a\}\}=\{a,3,1,2\}$
• $\{a,a,\{a,a,\{a,a,a\}\}\}=\{a,4,1,2\}$ и так далее.

Четыре записи преобразуются в пять:

• $\{a,a,a,a\}=\{a,2,1,1,2\}$
• $\{a,a,a,\{a,a,a,a\}\}=\{a,3,1,1,2\}$
• $\{a,a,a,\{a,a,a,\{a,a,a,\{a,a,a,\{a,a,a,a\}\}\}\}\}=\{a,6,1,1,2\}$

Пять записей преобразуются в шесть:

• $\{a,a,a,a,a\}=\{a,2,1,1,1,2\}$
• $\{a,a,a,a,\{a,a,a,a,a\}\}=\{a,3,1,1,1,2\}$
• $\{a,a,a,a,\{a,a,a,a,\{a,a,a,a,a\}\}\}=\{a,4,1,1,1,2\}$

В общем случае, $\{a,b,1,1,...,1,1,2\}=\{a,a,a,...,a,a,\{a,a,a,...a,a,\{a,a,a,...,a,a,\{a,a,a,...,a,a\}\ldots \}\}\}$, с b-1 слоями.

Мультиразмерные массивы

Мы введём новый оператор, "массив b из a":

$b\&a=\underbrace {\{a,a,...,a,a\}} _{b}$

Эта функция диагонализирует всё, что мы сделали до сих пор. Это довольно большая функция; если вы знакомы с быстрорастущей иерархией, то $n\&n$ примерно на уровне $f_{\omega^\omega}(n)$.

Чтобы продолжить расширять нотацию массива, нам нужно немного поработать над интуицией. $b\&a$ смутно напоминает $a^{b}=\underbrace {\{a\cdot a\cdots a\cdot a\}} _{b}$, поэтому давайте запишем "нотацию массива второго порядка" с изменённым базовым правилом:

1. Базовое правило. Если пилота нет (то есть все записи после штриха равны 1), то $v(A)=p\&b$.

Чтобы обозначить нотацию массива второго порядка, мы поместим после массива нижний индекс 2: $\{a,b\}_{2}=p\&b$. Помимо этого базового правила, другие правила нотации массива остаются неизменными, поэтому у нас по-прежнему есть $\{a,b,c\}_{2}=\{a,\{a,b-1,c\}_{2},c-1\}_{2}$ и так далее. Мы могли бы также сделать 3, пока мы в нём. Определим $b\&_{2}a=\underbrace {\{a,a,...,a,a\}_{2}} _{b}$ и заменим $\&$ на $\&_{2}$ в базовом правиле выше. Бам, нотация массива третьего порядка.

Отсюда расширение должно быть очевидным и немного скучным. Давайте обобщим и создадим новый набор правил с $r$ в качестве порядка:

1. Базовое правило. Если пилота нет и $r=1$, то $v(A) = b^p$.
2. Правило порядка. Если пилота нет и $r>1$, то $v(A)=p\&_{r-1}b$.
3. Основное правило и катастрофическое правило остаются неизменными.

Итак, как мы можем максимально использовать преимущества этого расширения? Позволяя $r$ быть значением массива:

$\{a,a,\ldots ,a,a\}_{\{a,a,\ldots ,a,a\}}$

Чёрт, почему бы не вложить его $b$ раз?

$\{a,a,\ldots ,a,a\}_{\{a,a,\ldots ,a,a\}_{\{a,a,\ldots ,a,a\}_{._{._{.}}}}}$ (где каждый массив имеет $b$ записей)

Мы будем использовать $b\&_{1,2}a$, чтобы записать это, что позволит нам определить "нотацию порядка 1,2". (Хммм... почему "1,2"?) Далее следует $2,2$, что просто $\{a,a,\ldots ,a,a\}_{1,2}$. Мы можем индуктивно определить порядок n,2 таким же образом, как мы определили порядок n.

Теперь для 1,3:

$\{a,a,\ldots ,a,a\}_{\{a,a,\ldots ,a,a\}_{\{a,a,\ldots ,a,a\}_{._{._{.}}},2},2}$

и в общем случае 1,n для n > 1:

$\{a,a,\ldots ,a,a\}_{\{a,a,\ldots ,a,a\}_{\{a,a,\ldots ,a,a\}_{._{._{.}}},n-1},n-1}$

Пока что неплохо. А как насчёт 1,1,2? Отсюда видно, что $r$ принимает несколько записей и может начать отражать способ работы обычных массивов. Находим первую запись, не равную 1, в $r$, называем её "порядковый пилот", заменяем "второй порядковый пилот" копией массива с простым числом, уменьшенным на 1, уменьшаем порядковый пилот и устанавливаем первые записи $p$ в $b$.

Но зачем нам вообще разделять пилот и порядковый пилот? Нам нужно заботиться о порядке только тогда, когда массив представляет собой только основание и простое число, как в $\{b,p\}_{1,1,2}$. Решающим шагом здесь является утверждение, что $r$ является частью массива, и, следовательно, порядковый пилот является пилотом.

Давайте изменим нашу запись, чтобы поместить $r$ в фигурные скобки. Увлечение Бауэрса более высокими измерениями привело его к тому, что он поместил $r$ во вторую строку, например:

$\left\{{\begin{matrix}b,p\\1,1,2\end{matrix}}\right\}$

В строке мы запишем это как $\{b,p\ (1)\ 1,1,2\}$, где (1) обозначает разрыв между строками. Опять же, каждая строка автоматически заполняется (счётно) бесконечным числом единиц, поэтому этот массив идентичен $\{b,p,1\ (1)\ 1,1,2\}$ или $\{b,p,1,1,1\ (1)\ 1,1,2,1,1\}$.

Давайте попробуем наше новое расширение на две строки для существующего набора правил, скажем, $\{b,p(1)2\}$. Сразу же мы видим, что второго пилота нет! Нам нужно будет пересмотреть правила, чтобы учесть случаи отсутствия второго пилота. Здесь возникает менее тривиальная проблема:

$\{b,p(1)1,1,2\}=\{b,b,b,\ldots (1)b,\{b,p-1(1)1,1,2\}\}$

Проблема в бесконечном количестве b в первой строке; нам нужно только p из них. Наше текущее определение "пассажиров" сломало нашу систему, поэтому мы также исправим его. Вкратце:

• база — первая запись.
• штрих — вторая запись.
• пилот — первая запись, не равная 1, после штриха.
• второй пилот — запись, которая находится непосредственно перед пилотом. Она может отсутствовать, если пилот находится в начале второй строки.
• предыдущая запись — запись, которая находится перед другой, которая всё ещё находится в той же строке. (Так, в $\{a,b(1)c,d\}$, $c$ — предыдущая запись для $d$, но $a$ и $b$ — нет.)
• простой блок строки — первые $p$ записей этой строки.
• самолёт — пилот и все предыдущие записи. Если пилот находится во второй строке, самолёт также включает основной блок предыдущей строки.
• пассажиры — все записи в самолете, за исключением пилота и второго пилота (если он есть).

В остальном правила такие же, как и в линейной нотации массива. Никакого "правила порядка" не требуется, поскольку то, что мы изначально называли порядком, теперь является частью массива.

Вот краткий пример:

${\begin{matrix}\{3,3,3(1)2\}&=&\{3,\{3,2,3(1)2\},2(1)2\}\\&=&\{3,\{3,\{3,1,3(1)2\},2(1)2\},2(1)2\}\\&=&\{3,\{3,3,2(1)2\},2(1)2\}\\&=&\{3,\{3,\{3,2,2(1)2\},1(1)2\},2(1)2\}\\&=&\{3,\{3,\{3,2,2(1)2\}(1)2\},2(1)2\}\\&=&\{3,\{3,\{3,\{3,1,2(1)2\},1(1)2\}(1)2\},2(1)2\}\\&=&\{3,\{3,\{3,3(1)2\}(1)2\},2(1)2\}\\&=&\{3,\{3,\{3,3,3(1)1\}(1)2\},2(1)2\}\\&=&\{3,\{3,\{3,3,3\}(1)2\},2(1)2\}\\&=&\{3,\{3,3\uparrow \uparrow \uparrow 3(1)2\},2(1)2\}\\&=&\{3,\{\underbrace {3,\cdots ,3} _{3\uparrow \uparrow \uparrow 3}\},2(1)2\}\end{matrix}}$

Больше строк

Наименьший нетривиальный массив из трёх строк — $\{b,p(1)(1)2\}$, где вторая строка состоит только из единиц. Как и следовало ожидать, это равно $\{b,b,\ldots ,b,b(1)b,b,\ldots ,b,b\}$ с $p$ элементами в строке. Пилот теперь переместился в третью строку, и мы можем ввести второго пилота, как в $\{b,p(1)(1)1,2\}=\{b,b,\ldots ,b,b(1)b,b,\ldots ,b,b(1)\{b,p-1(1)(1)1,2\}\}$. Более трёх строк ведут себя примерно одинаково, поэтому давайте воспользуемся возможностью обобщить.

Нам нужно будет снова изменить наше определение самолёта:

• самолёт — пилот, все предыдущие записи и основные блоки всех предыдущих строк.

Когда пилот находится в первой строке, предыдущих строк нет, а самолёт — только предыдущие записи. Это решает проблему уродливого условного оператора в нашем предыдущем самолёте.

Теперь мы полностью определили нотацию массива в плоскости. Так что же там за строкой?

Три измерения

Плоскость. Мы будем использовать разделитель (2) для обозначения плоскостного разрыва. Наименьший двухплоскостной массив — $\{b,p(2)2\}=\{b,b,\ldots ,b,b(1)b,b,\ldots ,b,b(1)\ldots (1)b,b,\ldots b,b(1)b,b,\ldots ,b,b\}$ или массив $p \times p$ из $b$. (Мы также можем записать это как $p^{2}\&b$, подробнее об этом позже.) В конце концов мы достигнем нескольких плоскостей, которые в значительной степени решаются так, как и ожидалось.

Давайте определим это формально. Чтобы помочь в обобщении, нам нужно ввести несколько более абстрактных терминов. Один из них — структура, которая является либо записью, либо строкой, либо плоскостью. Теперь мы дадим общее определение простым блокам структур.

• Простым блоком строки являются первые $p$ записей, а простым блоком плоскости является первый $p \times p$ квадрат записей (или простые блоки первых $p$ строк).
• Предыдущая запись для X — запись перед X в той же строке. Предыдущая строка для X — строка перед X в той же плоскости.
• Самолёт — пилот, все предыдущие записи и простые блоки всех предыдущих структур.

Внимательно изучите последнее определение, потому что это основная часть того, как работает BEAF.

Четыре и более

Бесконечная линия плоскостей или трёхмерное пространство, по Бауэрсу, является областью. Четырёхмерное пространство — флюна. Символы для обозначения разрывов в областях и флюнах — (3) и (4) соответственно.

Обычно (n) обозначает разрыв в следующее n-мерное пространство. Запятая — сокращение от (0), поскольку запись — 0-мерное пространство. "Структура" — любое n-мерное пространство; мы будем обозначать nD структуру как $X^n$.

Давайте пересмотрим наши определения "структуры", "простого блока", "предыдущей структуры" и "самолёта".

• Структура — запись, строка, плоскость, область, флюна, 5-пространство, ... индуктивно это определяется как запись или бесконечный ряд структур.
• Первичный блок строки — первые $p$ записей; первичный блок плоскости — первый $p \times p$ квадрат; первичный блок области — первый $p\times p\times p$ куб и т. д. Индуктивно первичный блок строки — первые $p$ записей, а первичный блок структуры $X^n$ — первичные блоки первых $p$ $X^{n-1}$-структур.
• Предыдущая структура для A — $X^n$ перед A в той же $X^{n+1}$ структуре. В частности, предыдущая запись в A — запись перед A в той же строке, предыдущая строка в A — строка перед A в той же плоскости и т.д.
• Самолёт — пилот, все предыдущие записи и простые блоки всех предыдущих структур.

До сих пор мы полностью определили нотацию размерного массива. Повтор с полными правилами:

Нотация размерного массива

Определения:

• база $b$ — первая запись.
• штрих $p$ — вторая запись.
• пилот — первая не-1 запись после штриха.
• второй пилот — запись непосредственно перед пилотом. Она может отсутствовать, если пилот находится в начале строки.
• структура — это запись, строка, плоскость, область, поток, 5-пространство, ... Индуктивно это определяется как запись или бесконечная строка структур.
• первичный блок строки — первые $p$ записей; первичный блок плоскости — первый $p \times p$ квадрат; первичный блок области — первый $p\times p\times p$ куб и т.д. Индуктивно первичный блок строки — первые $p$ записей, а первичный блок структуры $X^n$ — первичные блоки первых $p$ $X^{n-1}$-структур.
• предыдущая структура для A — $X^n$ перед A в той же $X^{n+1}$ структуре. В частности, предыдущая запись в A — запись перед A в той же строке, предыдущая строка в A — строка перед A в том же самолёте и т.д.
• самолёт — пилот, все предыдущие записи и простые блоки всех предыдущих структур.
• пассажиры — все записи в самолёте, за исключением пилота и второго пилота (если он есть).

Правила:

1. Базовое правило. Если пилота нет (то есть все записи после штриха равны 1), то $v(A) = b^p$.
2. Правило штриха. Если штрих равен 1, то $v(A) = b$.
3. Катастрофическое правило. В противном случае...
   1. Если второй пилот существует, замените второго пилота копией исходного массива, но с штрихом, уменьшенным на единицу.
   2. Уменьшаем значение пилота на 1.
   3. Заменяем всех пассажиров на $b$.

(конец определения)

Ух ты! Это "расширенная нотация массива", разработанная Бердом и Бауэрсом. В оригинале использовалось семь правил, но мы применили современное определение BEAF, чтобы немного упростить его.

Массив или оператор

Оператор массива, обозначаемый как & (не путать с логическим оператором "и") возвращает массив, назначенный структуре слева от &, заполненный числом записей справа от &. Что это за структуры? Первые структуры — числа, и $n\ \&\ m=\{\underbrace {m,m,m,\cdots ,m,m,m} _{\text{n m's}}\}$. Структура над числами, так называемая X-структура, должна быть оценена как m. Итак, $X\ \&\ m=m\&\ m=\{m,m(1)2\}$.

Если мы хотим указать другое число, мы можем заключить его в скобки: $X\ \&\ a[b]=b\ \&\ a[b]$. Эта нотация не использовалась самим Бауэрсом.

Структуры над числами X — X+1,X+2,X+3,...,2X,2X+1,2X+2,2X+3,...,3X,4X,...,$X^2$ и т. д. X+m можно рассматривать как строку записей с m записями под ней, 2X — как две строки, 3X — как три строки, nX+m — как n строк записей с m записями под ней. Вот некоторые соответствия между нашими обозначениями выше и "массивом":

${\begin{matrix}1\ \&\ n&=&\{n\}=n\\2\ \&\ n&=&\{n,n\}=n^{n}\\3\ \&\ n&=&\{n,n,n\}=n\uparrow ^{n}n\\4\ \&\ n&=&\{n,n,n,n\}=n\underbrace {\{\{\cdots \{\{n\}\}\cdots \}\}} _{n\{\}'s}n\\m\ \&\ n&=&\{\underbrace {n,n,n,\cdots ,n,n,n} _{\text{m n's}}\}&=&\{n,m(1)2\}\\X\ \&\ n&=&\{\underbrace {n,n,n,\cdots ,n,n,n} _{\text{n n's}}\}&=&\{n,n(1)2\}\\X+1\ \&\ n&=&\{\underbrace {n,n,n,\cdots ,n,n,n} _{\text{n n's}}(1)n\}\\X+2\ \&\ n&=&\{\underbrace {n,n,n,\cdots ,n,n,n} _{\text{n n's}}(1)n,n\}\\X+3\ \&\ n&=&\{\underbrace {n,n,n,\cdots ,n,n,n} _{\text{n n's}}(1)n,n,n\}\\X+m\ \&\ n&=&\{\underbrace {n,n,n,\cdots ,n,n,n} _{\text{n n's}}(1)\underbrace {n,n,n,\cdots ,n,n,n} _{\text{m n's}}\}\\2X\ \&\ n&=&\{\underbrace {n,n,n,\cdots ,n,n,n} _{\text{n n's}}(1)\underbrace {n,n,n,\cdots ,n,n,n} _{\text{n n's}}\}\\3X\ \&\ n&=&\{\underbrace {n,n,n,\cdots ,n,n,n} _{\text{n n's}}(1)\underbrace {n,n,n,\cdots ,n,n,n} _{\text{n n's}}(1)\underbrace {n,n,n,\cdots ,n,n,n} _{\text{n n's}}\}\\mX\ \&\ n&=&\{\underbrace {X\ \&\ n(1)X\ \&\ n(1)X\ \&\ n(1)\cdots (1)X\ \&\ n(1)X\ \&\ n(1)X\ \&\ n} _{\text{m X's}}\}&=&\{n,m(2)2\}\\X^{2}\ \&\ n&=&\{\underbrace {X\ \&\ n(1)X\ \&\ n(1)X\ \&\ n(1)\cdots (1)X\ \&\ n(1)X\ \&\ n(1)X\ \&\ n} _{\text{n X's}}\}&=&\{n,n(2)2\}\end{matrix}}$

Как можно видеть, последние три примера можно упростить до $\{n,3(2)2\},\{n,m(2)2\}$ и $\{n,n(2)2\}$ соответственно. Здесь последняя "2" находится в следующей плоскости и отмечает начало трёхмерных массивов. К счастью, нам не нужно рисовать многомерные массивы в их естественном виде. Главным ключом к нему является использование полиномиальной формы: выражение $a_{1}X^{m}+a_{2}X^{m-1}+a_{3}X^{m-2}+\cdots +a_{m-1}X+a_{m}\&\ b[p]$ означает, что его массив образован $a_1$ секциями $X^{m}$ (m-мерный массив b), затем $a_2$ секциями $X^{m-1}$, затем $a_3$ секциями $X^{m-2}$ и т. д. Общее количество записей можно найти, заменив каждый X на p и решив как обычный полином. Например, $X^{100}+X^{99}\&\ 3[4]$ имеет $4^{100}+4^{99}$ записей.

Тетрационные массивы

До сих пор у нас была система на уровне $f_{\omega^{\omega^\omega}}$ для тех, кто знаком с БРИ. Следующий шаг не совсем очевиден, но он имеет решающее значение для продолжения системы.

$\{b,p(0,1)2\}$

Что это вообще значит? Это структура $X^X$, а первичный блок структуры $X^X$ — структура $p^p$ или гиперкуб $\underbrace {p\times p\times \cdots \times p\times p} _{p}$. Итак, это квадрат 2 на 2, или куб 3 на 3 на 3, или тессеракт 4 на 4 на 4 на 4 и т. д. Когда мы на самом деле решаем массив, мы можем заменить (0, 1) на (p) — например, $\{b,4(0,1)2\}=\{b,4(4)2\}$.

Техническое примечание: пространство, описываемое структурой $X^X$, называется размерной группой. В размерной группе каждая координата описывается строкой координат (тип порядка $\omega$), а не фиксированным конечным числом.

$\{b,p(1,1)2\}$

Это структура $X^{X+1}$; его основной блок — $p^{p+1}$. Обычно разделитель $(n,m)$ создаёт структуру $X^{mX+n}$. Это строка размерных групп.

Массивы линейных разделителей могут описывать всё возможные $X^{P}$, где $P$ — многочлен от $X$. (Здесь и далее в статье мы ограничиваем "полином" неотрицательными целыми коэффициентами.) Они делают это, предоставляя список коэффициентов от степени 0 до:

$(a_{0},a_{1},a_{2},a_{3},\ldots )$ описывает структуру типа $X^{a_{0}+a_{1}X+a_{2}X^{2}+a_{3}X^{3}+\cdots }$

Так, например, (0, 0, 1) описывает $X^{X^{2}}$ (размерную группу), а (1, 0, 6, 1) описывает $X^{1+6X^{2}+X^{3}}$. Вы заметите, что теперь по умолчанию используются нули, а не единицы; это одно из самых раздражающих свойств BEAF.

$\{b,p(0(1)1)2\}=\{b,p((1)1)2\}$

Конечно, у нас нет причин останавливаться на линейных массивах для разделителей. Эта структура — $X^{X^{X}}$, суперразмерная группа. (Векторы в суперразмерной группе имеют тип порядка $\omega^{\omega}$.) В общем случае для второй строки,

$(a_{00},a_{01},a_{02},\ldots (1)a_{10},a_{11},a_{12},\ldots )$ описывает структуру типа $X^{a_{00}+a_{01}X+a_{02}X^{2}+a_{03}X^{3}+\cdots +a_{10}X^{X}+a_{11}X^{X+1}+a_{12}X^{X+2}+\ldots }$.

Третья строка ((1)(1)1) описывает $X^{X^{2X}}$ (нет, мы ещё не достигли $X^{X^{X^{X}}}$!), а (n + 1)-я строка описывает $X^{X^{nX}}$. Вторая плоскость ((2)1) — $X^{X^{X^{2}}}$, вторая область ((3)1) — это $X^{X^{X^{3}}}$ и так далее и тому подобное. Наконец, мы достигаем $X^{X^{X^{X}}}=X\uparrow \uparrow 4$ во второй размерной группе, ((0, 1) 1). Внутренняя пара скобок описывает многочлен $P$ в $X$, а внешняя пара описывает $X^{X^{X^{P}}}$.

$\{b,p(((1)1)1)2\}$

Это $X^{X^{X^{X^{X}}}}=X\uparrow \uparrow 5$.

$\{b,p(((0,1)1)1)2\}$ описывает $X\uparrow \uparrow 6$

$\{b,p((((1)1)1)1)2\}$ описывает $X\uparrow \uparrow 7$

$\{b,p((((0,1)1)1)1)2\}$ описывает $X\uparrow \uparrow 8$

и т. д.

Пределом всего этого является структура $X\uparrow\uparrow X$. Если мы остановимся здесь, то получим тетрационную запись массива.

Попытка определения

Бауэрс никогда не удосужился формализовать тетрациональные массивы, но мы попробуем. Единственное, что нас сдерживает сейчас, — определение простых блоков, которое специально предназначено только для размерных массивов. Давайте рассмотрим наше текущее индуктивное определение:

• Простой блок записи — запись.
• Простой блок структуры $X^{n+1}$ — простые блоки её первых $p$ $X^n$-структур.

(Здесь есть небольшое изменение, но можно увидеть, что оно имеет минимальный эффект.) Это определение не говорит, что происходит, когда наша структура является структурой $X^X$, потому что это не структура вида $X^{n+1}$.

Давайте попробуем расширить это определение, чтобы разрешить все $X^{P}$ для полиномов степени 1 $P$.

• Первичный блок записи — запись.
• Первичный блок структуры $X^{P+1}$ — первичные блоки её первых $p$ $X^{P}$-структур, где $P$ — полином от $X$.
• Первичный блок структуры $X^{P+X}$ — первичный блок её первой $X^{P+p}$-структуры.

Это ломается в $X^{X^{2}}$, как и ожидалось, но здесь прослеживается закономерность.

• Первичный блок записи — запись.
• Первичный блок структуры $X^{P+1}$ — первичные блоки её первых $p$ $X^{P}$-структур, где $P$ — полином от $X$.
• Первичный блок структуры $X^{P+X}$ является первичным блоком её первой $X^{P+p}$-структуры.
• Первичный блок структуры $X^{P+X^{2}}$ является первичным блоком её первой $X^{P+pX}$-структуры.
• Первичный блок структуры $X^{P+X^{3}}$ является первичным блоком её первой $X^{P+pX^{2}}$-структуры.
• В общем случае первичный блок структуры $X^{P+X^{n+1}}$ является первичным блоком её первой $X^{P+pX^{n}}$-структуры.

Это работает до $X^{X^{X}}$. При таком раскладе мы никогда не доберемся до $X\uparrow\uparrow X$!

Вторая попытка

Давайте обобщим понятие "структура", чтобы помочь нашему определению.

• $0$ — структура.
• Если $\alpha$ — структура, то $X^{\alpha}$ — также структура.
• Если $\alpha$ и $\beta$ — структуры, то $\alpha + \beta$ — также структура.

Это допускает такие вещи, как $2X$ и $4X^{X}+X+1$, и работает вплоть до нашего предела $X\uparrow\uparrow X$. Кроме того, давайте определим предельную структуру как одну из форм $X^{\alpha}$ для $\alpha>0$ или $\alpha + \beta$ для $\alpha$ и $\beta$, являющихся предельными структурами, и структуру-последователя как одну из форм $\alpha+1$.

Теперь для структуры $\alpha$ и натурального числа $p$ мы рекурсивно определим простой блок $\alpha [p]$ $\alpha$:

• $0[p]=\{\}$
• $(\alpha +1)[p]=\alpha [p]\cup \{{\text{последняя запись }}\alpha +1\}$
• $X[p]=p$ и $X^{\alpha +1}[p]=X^{\alpha }p$
• $X^{\alpha }[p]=X^{\alpha [p]}$ тогда и только тогда, когда $\alpha$ является предельной структурой.
• $(X^{\alpha _{1}}+X^{\alpha _{2}}+\cdots +X^{\alpha _{k-1}}+X^{\alpha _{k}})[p]=(X^{\alpha _{1}}+X^{\alpha _{2}}+\cdots +X^{\alpha _{k-1}})[p]\cup X^{\alpha _{k}}[p])$ где $\alpha_k$ — наименьшее $\alpha_{i}$
• $X\uparrow \uparrow X[0]=1$ и $X\uparrow \uparrow X[p]=X^{X\uparrow \uparrow X[p-1]}$

Если вы запутались, пропустите это. Всё, что вам нужно, — интуитивное представление о том, как это работает.

Остался один последний шаг. Обратите внимание, как мы использовали слово "наименьший" в определении выше, но структуры — не числа, и мы ещё не определили порядок. Это просто:

• $\alpha <\alpha +X^{0}$
• $X^{\alpha }<X^{\beta }$ тогда и только тогда, когда $\alpha < \beta$
• $\alpha +\gamma <\beta +\gamma$ тогда и только тогда, когда $\alpha < \beta$

И мы закончили! Тетрационные массивы.

Но можем ли мы сделать это проще?

Как ординалы (передовое)

Некоторые из наших более опытных читателей могут заметить параллели с ординальными иерархиями. $X$ функционирует во многом как $\omega$, а наше определение простого блока похоже на определение иерархии Вайнера — мы выбрали нотацию $\alpha [p]$ не просто так. Мы разработали нотацию для ординалов до $\varepsilon_0$, что также является сильной стороной BEAF до этого момента. Кажется разумным переписать нашу нотацию с использованием ординалов, и мы так сделаем.

Мы определим массив как функцию $A:\varepsilon _{0}\mapsto \mathbb {N} _{+}$, где количество выходов больше 1 конечно. (Это предотвращает бесконечные массивы типа {6, 6, 6, ...}.) Пусть $b=A(0)$, $p=A(1)$, $\pi =\min\{\alpha >1:A(\alpha )>1\}$ (позиция пилота) и $\kappa =\pi -1$ (позиция второго пилота).

Определим простой блок $\Pi (\alpha )$:

• $\Pi (0)=\{\}$
• $\Pi (\alpha +1)=\{\alpha \}\cup \Pi (\alpha )$
• $\Pi (\alpha )=\Pi (\alpha [p])$ если $\alpha$ — предельный ординал

(Это очень похоже на медленнорастущую иерархию.) Определим пассажиров как $S=\Pi (\pi )\backslash \{\pi ,\kappa \}$.

И три правила:

1. Основное правило. Если $\pi$ не существует, $v(A) = b^p$.
2. Правило штриха. Если $p = 1$, $v(A) = b$.
3. Катастрофическое правило. Определим $A'$ как $A$ со следующими изменениями:
   • Определим $B$ как $A$, но с $B(1)=p-1$.
   • Если $\kappa$ существует, $A'(\kappa ):=v(B)$.
   • $A'(\pi )=A(\pi )-1$.
   • $A(\sigma ):=b$ для $\sigma \in S$.
   • $v(A)=v(A')$.

Хотя это и менее доступно, это гораздо более простое определение, чем выше!

Ещё одно; давайте определим некоторые фундаментальные последовательности для ординалов ниже $\varepsilon_0$.

• $\omega^{\alpha}[n]=\omega^{\alpha[n]}$ для предельных ординалов $\alpha$
• $\omega^{\alpha+1}[n]=\omega^{\alpha}n$
• $(\omega ^{\alpha _{1}}+\omega ^{\alpha _{2}}+\cdots +\omega ^{\alpha _{k}})[n]=\omega ^{\alpha _{1}}+\omega ^{\alpha _{2}}+\cdots +\omega ^{\alpha _{k}}[n]$ где $\alpha_1\geq\alpha_2\geq\cdots\geq\alpha_k$
• $\omega \uparrow \uparrow 0=1$
• $(\omega \uparrow \uparrow (\alpha +1))[n]=\omega ^{\omega \uparrow \uparrow \alpha }[n]$

Обратите внимание, что эта система плохо определена и используется только для грубого наброска поведения. Мы добавили определение $\omega \uparrow \uparrow n$, чтобы гарантировать, что мы правильно отражаем иерархию $X$ Бауэрса. Действительно, после $\varepsilon_0$ фундаментальные последовательности немного отклоняются от обычных.

Пентационные массивы

Пентационные массивы — своего рода взрыв мозга. Но самое худшее, что до сих пор не придумано никаких нотаций для их поддержки! Бауэрс так и не потрудился составить их; он просто использовал оператор массива.

Помните оператор массива?

$a\&b=\{b,a(1)2\}$

Мы оставили его позади в эпоху однострочных массивов. Оказывается, у & есть расширение, которое позволяет использовать его за пределами этого уровня.

$a^{2}\&b=\{b,a(2)2\}$

Нетрудно увидеть, что правая часть — массив a на a из b или массив a² из b. Обратите внимание, что выражение "$a^2$" не должно быть решено первым; скорее, это план для измерений массива.

$a^{k}\&b=\{b,a(k)2\}$

В общем случае оператор массива позволяет нам указывать много измерений и даже тетрационные массивы, такие как этот:

$a^{a^{a}}\&b=a\uparrow \uparrow 3\&b=\{b,a((1)1)2\}$

Для тех, кто понял ординальное определение выше, мы можем формально определить $f(a)\&b=\{0\mapsto b,1\mapsto a,f(\omega )\mapsto 2\}$.

Наименьший пентационный массив:

$(a\uparrow \uparrow a)\&b=\{b,a(???)2\}$

Для этого массива нет обозначения (структура $X\uparrow\uparrow X$), но его, безусловно, можно определить с помощью ординалов, где $\omega \uparrow \uparrow \omega =\varepsilon _{0}$ с использованием фундаментальной последовательности $\varepsilon _{0}[n]=\omega \uparrow \uparrow n$. Мы на минутку извинимся перед читателями, которые ещё не поняли ординалы. Перейдите сразу к легиональным массивам, если вы один из них.

На этом этапе вы можете задаться вопросом, что такое $X \uparrow \uparrow \uparrow X$, но мы не можем перейти к этому, пока не определим $X\uparrow \uparrow (X2)$ или фундаментальную последовательность "$\omega \uparrow \uparrow (\omega 2)$". Наше текущее намерение $\uparrow\uparrow$ над ординалами, которое плохо определено из-за отсутствия фиксированного определения, сделало бы $\omega \uparrow \uparrow (\omega 2)=\omega \uparrow \uparrow \omega$, поэтому нам нужно это исправить.

Если мы можем изменить наше определение на $\omega \uparrow \uparrow (1+\alpha )=\omega ^{\omega \uparrow \uparrow \alpha }$, мы можем ясно видеть, что $\omega \uparrow \uparrow (1+\omega )=\omega \uparrow \uparrow \omega$ является неподвижной точкой функции $\alpha\mapsto\omega^{\alpha}$.

Если мы можем определить $\uparrow\uparrow$ таким образом, то было бы естественно ожидать, что $\omega \uparrow \uparrow (\omega 2)$ должна быть следующей неподвижной точкой, т. е. $\varepsilon_1$. Одно особенно ясное определение $\varepsilon_1$ — предел $\varepsilon _{0},\varepsilon _{0}^{\varepsilon _{0}},\varepsilon _{0}^{\varepsilon _{0}^{\varepsilon _{0}}},\ldots$, так почему бы не сделать $\varepsilon _{1}=\varepsilon _{0}\uparrow \uparrow \omega =(\omega \uparrow \uparrow \omega )\uparrow \uparrow \omega$? Сначала это кажется немного странным, так как в общем случае $a\uparrow \uparrow a2\neq (a\uparrow \uparrow a)\uparrow \uparrow a$. Ординалы работают загадочным образом.

Следующая неподвижная точка — $\omega \uparrow \uparrow (\omega 3)=\varepsilon _{1}\uparrow \uparrow \omega =\varepsilon _{2}$, и в общем случае $\omega \uparrow \uparrow (\omega n)=\varepsilon _{n-2}\uparrow \uparrow \omega =\varepsilon _{n-1}$ для конечного $n > 0$. Понятно, что предел всех этих массивов равен $\omega \uparrow \uparrow (\omega ^{2})=\varepsilon _{\omega }$.

Бла-бла-бла. Ничего особенно интересного здесь нет, пока $\varepsilon _{\varepsilon _{0}}=\omega \uparrow \uparrow (\omega \uparrow \uparrow \omega )=\omega \uparrow \uparrow \uparrow 3$ и $\varepsilon _{\varepsilon _{\varepsilon _{0}}}=\omega \uparrow \uparrow \uparrow 4$. Тройные стрелки весьма многообещающие, и действительно предел всего этого - $\zeta _{0}=\omega \uparrow \uparrow \uparrow \omega$. Бум. Готово.

Формальное определение

Хорошие новости: формализация этого процесса сводится всего лишь к определению некоторых функций над порядковыми числами и фундаментальными последовательностями, которые они создают. Стрелочная нотация не является частью стандартной порядковой арифметики, поэтому нам придется определить ее самостоятельно:

• $\alpha \uparrow \uparrow 0=1$
• $\alpha \uparrow \uparrow (n+1)=\alpha ^{\alpha \uparrow \uparrow n}$ для $n<\omega$
• $\alpha \uparrow \uparrow \beta =\bigcup \{\gamma <\beta :\alpha \uparrow \uparrow \gamma \}$ для предельных порядковых чисел $\beta$
• $\alpha \uparrow \uparrow (\beta +\omega )=\lim\{(\alpha \uparrow \uparrow \beta ),(\alpha \uparrow \uparrow \beta )^{(\alpha \uparrow \uparrow \beta )},(\alpha \uparrow \uparrow \beta )^{(\alpha \uparrow \uparrow \beta )^{(\alpha \uparrow \uparrow \beta )}},...\}$ для $\beta \geq \omega$
• $(\alpha \uparrow \uparrow \beta )[n]=\alpha \uparrow \uparrow \beta [n]$

Обратите внимание, что этот гипероператор и система фундаментальных последовательностей все еще плохо определены, и, следовательно, не дают никакого формального определения вообще. Мы просто грубо объясняем, как определить нужный оператор для удобства читателя.

Дальнейшие массивы, предшествующие легиональным

Мы закончили последний раздел с помощью $\zeta _{0}=\omega \uparrow \uparrow \uparrow \omega$. Мы также можем написать $\omega \uparrow \uparrow \uparrow \omega =\{\omega ,\omega ,3\}$, и что мешает нам определить $\{\omega ,\omega ,4\}$? Или $\{\omega ,\omega ,1,2\}$? Или $\{\omega ,\omega (0,1)2\}$?

Единственным препятствием является формальность: нам нужно определить BEAF для ординалов. Начнём со стрелочной нотации для конечного числа стрелок:

• $\alpha\uparrow\beta=\alpha^\beta$
• $\alpha \uparrow ^{k}0=1$
• $\alpha \uparrow ^{k+1}(n+1)=\alpha \uparrow ^{k}(\alpha \uparrow ^{k+1}n)$ для $n<\omega$
• $\alpha \uparrow ^{k}\beta =\sup\{\gamma <\beta :\alpha \uparrow ^{k}\gamma \}$ для предельных ординалов $\beta$
• $\alpha \uparrow ^{k}(\beta +\omega )=\lim\{(\alpha \uparrow ^{k}\beta ),(\alpha \uparrow ^{k}\beta )\uparrow ^{k-1}(\alpha \uparrow ^{k}\beta ),(\alpha \uparrow ^{k}\beta )\uparrow ^{k-1}(\alpha \uparrow ^{k}\beta )\uparrow ^{k-1}(\alpha \uparrow ^{k}\beta ),...\}$ для $\beta \geq \omega$
• $(\alpha \uparrow ^{k}\beta )[n]=\alpha \uparrow ^{k}\beta [n]$

Нетрудно заметить, что ординальная стрелочная нотация похожа на функцию Веблена, а различия в основном заключаются в фундаментальных иерархиях. Аналогично функции Веблена, $\alpha \mapsto \omega \uparrow ^{k+1}(\omega +\alpha )$ перечисляет неподвижные точки $\alpha \mapsto \omega \uparrow ^{k}\alpha$.

Уже само это определение слегка раздражает из-за огромного количества правил. В любом случае, давайте попробуем $k=\omega$:

• $\alpha \uparrow ^{\omega }\beta =\sup\{k<\omega :\alpha \uparrow ^{k}\beta \}$
• $(\alpha \uparrow ^{\omega }\beta )[n]=\alpha \uparrow ^{n}\beta$

Обратите внимание, что $\omega \uparrow ^{\omega }\omega =\varphi _{\omega }(0)$. Наш существующий фреймворк работает для последующих ординалов $k$, но здесь нам нужны некоторые ограничения:

• $\alpha \uparrow ^{\kappa }\beta =\sup\{\gamma <\kappa :\alpha \uparrow ^{\gamma }\beta \}$
• $(\alpha \uparrow ^{\kappa }\beta )[n]=\alpha \uparrow ^{\kappa [n]}\beta$

Собираем всё вместе:

• $\alpha\uparrow\beta=\alpha^\beta$
• $\alpha \uparrow ^{\kappa }0=1$
• $\alpha \uparrow ^{\kappa +1}(n+1)=\alpha \uparrow ^{\kappa }(\alpha \uparrow ^{\kappa +1}n)$ для $n<\omega$
• $\alpha \uparrow ^{\kappa }(\beta +1)=(\alpha \uparrow ^{\kappa }\beta )\uparrow ^{\kappa }\alpha$ для $\beta \geq \omega$
• $\alpha \uparrow ^{\kappa }\beta =\sup\{\gamma <\kappa :\alpha \uparrow ^{\gamma }\beta \}$ для предельных порядковых чисел $\kappa$
• $\alpha \uparrow ^{\kappa }\beta =\sup\{\gamma <\beta :\alpha \uparrow ^{\kappa }\gamma \}$ для предельных порядковых чисел $\beta$
• $(\alpha \uparrow ^{\kappa }\beta )[n]=\alpha \uparrow ^{\kappa [n]}\beta$ для предельных ординалов $\kappa$
• $(\alpha \uparrow ^{\kappa }\beta )[n]=\alpha \uparrow ^{\kappa }\beta [n]$ для предельных ординалов $\beta$

Это определение работает нормально, но последние две пары правил имеют идентичные условия. В случае $(\omega \uparrow ^{\omega }\omega )[n]$ мы бы предпочли $\omega \uparrow ^{n}\omega$, поэтому если $\kappa$ и $\beta$ являются предельными ординалами, мы должны сначала сосредоточиться на $\kappa$.

А пока давайте запишем это как трёхэлементную нотацию массива. Это обычная трёхэлементная нотация с некоторыми предельными ординальными случаями. Для упрощения мы не позволим ни одной записи быть равной 0, как в обычной нотации массива.

• $\{a,b,1\}=a^{b}$
• $\{a,1,c\}=a$
• $\{a,b+1,c+1\}=\{a,\{a,b,c+1\},c\}$ для $b<\omega$
• $\{a,b+1,c\}=\{\{a,b,c\},a,c\}$ для $b\geq \omega$
• $\{a,b,c\}=\sup\{x<c:\{a,b+1,x\}\}$ для $c\in {\text{Lim}}$
• $\{a,b,c+1\}=\sup\{x<b:\{a,b+1,c+1\}\}$ для $b\in {\text{Lim}}$
• $\{a,b,c\}[n]=\{a,b,c[n]\}$ для $c\in {\text{Lim}}$
• $\{a,b,c+1\}[n]=\{a,b[n],c+1\}$ для $b\in {\text{Lim}}$

Где ${\text{Lim}}$ — класс всех предельных ординалов.

Мы также можем удалить четвёртое и пятое правила, если определим их как пределы шестого и седьмого правил соответственно.

Теперь для четырёх записей:

• $\{a,b,1,1\}=a^{b}$
• $\{a,1,c,d\}=a$
• $b<\omega :$
  • $\{a,b+1,1,d+1\}=\{a,\{a,b,1,d+1\},1,d\}$
  • $\{a,b+1,c+1,d\}=\{a,\{a,b,c+1,d\},c,d\}$
• $b>\omega :$
  • $\{a,b+1,c,d\}=\{\{a,b,c,d\},a,c,d\}$
• $\{a,b,c,d\}[n]=\{a,b,c,d[n]\}$ для $d\in {\text{Lim}}$
• $\{a,b,c,d+1\}[n]=\{a,b,c[n],d+1\}$ для $c\in {\text{Lim}}$
• $\{a,b,c+1,d+1\}[n]=\{a,b[n],c+1,d+1\}$ для $b\in {\text{Lim}}$

Отсюда легко сделать обобщение.

Линейная ординальная нотация массива

Определения не изменяются, первая запись — основание $b$, вторая запись — штрих $p$, первая запись, не равная 1, после штриха — пилот, запись перед ним — второй пилот, а пассажиры — все записи до второго пилота. Кроме того, мы определим ограничитель $l$ как последний предельный ординал после основания; он может не существовать, если есть только последующие ординалы от штриха.

Все записи находятся между нулём и $\omega_1$ включительно.

1. Основное правило. Если пилота нет, $v(A) = b^p$.
2. Правило штриха. Если $p = 1$, $v(A) = b$.
3. Катастрофическое правило. Если ограничителя нет и $p<\omega$...
   1. Заменить второго пилота копией массива с штрихом, уменьшенным на 1.
   2. Уменьшить пилота на 1. (Пилот должен быть последовательным ординалом или конечным кардиналом, иначе будет ограничитель.)
   3. Заменить всех пассажиров на $b$.
4. Бесконечное катастрофическое правило. Если ограничителя нет и $p\geq \omega$...
   1. Заменить базу копией массива с штрихом, уменьшенным на 1. (Первым числом должен быть последовательный ординал, иначе будет ограничитель.)
   2. Установить штрих в исходное значение $b$.
5. Правило предела. Иначе...
   1. Пусть $v(A)[n]$ будет значением массива с ограничителем, измененным на $l[n]$.
   2. $v(A)=\sup\{1\leq n<\omega :v(A)[n]\}$.

(конец определения)

Конечно, у нас нет причин останавливаться на линейных массивах. Наш тетрационный BEAF легко расширяется до ординалов; нам просто нужно добавить правило предела и расширить область $A$ с $\varepsilon_0$ до $\omega_1$, первого ординала без фундаментальной последовательности со счётной длиной. Мы запретим себе просто вставлять любой большой счётный ординал, поскольку мы строим с нуля и используем BEAF для определения ординалов по мере продвижения.

Кстати, какие ординалы мы определили? Довольно много.

• $\Gamma _{0}=\{\omega ,\omega ,1,2\}$ (расширяющиеся массивы)
• $\varphi (1,0,0,0)=\psi _{0}(\Omega ^{\Omega ^{2}})=\{\omega ,\omega ,1,1,2\}$ (относительно функции Бухгольца)
• ${\text{МОВ}}=\psi _{0}(\Omega ^{\Omega ^{\omega }})=\{\omega ,\omega (1)2\}$ (также относительно функции Бухгольца)
• ${\text{БОВ}}=\psi _{0}(\Omega ^{\Omega ^{\Omega }})=\{\omega ,\omega ,2(1)2\}$ (то же самое)
• ${\text{ОБГ}}=\psi _{0}(\Omega _{2})=\{\omega ,\omega (\varepsilon _{0})2\}$

Пределом нашей нотации на данный момент является $\psi_0(\Omega_{\omega})$, то есть ординал Бухгольца. Это настоящее достижение!

Легиональные массивы

Спасибо вам, неординальные читатели, за то, что ждали так долго! До сих пор у нас было то, что можно было бы назвать "BEAF, предшествующим легионам". Бауэрс называл всё до этого момента "L-пространством".

Мы снова воскрешаем массив оператора &. По мере того, как наши нотации становятся всё более и более быстрорастущими, также становится и &: к настоящему времени у нас есть хорошее определение для таких вещей, как {3, 3, 3}&3 (триакулус), пентационный массив. Оператор массива всегда сможет диагонализировать наши самые быстрорастущие нотации.

Обратите внимание, что мы также можем записать триакулус как (3&3)&3, и мы сделаем оператор левоассоциативным, чтобы избавиться от скобок, как в 3&3&3. Это естественным образом создаёт оператор, b♦p = b&b&...&b&b p раз. Этот оператор выражает предел BEAF до легионов; это самая мощная функция, которую мы определили до сих пор. Обратите внимание, что ♦ не использовался самим Бауэрсом.

$b{\text{♦}}p$ немного напоминает нам $b^{p}$, поэтому давайте воспользуемся тем же трюком, который мы использовали в двухстрочных массивах. Мы можем сделать этот "BEAF, предшествующий легионам, второго порядка", переопределив базовое правило как $b{\text{♦}}p$.

Как мы делали с двухстрочной нотацией массива, мы могли бы продолжать расширять более высокий порядок BEAF, предшествующего легионам, пока нам не понадобится объединить порядок в массив. Мы перейдём к сути и немедленно поместим порядок в массив.

$\{b,p/2\}=b{\text{♦}}p$

Разделитель слэш обозначает новый тип пространства, называемый пространством легиона. Пилот 2 находится во втором легионе, так же, как мы переместили пилота во вторую строку в нотации массива в плоскости. Первичный блок легиона — $b{\text{♦}}p$, например, $\{b,p/3\}=\{b{\text{♦}}p/2\}$.

$\{b,p/1,2\}=\{b{\text{♦}}p/\{b,p-1/2\}\}$

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

$\{b,p/1/2\}=\{b{\text{♦}}p/b{\text{♦}}p\}$

Мы также можем добавить более двух легионов...

$\{b,p(/1)2\}=\{b{\text{♦}}p/b{\text{♦}}p/\ldots /b{\text{♦}}p/b{\text{♦}}p\}$ с $p$ легионами

$\{b,p(/0,1)2\}=\{b{\text{♦}}p/b{\text{♦}}p/\ldots /b{\text{♦}}p/b{\text{♦}}p\}$ где легионы образуют $p^p$ структуру

...а сами легионы могут принимать размерные структуры любой размерности.

Другое обозначение для $\{b,p(/1)2\}=\{b{\text{♦}}p/b{\text{♦}}p/\ldots /b{\text{♦}}p/b{\text{♦}}p\}$ — $p\&\&b$, или p легионарных массив b. Аналогично, $\{b,p(/(1)1)2\}=p^{p}\&\&b$, поэтому оператор && работает аналогично &, но с легионами вместо записей. Мы будем использовать b♦♦p для обозначения b&&b&&..&&b&&b p раз, и мы введём "легион-легиональный пробел" с помощью разделителя $//$.

$\{b,p//2\}=b{\text{♦♦}}p=b\&\&b\&\&\ldots \&\&b\&\&b$

$\{b,p(//1)2\}=\{b{\text{♦♦}}p//b{\text{♦♦}}p//\ldots //b{\text{♦♦}}p//b{\text{♦♦}}p\}=p\&\&\&b$

$\{b,p/^{n}2\}=b{\text{♦}}^{n}p=b\&^{n}b\&^{n}\ldots \&^{n}b\&^{n}b$

$\{b,p(/^{n}1)2\}=\{b{\text{♦}}^{n}p/^{p}b{\text{♦}}^{n}p/^{p}\ldots /b{\text{♦}}^{n}p/^{p}b{\text{♦}}^{n}p\}=p\&^{n+1}b$

Расширение простое.

$\{b,p(1)/2\}=\{b,p/^{p}2\}=b(1)\&p$

$\{b,p///(1)///(1)///2\}$

Почему бы не дать легионам многомерную структуру? Проблема в том, что нам нужно это определить. Пусть L будет структурой легиона, которая больше всех структур до, но не включая легионы. (Таким образом, L является легионом в том же смысле, что X является строкой.) Мы могли бы сказать, что L = {X, X / 2}, но это неудобное определение. В любом случае, первичный блок легиона — $b{\text{♦}}p$.

Два легиона — структура $2L$, ряд легионов — структура $XL$, легион легиональный // — структура $L^2$. Отсюда мы можем поместить L в массив так же, как мы писали такие вещи, как {X, X, X}. Мы можем написать $\{L,L\}$ или $\{L,L,L\}$ или $\{L,X(1)2\}=X\&L$. К сожалению, к настоящему времени у нас нет нотаций для разделителей, но Бауэрс предоставил $\{L,L\}_{b,p}$ (скажем), чтобы обозначить структуру $\{L,L\}$, решённую с b в качестве основания и p в качестве штриха.

Мы продолжаем создавать из L во всё большие и большие массивы, пока не достигнем ориентира $\{L,L/2\}$, или лугионального пространства. Бауэрс также записывает этот $L2$ с помощью разделителя \ и оператора $a$@$b$, или a леггиатического массива b.

Формализация

Мы быстро догоним легиональную нотацию массива с ординалами. Во-первых, мы заметим, что оператор массива состоит из трех частей: основания, штриха и типа структуры. Например, $3\&4$ имеет основание 4, штрих 3 и тип структуры X, а $3\uparrow \uparrow \uparrow 4\&5$ имеет основание 5, штрих 3 и тип структуры $X\uparrow \uparrow \uparrow 4$. Небольшое злоупотребление Бауэрсом обозначениями можно исправить с помощью оператора массива с тремя аргументами:

$\lambda (b,p,\xi )=\{(0,b),(1,p),(\xi ,2)\}$

То есть основание $b$, штрих $p$ и число 2 в позиции $\xi$. Обычно $\xi$ является предельным ординалом, но наша новая функция допускает любой $\xi >1$.

Ординал для пространства легионов равен $\vartheta (\Omega _{\omega })=\{\omega ,\omega /2\}$, а его фундаментальная последовательность равна $\vartheta (\Omega _{\omega })[1]=\omega ,\,\vartheta (\Omega _{\omega })[2]=\lambda (\omega ,\omega ,\omega ),\,\vartheta (\Omega _{\omega })[3]=\lambda (\omega ,\omega ,\lambda (\omega ,\omega ,\omega ))$, и так далее. Это определяет основной блок структуры $\vartheta(\Omega_{\omega})$, как определённый ранее.

Внешние ссылки

• Третья линейная запись
• Четвёртая линейная запись
• Самые большие числа в мире, часть первая @ Вещи, представляющие интерес (линейные массивы)
• Самые большие числа в мире, часть вторая @ Вещи, представляющие интерес (массивы в плоскости)
• Линейная нотация массива