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 $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 (Hn(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 (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
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

Voci correlate

• Elevamento a potenza
• Tetrazione
• Numero di Graham

Collegamenti esterni

• (EN) Eric W. Weisstein, Notazione a frecce di Knuth, su MathWorld, Wolfram Research.