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

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

Правила

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

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

Примеры

Массив включает 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\}\}\}=\underset{\text{100 десяток}}{\underbrace{10^{10^{10^{{\cdots }^{10^{10}}}}}}}=10\uparrow \uparrow 100$ (применено правило 5)
• $\{10,100,3\}=\{10,\{10,99,3\},2\}=\{10,\{10,\{10,98,3\},2\},2\}=\begin{array}{ccc}& & \underbrace{10^{10^{10^{{\cdots }^{10^{10}}}}}}\\ & & \underbrace{10^{10^{10^{{\cdots }^{10^{10}}}}}}\\ & & \underbrace{⋮}\\ & & \underbrace{10^{10^{10^{{\cdots }^{10^{10}}}}}}\\ & & \text{10 десяток}\end{array}\}\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\}\}\}=\begin{array}{ccc}& & \underbrace{10\uparrow \uparrow \cdots \uparrow \uparrow 10}\\ & & \underbrace{10\uparrow \uparrow \cdots \uparrow \uparrow 10}\\ & & \underbrace{⋮}\\ & & \underbrace{10\uparrow \uparrow \cdots \uparrow \uparrow 10}\\ & & \text{10 стрелок}\end{array}\}\text{100 }\approx 10\to 10\to 100\to 2$ (применено правило 4)

и это уже больше числа Грэма (само число Грэма находится где-то между {3,64,1,2} и {3,65,1,2}).

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

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

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

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

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