Notazione a frecce di Knuth

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 ${\displaystyle H_{n}(a,b)\,:\,(\mathbb {N} _{0})^{3}\rightarrow \mathbb {N} _{0}\,\!}$, definita ricorsivamente come segue:

${\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))&{\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:

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

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

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

${\displaystyle 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

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

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

...

${\displaystyle 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 (${\displaystyle \uparrow \uparrow }$) rappresenta una tetrazione, ovvero una potenza ricorsiva;
• tre frecce (${\displaystyle \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:

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

${\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{ 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 (Hn(a, b))	Definizione	Nomi	Dominio
0	${\displaystyle 1+b}$	${\displaystyle {1+{\underbrace {1+1+1+\cdots +1} \atop {b{\mbox{ copie di 1}}}}}}$	iper0, incremento, funzione successiva,	arbitrario
1	${\displaystyle a+b}$	${\displaystyle {a+{\underbrace {1+1+1+\cdots +1} \atop {b{\mbox{ copie di 1}}}}}}$	iper1, addizione	arbitrario
2	${\displaystyle a\cdot b}$	${\displaystyle {{\underbrace {a+a+a+\cdots +a} } \atop {b{\mbox{ copie di }}a}}}$	iper2, moltiplicazione	arbitrario
3	${\displaystyle a^{b}}$ o ${\displaystyle a\uparrow b}$	${\displaystyle {{\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	${\displaystyle ^{b}a}$ o ${\displaystyle a\uparrow \uparrow b}$	${\displaystyle {{\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	${\displaystyle a\uparrow \uparrow \uparrow b}$ o ${\displaystyle a\uparrow ^{3}b}$	${\displaystyle {{\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	${\displaystyle a\uparrow \uparrow \uparrow \uparrow b}$ o ${\displaystyle a\uparrow ^{4}b}$	${\displaystyle {{\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]