Knuthův zápis

Knuthův zápis je způsob zápisu velkých čísel zavedený Donaldem Knuthem v roce 1976. Idea zápisu je, že násobení se může brát jako opakované sčítání, a umocňování jako opakované násobení. Pokračování tímto způsobem spěje k opakovanému umocňování (tetraci) a k dalším operacím.

Úvod

Základní matematické operace sčítání, násobení a umocňování jsou přirozeně rozšířeny do sekvence hyperoperací následujícím způsobem.

Násobení přirozeným číslem lze definovat jako opakované sčítání

$a\times b = \underbrace{a+a+\dots+a}_{b\text{ opakování }a}.$

Příklad:

$4\times 3 = \underbrace{4+4+4}_{3\text{ opakování }4} = 12$

Operátor umocňování

Umocňování na přirozený exponent $b$ lze definovat jako opakované násobení, což Knuth označil jednou šipkou vzhůru

$a\uparrow b= a^b = \underbrace{a\times a\times\dots\times a}_{b\text{ opakování }}.$

Příklad:

$4\uparrow 3= 4^3 = \underbrace{4\times 4\times 4}_{3\text{ opakování }4} = 64$

Operátor tetrace

Zobecněním tohoto postupu za operaci umocňování dostaneme operaci tetrace, pro kterou zavedl Knuth operátor "dvojité šipky",

$a\uparrow\uparrow b = {\ ^{b}a} = \underbrace{a^{a^{{}^{.\,^{.\,^{.\,^a}}}}}}_{b\text{ opakování }a} = \underbrace{a\uparrow (a\uparrow(\dots\uparrow a))}_{b\text{ opakování }a}.$

Příklady:

$4\uparrow\uparrow 3 = {\ ^{3}4} = \underbrace{4^{4^4}}_{3\text{ opakování }4} = \underbrace{4\uparrow (4\uparrow 4)}_{3\text{ opakování }4} = 4^{256} \approx 1,3\times 10^{154}$

$3\uparrow\uparrow2=3^3=27$

$3\uparrow\uparrow3=3^{3^3}=3^{27}=7\,625\,597\,484\,987$

$3\uparrow\uparrow4=3^{3^{3^3}}=3^{7\,625\,597\,484\,987}$

$3\uparrow\uparrow5=3^{3^{3^{3^3}}} = 3^{3^{7\,625\,597\,484\,987}}$

Operátor pentace

Již "operátor dvou šipek" vede na velká čísla, ale Knuth notaci rozšířil. Definoval operátor "trojité šipky" pro opakování operátoru "dvojité šipky" neboli pentaci,

$a\uparrow\uparrow\uparrow b = \underbrace{{}^{ {}^{ {}^{ {}^{ {}^a \cdot} \cdot} \cdot} a} a}_{b\text{ opakování }a} = \underbrace{a\,\uparrow\uparrow\,(a\,\uparrow\uparrow\,(\dots\,\uparrow\uparrow\,a))}_{b\text{ opakování }a}.$

Příklady:

$\begin{align} 3\uparrow\uparrow\uparrow2 &= 3\uparrow\uparrow3 = {}^33 = \\ & = 3\uparrow(3\uparrow3) = 3^{3^3} = 3^{27}=7\,625\,597\,484\,987 \\ \end{align}$

Velikost čísel opravdu velmi rychle roste

$\begin{align} 3\uparrow\uparrow\uparrow3 &= 3\uparrow\uparrow(3\uparrow\uparrow3) = {}^{ {}^3 3} 3 = {}^{7\,625\,597\,484\,987}3 = \\ & = 3\uparrow\uparrow(3\uparrow(3\uparrow3)) = \underbrace{3\uparrow(3\uparrow(\dots\uparrow 3))}_{3\uparrow(3\uparrow3)=7\,625\,597\,484\,987\text{ opakování }3} = \underbrace{3^{3^{\cdot^{\cdot^{\cdot^3}}}}}_{3\uparrow(3\uparrow3)\text{ opakování }3} \approx \exp_{10}^{7\,625\,597\,484\,987}(1.09902) \end{align}$

Následující číslo má v klasickém zápisu více než 10¹⁰²¹⁸⁴ číslic

$5 \uparrow\uparrow\uparrow2 = 5\uparrow\uparrow5 = {^{5}5} = 5^{5^{5^{5^5}}} = 5^{5^{5^{3125}}} \approx \exp_{10}^4(3.33928)$

Vyšší operátory

Dále operátor "čtyř šipek",

$a\uparrow\uparrow\uparrow\uparrow b = \underbrace{a\,\uparrow\uparrow\uparrow \,(a\,\uparrow\uparrow\uparrow(\dots\uparrow\uparrow\uparrow\,a))}_{b\text{ opakování }a}$

atd. Obecně "$n$-šipkový operátor" zavedeme jako sekvenci "($n - 1$)-šipkových operátorů". S využitím zápisu

$a \uparrow^n b=a\,\underbrace{\uparrow\uparrow\!\!\dots\!\!\uparrow}_{n\text{ šipek}}\,b$

dostaneme

$a\uparrow^nb = a\,\underbrace{\uparrow\uparrow\!\!\dots\!\!\uparrow}_{n\text{ šipek}}\,b \;=\; \underbrace{a\,\underbrace{\uparrow\!\!\dots\!\!\uparrow}_{n-1} \,(a\,\underbrace{\uparrow_{}\!\!\dots\!\!\uparrow}_{n-1} \,(\dots\,\underbrace{\uparrow_{}\!\!\dots\!\!\uparrow}_{n-1}\,a))}_{b\text{ opakování }a} \;=\; \underbrace{a\uparrow^{n-1}(a\uparrow^{n-1}(\ldots\uparrow^{n-1}a))}_{b\text{ opakování }a}.$

Základní operace a nevýhody značení

Základní operace můžeme vyjádřit pomocí Knuthova zápisu následovně:

$\begin{array}{ll} a\uparrow^0b=a\times b & \text{ (násobení),} \\ a\uparrow^1b=a^b & \text{ (umocňování),} \\ a\uparrow^2b={}^ba & \text{ (tetrace),} \\ a\uparrow^3b=a\!\uparrow\uparrow\uparrow\!b & \text{ (pentace),} \end{array}$

atd.

Zjevnou nevýhodou je, že pro sčítání bychom potřebovali zavést symbol $\uparrow^{-1}$ (tj. $a\uparrow^{-1}b=a+b$), který však evokuje inverzní operaci k $\uparrow$.

S tím souvisí i posunutí názvosloví vzhledem k počtu šipek použitých k označení operátoru (tetrace, pentace, tj. čtvrtá, resp. pátá operace jsou značeny pomocí dvou, resp. tří šipek).

Reference

V tomto článku byl použit překlad textu z článku Knuth's up-arrow notation na anglické Wikipedii.