Notazione a frecce di Knuth

Questa voce o sezione sull'argomento matematica non cita le fonti necessarie o quelle presenti sono insufficienti.

La notazione a frecce di Knuth è un tipo di notazione numerica, creata dall'informatico Donald Knuth per scrivere numeri molto grandi che nelle normale notazioni a cifre o esponenziale sarebbero impossibili da scrivere, come il numero di Graham.

Definizione

La sequenza di iperoperazione è una sequenza di operazioni binarie $H_{n}(a,b)\,:\,(\mathbb {N} _{0})^{3}\rightarrow \mathbb {N} _{0}\,\!$ , definita ricorsivamente come segue:

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}}\,\!

(Notare che n = 0, l'operazione binaria essenzialmente si riduce a un'operazione unaria (funzione successiva) ignorando il primo argomento.)

Per n = 0, 1, 2, 3, questa definizione riproduce le operazioni di base dell'aritmetica della funzione successiva (che è un'operazione unaria), addizione, moltiplicazione e esponenziazione, come:

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

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

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

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

e per n ≥ 4 estende queste operazioni di base oltre l'esponenziazione in quella che può essere scritta in notazione a frecce di Knuth come

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

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

...

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

...

Descrizione

Questa notazione si compone di un numero iniziale, seguito da un dato numero di frecce verso l'alto, seguita infine da un numero finale.

Il significato delle frecce è il seguente:

una singola freccia verso l'alto rappresenta un elevamento a potenza;
una doppia freccia verso l'alto ( $\uparrow \uparrow$ ) rappresenta una tetrazione, ovvero una potenza ricorsiva;
tre frecce ( $\uparrow \uparrow \uparrow$ ) rappresentano una tetrazione ricorsiva;
ogni successiva freccia incrementa la profondità di iterazione.

Il risultato è un aumento numerico estremamente elevato per ogni freccia aggiunta.

In termini numerici:
$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.$ volte
e via dicendo.

Esempi

n	Operazione (H_n(a, b))	Definizione	Nomi	Dominio
0	$1+b$	${1+{\underbrace {1+1+1+\cdots +1} \atop {b{\mbox{ copie di 1}}}}}$	iper0, incremento, funzione successiva,	arbitrario
1	$a+b$	${a+{\underbrace {1+1+1+\cdots +1} \atop {b{\mbox{ copie di 1}}}}}$	iper1, addizione	arbitrario
2	$a\cdot b$	${{\underbrace {a+a+a+\cdots +a} } \atop {b{\mbox{ copie di }}a}}$	iper2, moltiplicazione	arbitrario
3	$a^{b}$ o $a\uparrow b$	${{\underbrace {a\cdot a\cdot a\cdot a\cdot \ldots \cdot a} } \atop {b{\mbox{ copie di }}a}}$	iper3, esponenziazione	b reale, con alcune estensioni multivalore nei numeri complessi
4	$^{b}a$ or $a\uparrow \uparrow b$	${{\underbrace {a\uparrow (a\uparrow (a\uparrow (a\uparrow \cdots \uparrow a))...)} } \atop {b{\mbox{ copie di }}a}}$	iper4, tetrazione	a ≥ 0 o un intero, b un intero ≥ −1^[1] (con alcune estensioni proposte)
5	$a\uparrow \uparrow \uparrow b$ o $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}}$	iper5, pentazione	a, b interi ≥ −1^[1]
6	$a\uparrow \uparrow \uparrow \uparrow b$ or $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}}$	iper6, esazione	a, b interi ≥ −1^[1]

Note

^ ^a ^b ^c Sia x = a[n](-1). Dalla formula ricorsiva, a[n]0 = a[n-1](a[n](-1)) => 1 = a[n-1]x. Una soluzione è x = 0, perché a[n-1]0 = 1 da definizione quando n ≥ 4. Questa soluzione è unica, perché a[n-1]b > 1 per ogni a > 1, b > 0 (prova da ricorsione).