Notacio de Knuth

Suprenindikila notacio de Knuth estas matematika metodo por enskribi enorme grandajn nombrojn. Ĝi estas kreita far Donald Knuth en 1976. Ege parenca al funkcio de Ackermann, ĝi utiligas la principo de iteraciita potencigo, samkiel potencigo estas iteraciita multipliko kaj multipliko estas iteraciita adicio.

Enkonduko en la notacio

Multipliko je naturalo estas iteraciita adicio:

$\begin{matrix} a b & = & \underbrace{a+a+\dots+a} \\ & & b\mbox{ kopioj de }a \end{matrix} .$

Ekzemple

$\begin{matrix} 3\times 2 & = & \underbrace{3+3} & = & 6\\ & & 2\mbox{ kopioj de }3 \end{matrix} .$

Same, potencigo je naturalo estas iteraciita multipliko:

$\begin{matrix} a\uparrow b= a^b = & \underbrace{a\times a\times\dots\times a}\\ & b\mbox{ kopioj de }a \end{matrix} .$

Ekzemple:

$\begin{matrix} 3\uparrow 2= 3^2 = & \underbrace{3\times 3} & = & 9\\ & 2\mbox{ kopioj de }3 \end{matrix} .$

Notu, kiel suprenindikilo estas uzata por potencigo. Tiamaniere, Knuth definis operatoro de duobla suprenindikilo:

$\begin{matrix} a\uparrow\uparrow b & = {\ ^{b}a} = & \underbrace{a^{a^{{}^{.\,^{.\,^{.\,^a}}}}}} & = & \underbrace{a\uparrow a\uparrow\dots\uparrow a} \\ & & b\mbox{ kopioj de }a & & b\mbox{ kopioj de }a \end{matrix}$

Ekzemple:

$\begin{matrix} 3\uparrow\uparrow 2 & = {\ ^{2}3} = & \underbrace{3^3} & = & \underbrace{3\uparrow 3} & = & 27 \\ & & 2\mbox{ kopioj de }3 & & 2\mbox{ kopioj de }3 \end{matrix} .$

Notu, ke tie ĉi kaj plu la nombroj estas kalkulitaj kaj transformitaj de dekstre liven. Laŭ tiu ĉi difino:

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

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

$3\uparrow\uparrow4=3^{3^{3^3}}=3^{7625597484987}$ (nur por skribi la numeralon en plena formo oni bezonus ĉ. 1.37 terabajtojn de diska spaco, t. e. $7,625,597,484,987 \times \frac{\log 3}{\log 2}$ bitojn)

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

ktp.

Eĉ tiuj nombroj jam estas enormaj, sed Knuth plu disvolvigis la notacion, difininte operatoro de triobla suprenindikilo:

$\begin{matrix} a\uparrow\uparrow\uparrow b= & \underbrace{a_{}\uparrow\uparrow a\uparrow\uparrow\dots\uparrow\uparrow a}\\ & b\mbox{ kopioj de }a \end{matrix}$

kaj poste kvarobla suprenindikilo:

$\begin{matrix} a\uparrow\uparrow\uparrow\uparrow b= & \underbrace{a_{}\uparrow\uparrow\uparrow a\uparrow\uparrow\uparrow\dots\uparrow\uparrow\uparrow a}\\ & b\mbox{ kopioj de }a \end{matrix}$

kaj tiel plu.

La ĝenerala regulo estas ke operatoro de $n$-obla suprenindikilo transformas en serion de la ($n - 1$)-oblaj. Simbolece,

$\begin{matrix} a\ \underbrace{\uparrow_{}\uparrow\!\!\dots\!\!\uparrow}\ b= a\ \underbrace{\uparrow\!\!\dots\!\!\uparrow} \ a\ \underbrace{\uparrow_{}\!\!\dots\!\!\uparrow} \ a\ \dots \ a\ \underbrace{\uparrow_{}\!\!\dots\!\!\uparrow} \ a \\ \quad\ \ \,n\qquad\ \ \ \underbrace{\quad n_{}\!-\!\!1\quad\ \,n\!-\!\!1\qquad\quad\ \ \ \,n\!-\!\!1\ \ \ } \\ \qquad\qquad\quad\ \ b\mbox{ kopioj de }a \end{matrix}$

