Нотация массива

Нотация массива (англ. Array notation) — гугологическая функция, созданная Джонатаном Бауэрсом. Она была обобщена до расширенной нотации массива и в конечном итоге BEAF и BAN.

Её не следует путать с другими нотациями массива, такими как гиперфакториальная нотация массива, нотация птичьего массива, нотация массива Грэма, нотация массива Сайбиана, сильная нотация массива и т. д.

История

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

Изначально Правило 1 имело вид $\{a,b\}=a+b$. По предложению Криса Берда он изменил его на $a^b$, чтобы Правила 1 и 2 были совместимы.

Бауэрс обычно использовал угловые скобки <> для массивов, но нотация, которая изначально появилась на сайте, использовала вместо них фигурные скобки {}, поскольку угловые скобки вызывали проблемы с HTML.

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

Натан Хо и Wojowu показали, что нотация массива завершается — то есть её вывод существует для всех входных последовательностей.

Правила

Массив определяется как конечная последовательность положительных целых чисел. Нотация массива — функция $v(A)$, отображающая эти последовательности в большие положительные целые числа. Если $A=(a_{1},a_{2},\ldots ,a_{n})$, мы пишем $\{a_1,a_2 , \ldots,a_n\}$ как сокращение для $v(A)$.

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\}$. Другими словами, если третий элемент равен 1, то:
   • все элементы до последней 1, предшествующей не-1 элементу c, становятся первым элементом,
   • последняя из единиц становится исходным массивом со вторым элементом, уменьшенным на 1, и
   • указанный не-1 элемент уменьшается на единицу.
5. Если правила 1–4 не применяются, $\{a,b,c,d,\ldots,n\} = \{a,\{a,b-1,c,d,\ldots,n\},c-1,d,\ldots,n\}$

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

Бауэрс также создал набор "расширенных" операторов для дополнения нотации массива.

$a \{c\} b = \{a,b,c\}$

Например, $3\{3\}3=\{3,3,3\}$ = тритри.

В массиве {a,b,c,d,e,f,g,h}, a, b и c все показаны в числовой форме с наборами фигурных скобок d { }. Для представления e Бауэрс использует наборы квадратных скобок e - 1 [ ] над и под предложением, f представлена кольцами, подобными кольцам Сатурна, f - 1 вокруг предложения, а g представлена наборами скобок в виде крестообразного крыла g - 1 вокруг него. h представлена квадратными пластинами с противоположными краями, загнутыми на 90 градусов внутрь (т.е. трёхмерными версиями квадратных скобок).

Виды линейных массивов

Менее 3 записей

Когда записей меньше трёх, решить массивы довольно просто.

• Самый простой массив из всех — пустой: $\{\}=1$. Это технически недопустимая операция (она есть в BEAF), но она согласуется с остальными правилами.
• Массивы с 1 записью: $\{a\} = a$ (не путать со скобочными операторами).
• Массивы с 2 записями: $\{a,b\} = a^b$, что равно a в степени b (сложение в старой версии).

3–4 записи

Массивы с 3 записями дают то же значение, что и цепная нотация стрел: $\{a,b,c\}=a\rightarrow b\rightarrow c=a\uparrow ^{c}b=a\underbrace {\uparrow \ldots \uparrow } _{c}b$, точно так же, как $\{a,b\}=a\rightarrow b$

Массивы из 4 записей, $\{ a , b , c , d \}$, не продолжаются с этим шаблоном; на самом деле, согласно доказательству Берда, $\{ a , b , c , d \}$ превосходит цепь длиной d+2 из a в цепной нотации стрел.

Значения

$\{n,a+1,b+1,c+1,d+1,\cdots \}$

Нотация	Значение (приблизительное)
Многомерная функция Акерманна Таро	$f^{a}(n);f(n)=A(\cdots ,d,c,b,n)$
Быстрорастущая иерархия	$f_{\cdots +\omega ^{2}d+\omega c+b}^{a}(n)$
Иерархия Харди	$H_{\omega ^{\cdots +\omega ^{2}d+\omega c+b}a}(n)$
Медленнорастущая иерархия	$g_{\varphi (\cdots d+2,c+2,b+2,a^{2})}(n)$

Код на Haskell

import Data.List

an :: [Integer] -> Integer
-- Rule 1.
an [a] = a 
an [a,b] = a^b 
-- Rule 2.
an l | last l == 1 = an (init l)
-- Rule 3.
an (a:1:_) = a
-- Rule 4.
an (a:b:1:l) = an (a:a:map (const a) ones ++ an (a:b-1:l):c-1:rest) where
  (ones,c:rest) = span (==1) l
-- Rule 5.
an (a:b:c:l) = an (a:an (a:b-1:c:l):c-1:l)

Код машины Тьюринга

Формат ввода: x|A|, где A — массив в виде строк из единиц, разделённых пробелами. Например, x|111 111 111| вычисляет тритри.

Код машины Тьюринга:

0 * * r 0
0 _ _ r 1
0 | | r 0'
0' * * r 0'
0' _ _ r 1
0' | _ l h0
1 _ _ r 1
1 1 1 r 2
2 _ _ r 3
2 | _ l 4
2 1 1 r 5
3 * _ r 3
3 | _ l 4
4 * * l 4
4 1 _ l r0
5 1 1 r 5
5 | _ l 6
5 _ _ r 9
6 1 x l 7
6 _ 1 l s1
7 * * l 7
7 | | r 8
7 x x r 8
8 1 x r s0
8 _ 1 r s3
9 1 1 r 10
9 _ _ r 9
9 y y l b0
10 1 1 r 11
10 _ _ r 9
10 | _ l 12
11 1 1 r 11
11 _ _ r 9
11 | | l 15
12 1 _ l 13
13 _ | l 14
14 * * l 14
14 | | r 0
15 * * l 15
15 | | r c0
15 x x r c0
15 y y r c0

