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=\{\begin{array}{cc}{a}^b& \text{dla }n=1\\ 1& \text{dla }n>1\text{i }b=0\\ a{\uparrow }^{n-1}(a{\uparrow }^n(b-1))& \text{inaczej}\end{array}$

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

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

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

Z mnożeniem jako podstawą:

$a{\uparrow }^{n}b=\{\begin{array}{cc}a*b& \text{dla }n=0\\ 1& \text{dla }n⩾1\text{i }b=0\\ a{\uparrow }^{n-1}(a{\uparrow }^n(b-1))& \text{inaczej}\end{array}$

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$ Szablon:Link-interwiki itd. (ang. n-Szablon:Link-interwiki).

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\underset{n\text{razy}}{\underbrace{\uparrow \uparrow \dots \uparrow \uparrow }}b=a{\uparrow }^{n}b$

Konstrukcja

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

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

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

$a{\uparrow }^{4}b=a\uparrow \uparrow \uparrow a\uparrow \uparrow \uparrow \dots \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

Szablon:Osobny artykuł 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.

Zobacz też

• Działanie dwuargumentowe
• Liczba Grahama
• Tetracja