Ekzemploj:

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

$\begin{matrix} 3\uparrow\uparrow\uparrow3 = 3\uparrow\uparrow3\uparrow\uparrow3 = 3\uparrow\uparrow(3\uparrow3\uparrow3) = & \underbrace{3_{}\uparrow 3\uparrow\dots\uparrow 3} \\ & 3\uparrow3\uparrow3\mbox{ kopioj de }3 \end{matrix} \begin{matrix} = & \underbrace{3_{}\uparrow 3\uparrow\dots\uparrow 3} \\ & \mbox{7,625,597,484,987 kopioj de 3} \end{matrix}$

Forma difino

Forme, la Suprenindikila Notacio de Knuth difinatas kiel:

$a\uparrow^n b= \left\{ \begin{matrix} a^b, & \mbox{se }n=1; \\ 1, & \mbox{se }b=0; \\ a\uparrow^{n-1}(a\uparrow^n(b-1)), & \mbox{aliokaze} \end{matrix} \right.$

por ĉiuj $a, b, n$ se $b \ge 0, n \ge 1$.

La funkcio estas Dekstre-asocia, t.e. ĝi transformatas de dekstre liven, kaj en formulo kiu havas du aŭ pli da tiaj operatoroj, ankaŭ unue grupatas la plej dektrajn. Ekzemple, $a \uparrow b \uparrow c = a \uparrow (b \uparrow c)$, sed ne $(a \uparrow b) \uparrow c$;

Se estus alie, la funkcio estus nenio pli nova ol unua iteracio de potencigo. Ekzemple,
$3\uparrow\uparrow 3=3^{3^3}$ estas $3^{(3^3)}=3^{27}=7625597484987$, sed se oni grupus de live estus $\left(3^3\right)^3=27^3=19683.$.

Se oni skribas $(a\uparrow ^m)^b$ por la b-a funkcia potenco de la funkcio $f(n)=a\uparrow ^m n$, tio signifu $a\uparrow ^n b = (a\uparrow ^{n-1})^b 1$.

Valoroj

Kalkulo de $2\uparrow^m n$ povas esti skribita en senfinan tabelon. Oni metu numerojn n en supran vicon, kaj metu valorojn de m en unuan kolumnon. Jenas la rezulta tabelo:

Valoroj de $2\uparrow^m n$ = hyper(2, m + 2, n) = 2 → n → m

m\n	1	2	3	4	5	6	7	formula
0	2	4	6	8	10	12	14	$2n$
1	2	4	8	16	32	64	128	$2^n$
2	2	4	16	65536	$2^{65536}\approx 2.0 \times 10^{19,729}$	$2^{2^{65536}}\approx 10^{6.0 \times 10^{19,728}}$	$2^{2^{2^{65536}}}\approx 10^{10^{6.0 \times 10^{19,728}}}$	$2\uparrow\uparrow n$
3	2	4	65536	$\begin{matrix} \underbrace{2_{}^{2^{{}^{.\,^{.\,^{.\,^2}}}}}} \\ 65536\mbox{ kopioj de }2 \end{matrix}\approx (10\uparrow)^{65531}(6.0 \times 10^{19,728})$				$2\uparrow\uparrow\uparrow n$
4	2	4	$\begin{matrix} \underbrace{2_{}^{2^{{}^{.\,^{.\,^{.\,^2}}}}}}\\ 65536\mbox{ kopioj de }2 \end{matrix}$					$2\uparrow\uparrow\uparrow\uparrow n$

Sama tabelo por $3\uparrow^m n$:

Valoroj de $3\uparrow^m n$ = $3\uparrow^m n$ = hyper(3, m + 2, n) = 3 → n → m

m\n	1	2	3	4	5	formula
0	3	6	9	12	15	$3n$
1	3	9	27	81	243	$3^n$
2	3	27	7,625,597,484,987	$3^{7,625,597,484,987}$		$3\uparrow\uparrow n$
3	3	7,625,597,484,987	$\begin{matrix} \underbrace{3_{}^{3^{{}^{.\,^{.\,^{.\,^3}}}}}}\\ 7,625,597,484,987\mbox{ kopioj de }3 \end{matrix}$			$3\uparrow\uparrow\uparrow n$
4	3	$\begin{matrix} \underbrace{3_{}^{3^{{}^{.\,^{.\,^{.\,^3}}}}}}\\ 7,625,597,484,987\mbox{ kopioj de }3 \end{matrix}$				$3\uparrow\uparrow\uparrow\uparrow n$

Sama por $10\uparrow^m n$:

Valoroj de $10\uparrow^m n$ = hyper(10, m + 2, n) = 10 → n → m

m\n	1	2	3	4	5	formula
0	10	20	30	40	50	$10n$
1	10	100	1,000	10,000	100,000	$10^n$
2	10	10,000,000,000	$10^{10,000,000,000}$	$10^{10^{10,000,000,000}}$	$10^{10^{10^{10,000,000,000}}}$	$10\uparrow\uparrow n$
3	10	$\begin{matrix} \underbrace{10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}}\\ 10\mbox{ kopioj de }10 \end{matrix}$	$\begin{matrix} \underbrace{10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}}\\ 10^{10}\mbox{ kopioj de }10 \end{matrix}$	$\begin{matrix} \underbrace{10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}}\\ 10^{10^{10}}\mbox{ kopioj de }10 \end{matrix}$		$10\uparrow\uparrow\uparrow n$
4	10	$\begin{matrix} \underbrace{^{^{^{^{^{10}.}.}.}10}10}\\ 10\mbox{ kopioj de }10 \end{matrix}$	$\begin{matrix} \underbrace{^{^{^{^{^{10}.}.}.}10}10}\\ 10^{10}\mbox{ kopioj de }10 \end{matrix}$			$10\uparrow\uparrow\uparrow\uparrow n$

