Notacja strzałkowa

Notacja strzałkowa Knutha – metoda zapisywania bardzo dużych liczb wprowadzona przez amerykańskiego matematyka Donalda Knutha w 1976^[1]. 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 ${\displaystyle f_{\omega }(n).}$

Definicja

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

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

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

Przykłady

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

${\displaystyle 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}$

${\displaystyle 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:

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

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

${\displaystyle a\uparrow \uparrow ...\uparrow \uparrow b=a\uparrow ^{n}b}$

Konstrukcja

${\displaystyle a\uparrow ^{1}b=a\times a\times ...\times a}$

${\displaystyle a\uparrow ^{2}b=a\uparrow a\uparrow ...\uparrow a}$

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

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

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

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

Inne przykłady

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

${\displaystyle a\uparrow \uparrow 1=a\uparrow (a\uparrow \uparrow 0)=a\uparrow 1=a,}$

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

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

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

${\displaystyle 2\uparrow \uparrow 2=2\uparrow (2\uparrow \uparrow 1)=2\uparrow 2=4,}$

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

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

• ${\displaystyle 3\uparrow 3=3^{3}=27}$

${\displaystyle 3\uparrow ^{2}3=3\uparrow \uparrow 3=3\uparrow (3\uparrow 3)=3\uparrow 3^{3}=3\uparrow 27=7\ 625\ 597\ 484\ 987}$

${\displaystyle 3\uparrow ^{3}3=3\uparrow \uparrow \uparrow 3=3\uparrow \uparrow (3\uparrow \uparrow 3)=3\uparrow \uparrow 7\ 625\ 597\ 484\ 987=3\uparrow 3\uparrow 3\uparrow \cdots \uparrow 3}$  ← (7 625 597 484 987 trójek)

Liczba Grahama

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

Przypisy