Notacja strzałkowa

Notacja strzałkowa Knutha – metoda zapisywania bardzo dużych liczb wprowadzona przez amerykańskiego matematyka Donalda Knutha w 1976. Podstawowa idea tej metody jest oparta na iterowanym potęgowaniu, w sposób podobny do tego jak potęgowanie jest iterowanym mnożeniem, mnożenie jest iterowanym dodawaniem, a dodawanie jest iterowaną inkrementacją. Celem tej notacji było zapisanie bardzo dużych liczb, których nawet zapisanie w postaci wykładniczej było trudne lub praktycznie niemożliwe do wykonania. Tempo wzrostu w szybko rosnącej hierarchii wynosi $f_{\omega }(n).$

Definicja

Z potęgowaniem jako podstawą:

$a\uparrow ^{n}b=\left\{{\begin{array}{l}a^{b}&{\mbox{dla }}n=1\\1&{\mbox{dla }}n>1\ {\mbox{i }}\ b=0\\a\uparrow ^{n-1}(a\uparrow ^{n}(b-1))&{\mbox{inaczej}}\end{array}}\right.$

dla wszystkich liczb całkowitych $a,b,n$ z $a\geqslant 0,n\geqslant 1,b\geqslant 0.$

Dodatkowo w sekcji Inne przykłady wykazano, że:

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

Z mnożeniem jako podstawą:

$a\uparrow ^{n}b=\left\{{\begin{array}{l}a*b&{\mbox{dla }}n=0\\1&{\mbox{dla }}n\geqslant 1\ {\mbox{i }}\ b=0\\a\uparrow ^{n-1}(a\uparrow ^{n}(b-1))&{\mbox{inaczej}}\end{array}}\right.$

dla wszystkich nieujemnych liczb całkowitych $a,b,n.$

Dla $n=1$ otrzymamy zwykłe potęgowanie $(3\uparrow 4=3^{4}),$ dla $n=2$ tetrację, dla $n=3$ pentację itd. (ang. n-hyperoperation).

Przykłady

$3\uparrow \uparrow 3=3\uparrow 3\uparrow 3=3^{3^{3}}=7625597484987$

$3\uparrow \uparrow \uparrow 5=3\uparrow \uparrow (3\uparrow \uparrow (3\uparrow \uparrow (3\uparrow \uparrow 3)))=3\uparrow \uparrow 3\uparrow \uparrow 3\uparrow \uparrow 3\uparrow \uparrow 3$

$3\uparrow ^{3}3=3\uparrow \uparrow \uparrow 3=3\uparrow \uparrow (3\uparrow \uparrow \uparrow 2)=3\uparrow \uparrow (3\uparrow \uparrow 3)=3\uparrow \uparrow (3\uparrow 3\uparrow 3)=3\uparrow \uparrow (3\uparrow 3^{3})=3\uparrow \uparrow (3^{3^{3}})$

Opis notacji

Dla skrócenia zapisu dużą ilość strzałek zastępuje się ich liczbą umieszczoną po prawej stronie strzałki w indeksie górnym:

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

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

$a\ \underbrace {\uparrow \uparrow \ldots \uparrow \uparrow } _{n\ {\text{razy}}}\ b=a\uparrow ^{n}b$

Konstrukcja

$a\uparrow ^{1}b=a\times a\times \ldots \times a$

$a\uparrow ^{2}b=a\uparrow a\uparrow \ldots \uparrow a$

$a\uparrow ^{3}b=a\uparrow \uparrow a\uparrow \uparrow \ldots \uparrow \uparrow a$

$a\uparrow ^{4}b=a\uparrow \uparrow \uparrow a\uparrow \uparrow \uparrow \ldots \uparrow \uparrow \uparrow a$

$a\uparrow ^{n}b=a\uparrow ^{n-1}a\uparrow ^{n-1}\dots \uparrow ^{n-1}a$

gdzie $a$ występuje po prawej stronie równań zawsze dokładnie $b$ razy.

Inne przykłady

• $a\uparrow 1=a^{1}=a.$

$a\uparrow \uparrow 1=a\uparrow (a\uparrow \uparrow 0)=a\uparrow 1=a,$

$a\uparrow ^{n+1}1=a\uparrow ^{n}(a\uparrow ^{n+1}0)=a\uparrow ^{n}1,$

a stąd indukcyjnie uzasadniamy, że $a\uparrow ^{n}1=a$ dla wszystkich $n\in \mathbb {N} .$

• $2\uparrow 2=2^{2}=4,$

$2\uparrow \uparrow 2=2\uparrow (2\uparrow \uparrow 1)=2\uparrow 2=4,$

$2\uparrow ^{n+1}2=2\uparrow ^{n}(2\uparrow ^{n+1}1)=2\uparrow ^{n}2$

i stąd indukcyjnie uzasadniamy, że $2\uparrow ^{n}2=4$ dla wszystkich $n\in \mathbb {N} .$

Liczba Grahama

Oznaczmy $G_{1}=3\uparrow ^{4}3.$ Wtedy $G_{2}=3\uparrow ^{G_{1}}3,$ $G_{3}=3\uparrow ^{G_{2}}3,$ itd. Liczbę $G_{64}$ nazywamy liczbą Grahama.