c0 1 x r c1
c0 _ y r c3
c0 | | r c6
c1 * * r c1
c1 | | r c2
c2 * * r c2
c2 _ x l c5
c3 * * r c3
c3 | | r c4
c4 * * r c4
c4 _ y l c5
c5 * * l c5
c5 | | l 15
c6 x 1 r c6
c6 y _ r c6
c6 _ | l 16

16 * * l 16
16 | | r 17
17 1 1 r 17
17 _ _ r 18
18 1 1 r 18
18 _ 1 l 19
18 | _ l 20
19 1 _ r 18
20 1 | l 21
21 * * l 21
21 | | l 22
22 x 1 l 22
22 y _ l 22
22 | | r 23

23 1 1 r 23
23 _ _ r 24
24 1 1 r 24
24 _ _ r 25
25 1 y r 26
26 1 1 l 27
26 _ _ r 25
27 y _ l 27
27 _ _ l 28
28 1 1 l 28
28 y y l 27
28 _ _ r 29
29 1 x r 30
30 * * r 30
30 | | r 0

r0 _ _ l r0
r0 1 _ l r1
r0 | _ l r7
r1 * * l r1
r1 x 1 r r2
r2 1 x r r3
r2 _ x r r5
r2 | | r h0
r3 * * r r3
r3 | | r r4
r4 1 1 r r4
r4 _ _ l r0
r5 _ _ r r6
r5 1 _ r r10
r5 y _ r r13
r6 * * r r6
r6 | | r r4
r7 1 | l r8
r8 1 1 l r8
r8 _ 1 l r9
r8 x x r 32
r9 1 _ l r8
r9 _ _ l r9
r9 y _ l r14
r9 x _ r r9'
r9' _ _ l 31
r9' * * l 14
r10 _ 1 r r11
r10 1 1 r r10
r10 | 1 r r12
r11 _ _ r r11
r11 1 _ r r10
r12 _ _ l r7
r12 1 | l r1
r13 _ y r r5
r14 _ y l r9

b0 * * l b0
b0 | | r b0'
b0' 1 x r b0
b0 x 1 r b1
b1 _ _ r b7
b1 1 x r b2
b2 * * r b2
b2 y 1 r b3
b3 _ y r b4
b4 y _ r b3
b4 1 _ r b5
b5 1 1 r b5
b5 _ 1 r b4
b5 | 1 r b6
b6 _ | l b0
b7 * * r b7
b7 y 1 r 9

h0 * * l h0
h0 | 1 l h1
h1 * _ r halt

s0 * * r s0
s0 x x l 6
s1 * * l s1
s1 x x r s2
s2 1 _ r s4
s3 1 1 r s3
s3 x _ r s4
s4 * 1 r s4
s4 _ _ l s5
s5 * * l s5
s5 x 1 l s5
s5 | | r p0

p0 1 1 l p0a
p0 _ _ r p19
p0a | | r p0b
p0b 1 _ r p1
p1 1 _ r p21
p1 _ _ r p10
p1 x _ r p11
p2 * * r p2
p2 _ _ r p3
p3 1 _ r p4
p3 x _ l p8
p4 1 1 r p4
p4 _ x r p5
p4 x x r p5
p5 1 1 r p5
p5 _ 1 l p6
p6 1 1 l p6
p6 * * l p7
p7 1 1 l p7
p7 _ 1 r p3
p8 1 1 l p8
p8 x x l p8
p8 _ x l p9
p9 1 1 l p8
p9 _ _ r p10
p10 x _ r p1
p10 1 1 l p20
p11 1 1 r p11
p11 x _ r p11
p11 _ _ l p12
p12 1 1 l p12
p12 _ _ r m0
m0 1 _ r m1
m0 _ _ r m9
m1 1 1 r m1
m1 _ _ r m2
m2 1 _ r m3
m2 _ _ l m7
m3 1 1 r m3
m3 _ _ r m4
m4 1 1 r m4
m4 _ 1 l m5
m5 1 1 l m5
m5 _ _ l m6
m6 1 1 l m6
m6 _ 1 r m2
m7 1 1 l m7
m7 _ _ l m8
m8 1 1 l m8
m8 _ _ r m0
m9 1 _ r m9
m9 _ 1 r p13
p13 1 1 r p13
p13 _ _ l p14
p14 1 _ l p15
p15 1 1 l p15
p15 _ 1 l p16
p16 1 1 r p17
p16 _ _ r p13
p16 x _ r p18
p16 | | r p22
p17 1 _ l p12
p18 1 _ r halt
p19 1 _ r p19
p19 _ 1 r halt
p20 * * l p20
p20 x _ r halt
p21 * * r p2
p21 _ x r p3
p22 1 1 r p22
p22 _ _ l p23
p23 1 _ l r0

31 _ x r 32
32 * * r 32
32 | _ l r7

Смотрите также

• BEAF
• Доказательство Берда
• Цепная нотация стрел
• Расширенная нотация массива
• Многомерная функция Акерманна Таро