Русская Википедия:Массивная нотация Бауэрса
Массивная нотация Бауэрса (Шаблон:Lang-en) — нотация для записи больших чисел, предложенная американским математиком Джонатаном Бауэрсом (Jonathan Bowers) в 2002 году. Данная нотация является обобщением предшествующей 4-аргументной нотации (известной как Шаблон:Iw[1]) для произвольного числа аргументов[2].
Правила
Нотация Бауэрса для линейного массива включает следующие правила[3][4]:
- <math>\{a\} = a</math> и <math>\{a,b\} = a^b</math>
- <math>\{a,b,c,\ldots,n,1\} = \{a,b,c,\ldots,n\}</math>
- <math>\{a,1,b,c,\ldots,n\} = a</math>
- <math>\{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\}</math>.
- Если правила 1—4 не применяются, <math>\{a,b,c,d,\ldots,n\} = \{a,\{a,b-1,c,d,\ldots,n\},c-1,d,\ldots,n\}</math>
Примеры
- Массив включает 2 элемента
- <math>\{10,100\} = 10^{100}=10\uparrow100</math> (применено правило 1)
- Массив включает 3 элемента
- <math>\{10,100,1\} = \{10,100\}</math> (применено правило 2)
- <math>\{10,100,2\} = \{10,\{10,99,2\}\}= \{10,\{10,\{10,98,2\}\}\}=\underbrace{10^{10^{10^{\cdots^{10^{10}}}}}}_{\text{100 десяток}}=10\uparrow\uparrow100</math> (применено правило 5)
- <math>\{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\uparrow100</math> (применено правило 5) В общем случае для трёхэлементного массива верно <math>\{a,b,m\} = a\uparrow^m b</math> в соответствии с нотацией Кнута.
- Массив включает 4 элемента
- <math>\{10,100,1,1\}=\{10,100\} </math> (применено правило 2)
- <math>\{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</math> (применено правило 4)
- и это уже больше числа Грэма (само число Грэма находится где-то между {3,64,1,2} и {3,65,1,2}).
- <math>\{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</math> (применено правило 5)
- <math>\{10,100,m,2\} \approx 10 \rightarrow 10 \rightarrow 100 \rightarrow (m+1)</math>
В общем случае для четырёхэлементного массива верно
- <math>\{a,b,c,d\}>\underbrace{a \rightarrow a \rightarrow \cdots a \rightarrow a}_{d-1 \text{ стрелок}}\rightarrow (b-1) \rightarrow (c+1) </math>
в соответствии с нотацией Конвея.
Таким образом, если массив Бауэрса, включающий 3 элемента, имеет мощность нотации Кнута (предел <math>\omega</math>), то четырёхэлементный массив имеет уже мощность нотации Конвея (предел <math>\omega^2</math>), и так далее с добавлением каждого нового элемента. Нотация Бауэрса для линейного массива, включающего конечное число элементов, имеет предел <math>\omega^\omega</math> в терминологии быстрорастущей иерархии.
Примечания
