Массивная нотация Бауэрса

Массивная нотация (англ. Array notation) — нотация для записи больших чисел, предложенная американским математиком Джонатаном Бауэрсом (Jonathan Bowers) в 2002 году. Данная нотация является обобщением предшествующей 4-аргументной нотации (известной как операторы Бауэрса) для произвольного числа аргументов.

Правила

Нотация Бауэрса для линейного массива включает следующие правила:

1. $\{a\}=a$ и $\{a,b\}=a^{b}$
2. $\{a,b,c,\ldots ,n,1\}=\{a,b,c,\ldots ,n\}$
3. $\{a,1,b,c,\ldots ,n\}=a$
4. $\{a,b,1,\ldots ,1,c,d,\ldots ,n\}=\{a,a,a,\ldots ,\{a,b-1,1,\ldots ,1,c,d,\ldots ,n\},c-1,d,\ldots ,n\}$.
5. Если правила 1—4 не применяются, $\{a,b,c,d,\ldots ,n\}=\{a,\{a,b-1,c,d,\ldots ,n\},c-1,d,\ldots ,n\}$

Можно определить и более общие правила, но для этого нужно ввести понятия:

1. База - первый элемент в массиве.
2. Основание - второй элемент в массиве.
3. Пилот - первый элемент после основания в массиве, больший 1.
4. Копилот - элемент, сразу предшествующий пилоту, может отсутствовать, если пилот - первый на своей строке.
5. Простой блок структуры - первые p элементов в строке, первые p*p элементов в плоскости и так далее.
6. Пассажиры - это все предшествующие элементы на строке и простые блоки всех структур.

Более общие правила работают для всех массивов - их только три:

1. Правило основания: если основание равно 1, массив приравнивается базе;
2. Правило пилота: если все элементы, кроме двух первых, равны 1, массив равен базе в степени основания;
3. Иначе:
   1. уменьшить пилот на единицу,
   2. приравнять копилот (если есть) копией массива с основанием, уменьшенным на 1;
   3. приравнять все пассажиры базе.

Примеры

Массив включает 2 элемента

• $\{10,100\}=10^{100}=10\uparrow 100$ (применено правило 1)

Массив включает 3 элемента

• $\{10,100,1\}=\{10,100\}$ (применено правило 2)
• $\{10,100,2\}=\{10,\{10,99,2\}\}=\{10,\{10,\{10,98,2\}\}\}=\underbrace {10^{10^{10^{\cdots ^{10^{10}}}}}} _{\text{100 десяток}}=10\uparrow \uparrow 100$ (применено правило 5)
• $\{10,100,3\}=\{10,\{10,99,3\},2\}=\{10,\{10,\{10,98,3\},2\},2\}=\left.{\begin{matrix}&&\underbrace {10^{10^{10^{\cdots ^{10^{10}}}}}} \\&&\underbrace {10^{10^{10^{\cdots ^{10^{10}}}}}} \\&&\underbrace {\quad \quad \;\;\vdots \quad \quad \;\;} \\&&\underbrace {10^{10^{10^{\cdots ^{10^{10}}}}}} \\&&{\text{10 десяток}}\end{matrix}}\right\}{\text{100 }}=10\uparrow \uparrow \uparrow 100$ (применено правило 5)

В общем случае для трехэлементного массива верно $\{a,b,m\}=a\uparrow ^{m}b$ в соответствии с нотацией Кнута.

Массив включает 4 элемента

• $\{10,100,1,1\}=\{10,100\}$ (применено правило 2)
• $\{10,100,1,2\}=\{10,10,\{10,99,1,2\}\}=\{10,10,\{10,10,\{10,98,1,2\}\}\}=\left.{\begin{matrix}&&\underbrace {10\uparrow \uparrow \cdots \uparrow \uparrow 10} \\&&\underbrace {10\uparrow \uparrow \cdots \uparrow \uparrow 10} \\&&\underbrace {\qquad \ \;\;\vdots \qquad \;\;} \\&&\underbrace {10\uparrow \uparrow \cdots \uparrow \uparrow 10} \\&&{\text{10 стрелок}}\end{matrix}}\right\}{\text{100 }}\approx 10\rightarrow 10\rightarrow 100\rightarrow 2$ (применено правило 4)

и это уже больше числа Грэма (по Сайбиану это число называется "корпорал").

• $\{10,100,2,2\}=\{10,\{10,99,2,2\},1,2\}=\{10,\{10,\{10,98,2,2\},1,2\},1,2\}\approx 10\rightarrow 10\rightarrow 100\rightarrow 3$ (применено правило 5)
• $\{10,100,m,2\}\approx 10\rightarrow 10\rightarrow 100\rightarrow (m+1)$

В общем случае для четырёхэлементного массива верно

$\{a,b,c,d\}>\underbrace {a\rightarrow a\rightarrow \cdots a\rightarrow a} _{d-1{\text{ стрелок}}}\rightarrow (b-1)\rightarrow (c+1)$

в соответствии с нотацией Конвея.

Таким образом, если массив Бауэрса, включающий 3 элемента, имеет мощность нотации Кнута (предел $\omega$), то четырёхэлементный массив имеет уже мощность нотации Конвея (предел $\omega ^{2}$), и так далее с добавлением каждого нового элемента. Нотация Бауэрса для линейного массива, включающего конечное число элементов, имеет предел $\omega ^{\omega }$ в терминологии быстрорастущей иерархии.

Можно пойти дальше, в размерные массивы:

Массив включает 2 строки

• $\{10,3(1)2\}=\{10,10,10\}$ (применено правило 3)

• $\{10,3(1)1,2\}=\{10,10,10(1){10,2(1)2}\}$ (применено правило 3)

Так же поступают массивы с любым количеством строчек в любом количестве размерностей.

Бауэрс идёт дальше и определяет "тризмерные", "четырезмерные" и так далее массивы. Это - тетрациональные массивы. Верхний предел их роста -$\epsilon ₀$, что сравнимо с гидрой и последовательностями Гудштейна.