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 niemożliwe do wykonania.

Definicja

$a\uparrow^n b=\left\{ \begin{array}{ll} 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:

$a\uparrow^n 1 = a$

Przykłady

$3\uparrow\uparrow 4 = 3\uparrow 3\uparrow 3\uparrow 3 = 3^{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\uparrow\uparrow...\uparrow\uparrow b = a\uparrow^n b$

Konstrukcja

$a\uparrow^1 b = a\times a\times ... \times a$

$a\uparrow^2 b = a\uparrow a\uparrow ... \uparrow a$

$a\uparrow^3 b = a\uparrow\uparrow a\uparrow\uparrow ... \uparrow\uparrow a$

$a\uparrow^4 b = a\uparrow\uparrow\uparrow a\uparrow\uparrow\uparrow ... \uparrow\uparrow\uparrow a$

$a\uparrow^n b = a \uparrow^{n-1} a \uparrow^{n-1} ... \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}$.

• $3\uparrow 3 = 3^3 = 27$

$3\uparrow^2 3 = 3\uparrow\uparrow 3 = 3 \uparrow (3 \uparrow 3) = 3\uparrow 3^3 = 3\uparrow 27 = 7625597484987$

$3\uparrow^3 3 = 3\uparrow\uparrow\uparrow 3 = 3 \uparrow\uparrow (3 \uparrow\uparrow 3) = 3 \uparrow\uparrow 7625597484987 = 3 \uparrow 3 \uparrow 3 \uparrow \cdots \uparrow 3$  ← (7625597484987 trójek)

Liczba Grahama

Oznaczmy $G_{0}=3\uparrow^4 3$. Wtedy $G_{1}=3\uparrow^{G_0} 3$, $G_{2}=3\uparrow^{G_1} 3$, itd. Liczbę G₆₃ nazywamy liczbą Grahama i jest ona górnym ograniczeniem liczby RG(1,2,2).

Zobacz też

• Nazwy dużych liczb
• Funkcja Ackermanna