Limoj

La nombroj kiujn oni povas skribi per Notacio de Knuth jam estas enormaj, sed en matematiko ekzistas nombroj por kiuj eĉ ĝi ne sufiĉas. Por ili oni uzas operatoron de n-obla suprenindikilo, kiun skribas kiel $\uparrow^n$. Ankaŭ uzeblas hiper-operatoro. Sed ekzistas nombroj tiom nekredeble grandaj, ke eĉ tio ne sufiĉas. Ekzemple, por nombro de Graham oni bezonus turon de 64 tavoloj de potencaj simboloj, se oni volus skribi ĝis per Notacio de Knuth. En tiuj okazoj oni uzu eĉ pli ĝeneralitajn sistemojn, kiel ĉena indikila skribmaniero de Conway. En notacio de Conway ĉenoj de tri numeroj estas pli-malpli same potenca kiel $\uparrow^n$, sed ĉenoj de 4 aŭ pli numeroj estas ege pli potencaj:

$\begin{matrix} a\uparrow^n b & = & \mbox{hyper}(a,n+2,b) & = & a\to b\to n \\ \mbox{(Knuth)} & & & & \mbox{(Conway)} \end{matrix}$

Plej kutime matematikistoj uzas notacion de Knuth por relative "malgrandaj" nomoj, kaj por pli grandaj oni uzas notacion de Conway aŭ hiper-operatorojn.

Vidu ankaŭ

• Ĉena indikila skribmaniero de Conway
• Notacio de Cutler
• Hiper-operatoro

Ligoj

• Knuth, Donald E., "Coping With Finiteness", Science vol. 194 n. 4271 (Dec 1976), pp. 1235-1242.
• Eric W. Weisstein, Arrow Notation en MathWorld.
• Robert Munafo, Large Numbers