Notarea săgeții lui Knuth

Notarea cu săgeată a lui Knuth este un tip de notație numerică, creată de informaticianul Donald Knuth pentru a scrie numere foarte mari care, în cifre normale sau exponențiale , ar fi imposibil de scris, cum ar fi numărul lui Graham .

Definiție

Secvența de hiperoperare este o secvență de operații binare $H_{n}(a,b)\,:\,(\mathbb {N} _{0})^{3}\rightarrow \mathbb {N} _{0}\,\!$ ${\ displaystyle H_ {n} (a, b) \ ,: \, (\ mathbb {N} _ {0}) ^ {3} \ rightarrow \ mathbb {N} _ {0} \, \!}$ ${\ displaystyle H_ {n} (a, b) \ ,: \, (\ mathbb {N} _ {0}) ^ {3} \ rightarrow \ mathbb {N} _ {0} \, \!}$ , definit recursiv după cum urmează:

H_{n}(a,b)={\begin{cases}b+1&{\text{se }}n=0\\a&{\text{se }}n=1,b=0\\0&{\text{se }}n=2,b=0\\1&{\text{se }}n\geq 3,b=0\\H_{n-1}(a,H_{n}(a,b-1))&{\text{altrimenti}}\end{cases}}\,\!

{\ displaystyle H_ {n} (a, b) = {\ begin {cases} b + 1 & {\ text {se}} n = 0 \\ a & {\ text {se}} n = 1, b = 0 \ \ 0 & {\ text {se}} n = 2, b = 0 \\ 1 & {\ text {se}} n \ geq 3, b = 0 \\ H_ {n-1} (a, H_ {n} (a, b-1)) și {\ text {else}} \ end {cases}} \, \!}

{\ displaystyle H_ {n} (a, b) = {\ begin {cases} b + 1 & {\ text {se}} n = 0 \\ a & {\ text {se}} n = 1, b = 0 \ \ 0 & {\ text {se}} n = 2, b = 0 \\ 1 & {\ text {se}} n \ geq 3, b = 0 \\ H_ {n-1} (a, H_ {n} (a, b-1)) și {\ text {else}} \ end {cases}} \, \!}

(Rețineți că n = 0, operația binară se reduce în esență la o operație unară ( funcția următoare ) ignorând primul argument.)

Pentru n = 0, 1, 2, 3, această definiție reproduce operațiile de bază ale aritmeticii funcției următoare (care este o operație unară), adunarea, multiplicarea și exponențierea , cum ar fi:

H_{0}(a,b)=b+1\,\!,

{\ displaystyle H_ {0} (a, b) = b + 1 \, \!,}

{\ displaystyle H_ {0} (a, b) = b + 1 \, \!,}

H_{1}(a,b)=a+b\,\!,

{\ displaystyle H_ {1} (a, b) = a + b \, \!,}

{\ displaystyle H_ {1} (a, b) = a + b \, \!,}

H_{2}(a,b)=a\cdot b\,\!,

{\ displaystyle H_ {2} (a, b) = a \ cdot b \, \!,}

{\ displaystyle H_ {2} (a, b) = a \ cdot b \, \!,}

H_{3}(a,b)=a^{b}\,\!,

{\ displaystyle H_ {3} (a, b) = a ^ {b} \, \!,}

{\ displaystyle H_ {3} (a, b) = a ^ {b} \, \!,}

iar pentru n ≥ 4 extinde aceste operații de bază dincolo de exponențiere în ceea ce poate fi scris în notația săgeții lui Knuth ca

H_{4}(a,b)=a\uparrow \uparrow {b}\,\!,

{\ displaystyle H_ {4} (a, b) = a \ uparrow \ uparrow {b} \, \!,}

{\ displaystyle H_ {4} (a, b) = a \ uparrow \ uparrow {b} \, \!,}

H_{5}(a,b)=a\uparrow \uparrow \uparrow {b}\,\!,

{\ displaystyle H_ {5} (a, b) = a \ uparrow \ uparrow \ uparrow {b} \, \!,}

{\ displaystyle H_ {5} (a, b) = a \ uparrow \ uparrow \ uparrow {b} \, \!,}

...

H_{n}(a,b)=a\uparrow ^{n-2}b{\text{ per }}n\geq 3\,\!,

{\ displaystyle H_ {n} (a, b) = a \ uparrow ^ {n-2} b {\ text {per}} n \ geq 3 \, \!,}

{\ displaystyle H_ {n} (a, b) = a \ uparrow ^ {n-2} b {\ text {per}} n \ geq 3 \, \!,}

...

Descriere

Această notație este alcătuită dintr-un număr inițial, urmat de un număr dat de săgeți în sus, urmat în cele din urmă de un număr final.

Înțelesul săgeților este după cum urmează:

o singură săgeată în sus reprezintă exponențierea ;
o săgeată dublă îndreptată în sus ( $\uparrow \uparrow$ ${\ displaystyle \ uparrow \ uparrow}$ $\ uparrow \ uparrow$ ) reprezintă o tetrare sau o putere recursivă ;
trei săgeți ( $\uparrow \uparrow \uparrow$ ${\ displaystyle \ uparrow \ uparrow \ uparrow}$ $\ uparrow \ uparrow \ uparrow$ ) reprezintă o tetrare recursivă ;
fiecare săgeată ulterioară crește adâncimea de iterație.

Rezultatul este o creștere numerică extrem de mare pentru fiecare săgeată adăugată.

În termeni numerici:
$3\uparrow \uparrow 3=3^{3^{3}}=3^{27}=7625597484987$ ${\ displaystyle 3 \ uparrow \ uparrow 3 = 3 ^ {3 ^ {3}} = 3 ^ {27} = 7625597484987}$ $3 \ uparrow \ uparrow 3 = 3 ^ {{3 ^ {3}}} = 3 ^ {{27}} = 7625597484987$
$3\uparrow \uparrow \uparrow 3=3\uparrow \uparrow (3\uparrow \uparrow 3)={\begin{matrix}&3\underbrace {\uparrow 3\uparrow 3\uparrow \dots \uparrow 3} \\&3\uparrow \uparrow 3{\text{ volte }}\end{matrix}}=3\uparrow \uparrow 3^{27}=\left.{\begin{matrix}3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}\end{matrix}}\right\}\left.{\begin{matrix}7625597484987\end{matrix}}\right.$ ${\ displaystyle 3 \ uparrow \ uparrow \ uparrow 3 = 3 \ uparrow \ uparrow (3 \ uparrow \ uparrow 3) = {\ begin {matrix} & 3 \ underbrace {\ uparrow 3 \ uparrow 3 \ uparrow \ dots \ uparrow 3 } \\ & 3 \ uparrow \ uparrow 3 {\ text {times}} \ end {matrix}} = 3 \ uparrow \ uparrow 3 ^ {27} = \ left. {\ Begin {matrix} 3 ^ {3 ^ { \ cdot ^ {\ cdot ^ {\ cdot ^ {3}}}}} \ end {matrix}} \ right \} \ left. {\ begin {matrix} 7625597484987 \ end {matrix}} \ right.}$ $3 \ uparrow \ uparrow \ uparrow 3 = 3 \ uparrow \ uparrow (3 \ uparrow \ uparrow 3) = {\ begin {matrix} & 3 \ underbrace {\ uparrow 3 \ uparrow 3 \ uparrow \ dots \ uparrow 3} \\ & 3 \ uparrow \ uparrow 3 {\ text {times}} \ end {matrix}} = 3 \ uparrow \ uparrow 3 ^ {{27}} = \ left. {\ Begin {matrix} 3 ^ {{3 ^ { {\ cdot ^ {{\ cdot ^ {{\ cdot ^ {{3}}}}}}}}} \ end {matrix}} \ right \} \ left. {\ begin {matrix} 7625597484987 \ end {matrix }} \ dreapta.$ ori
si asa mai departe.

Exemple

n	Operațiune ( H _n ( a , b ))	Definiție	Numele	Domeniu
0	$1+b$ ${\ displaystyle 1 + b}$ ${\ displaystyle 1 + b}$	${1+{\underbrace {1+1+1+\cdots +1} \atop {b{\mbox{ copie di 1}}}}}$ ${\ displaystyle {1 + {\ underbrace {1 + 1 + 1 + \ cdots +1} \ atop {b {\ mbox {copii ale 1}}}}}}$ ${\ displaystyle {1 + {\ underbrace {1 + 1 + 1 + \ cdots +1} \ atop {b {\ mbox {copii ale 1}}}}}}$	hyper0, increment, funcție subsesivă ,	arbitrar
1	$a+b$ ${\ displaystyle a + b}$ ${\ displaystyle a + b}$	${a+{\underbrace {1+1+1+\cdots +1} \atop {b{\mbox{ copie di 1}}}}}$ ${\ displaystyle {a + {\ underbrace {1 + 1 + 1 + \ cdots +1} \ atop {b {\ mbox {copii ale 1}}}}}}$ ${\ displaystyle {a + {\ underbrace {1 + 1 + 1 + \ cdots +1} \ atop {b {\ mbox {copii ale 1}}}}}}$	iper1, plus	arbitrar
2	$a\cdot b$ ${\ displaystyle a \ cdot b}$ ${\ displaystyle a \ cdot b}$	${{\underbrace {a+a+a+\cdots +a} } \atop {b{\mbox{ copie di }}a}}$ ${\ displaystyle {{\ underbrace {a + a + a + \ cdots + a}} \ atop {b {\ mbox {copii ale}} a}}}$ ${\ displaystyle {{\ underbrace {a + a + a + \ cdots + a}} \ atop {b {\ mbox {copii ale}} a}}}$	hiper2, multiplicare	arbitrar
3	$a^{b}$ ${\ displaystyle a ^ {b}}$ $a ^ b$ sau $a\uparrow b$ ${\ displaystyle a \ uparrow b}$ ${\ displaystyle a \ uparrow b}$	${{\underbrace {a\cdot a\cdot a\cdot a\cdot \ldots \cdot a} } \atop {b{\mbox{ copie di }}a}}$ ${\ displaystyle {{\ underbrace {a \ cdot a \ cdot a \ cdot a \ cdot \ ldots \ cdot a}} \ atop {b {\ mbox {copies of}} a}}}$ ${\ displaystyle {{\ underbrace {a \ cdot a \ cdot a \ cdot a \ cdot \ ldots \ cdot a}} \ atop {b {\ mbox {copies of}} a}}}$	iper3, exponențiere	b real, cu unele extensii multivalorate în numere complexe
4	$^{b}a$ ${\ displaystyle ^ {b} a}$ ${\ displaystyle ^ {b} a}$ sau $a\uparrow \uparrow b$ ${\ displaystyle a \ uparrow \ uparrow b}$ ${\ displaystyle a \ uparrow \ uparrow b}$	${{\underbrace {a\uparrow (a\uparrow (a\uparrow (a\uparrow \cdots \uparrow a))...)} } \atop {b{\mbox{ copie di }}a}}$ ${\ displaystyle {{\ underbrace {a \ uparrow (a \ uparrow (a \ uparrow (a \ uparrow \ cdots \ uparrow a)) ...)}} \ atop {b {\ mbox {copii ale}} a }}}$ ${\ displaystyle {{\ underbrace {a \ uparrow (a \ uparrow (a \ uparrow (a \ uparrow \ cdots \ uparrow a)) ...)}} \ atop {b {\ mbox {copii ale}} a }}}$	iper4, tetration	a ≥ 0 sau un întreg, b un întreg ≥ −1 ^[1] (cu unele extensii propuse)
5	$a\uparrow \uparrow \uparrow b$ ${\ displaystyle a \ uparrow \ uparrow \ uparrow b}$ ${\ displaystyle a \ uparrow \ uparrow \ uparrow b}$ sau $a\uparrow ^{3}b$ ${\ displaystyle a \ uparrow ^ {3} b}$ ${\ displaystyle a \ uparrow ^ {3} b}$	${{\underbrace {a\uparrow \uparrow (a\uparrow \uparrow (a\uparrow \uparrow (a\uparrow \uparrow \cdots \uparrow \uparrow a))...)} } \atop {b{\mbox{ copie di }}a}}$ ${\ displaystyle {{\ underbrace {a \ uparrow \ uparrow (a \ uparrow \ uparrow (a \ uparrow \ uparrow (a \ uparrow \ uparrow \ cdots \ uparrow \ uparrow a)) ...)}} \ atop { b {\ mbox {copii ale lui}} a}}}$ ${\ displaystyle {{\ underbrace {a \ uparrow \ uparrow (a \ uparrow \ uparrow (a \ uparrow \ uparrow (a \ uparrow \ uparrow \ cdots \ uparrow \ uparrow a))) ...)}} \ atop { b {\ mbox {copii ale lui}} a}}}$	iper5, pentație	a , b numere întregi ≥ −1 ^[1]
6	$a\uparrow \uparrow \uparrow \uparrow b$ ${\ displaystyle a \ uparrow \ uparrow \ uparrow \ uparrow b}$ ${\ displaystyle a \ uparrow \ uparrow \ uparrow \ uparrow b}$ sau $a\uparrow ^{4}b$ ${\ displaystyle a \ uparrow ^ {4} b}$ ${\ displaystyle a \ uparrow ^ {4} b}$	${{\underbrace {a\uparrow ^{3}(a\uparrow ^{3}(a\uparrow ^{3}(a\uparrow ^{3}\cdots \uparrow ^{3}a))...)} } \atop {b{\mbox{ copie di }}a}}$ ${\ displaystyle {{\ underbrace {a \ uparrow ^ {3} (a \ uparrow ^ {3} (a \ uparrow ^ {3} (a \ uparrow ^ {3} \ cdots \ uparrow ^ {3} a)) ...)}} \ atop {b {\ mbox {copii ale lui}} a}}}$ ${\ displaystyle {{\ underbrace {a \ uparrow ^ {3} (a \ uparrow ^ {3} (a \ uparrow ^ {3} (a \ uparrow ^ {3} \ cdots \ uparrow ^ {3} a)) ...)}} \ atop {b {\ mbox {copii ale lui}} a}}}$	iper6, exacțiune	a , b numere întregi ≥ −1 ^[1]

Notă

^ ^a ^b ^c Fie x = a [ n ] (- 1). Din formula recursivă, a [ n ] 0 = a [ n -1] ( a [ n ] (- 1)) => 1 = a [ n -1] x . O soluție este x = 0, deoarece a [ n -1] 0 = 1 oferă definiție când n ≥ 4. Această soluție este unică, deoarece a [ n -1] b > 1 pentru fiecare a > 1, b > 0 (încercați prin recursivitate).

Elemente conexe

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[nega-1] Fie x = a [ n ] (- 1). Din formula recursivă, a [ n ] 0 = a [ n -1] ( a [ n ] (- 1)) => 1 = a [ n -1] x . O soluție este x = 0, deoarece a [ n -1] 0 = 1 oferă definiție când n ≥ 4. Această soluție este unică, deoarece a [ n -1] b > 1 pentru fiecare a > 1, b > 0 (încercați prin recursivitate).

[1]