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\to {\mathbb{N}}_0$, definita ricorsivamente come segue:

$H_n(a,b)=\{\begin{array}{cc}b+1& \text{se }n=0\\ a& \text{se }n=1,b=0\\ 0& \text{se }n=2,b=0\\ 1& \text{se }n\ge 3,b=0\\ H_{n-1}(a,H_n(a,b-1))& \text{altrimenti}\end{array}$

(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\ge 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{array}{cc}& 3\underbrace{\uparrow 3\uparrow 3\uparrow \dots \uparrow 3}\\ & 3\uparrow \uparrow 3\text{ volte }\end{array}=3\uparrow \uparrow 3^{27}=\begin{array}{c}{3}^{3^{{\cdot }^{{\cdot }^{{\cdot }^3}}}}\end{array}\}\begin{array}{c}7625597484987\end{array}$ volte
e via dicendo.

Esempi

n	Operazione (Hn(a, b))	Definizione	Nomi	Dominio
0	$1+b$	$1+\genfrac{}{}{0ex}{}{\underbrace{1+1+1+\cdots +1}}{b\text{ copie di 1}}$	iper0, incremento, funzione successiva,	arbitrario
1	$a+b$	$a+\genfrac{}{}{0ex}{}{\underbrace{1+1+1+\cdots +1}}{b\text{ copie di 1}}$	iper1, addizione	arbitrario
2	$a\cdot b$	$\genfrac{}{}{0ex}{}{\underbrace{a+a+a+\cdots +a}}{b\text{ copie di }a}$	iper2, moltiplicazione	arbitrario
3	$a^b$ o $a\uparrow b$	$\genfrac{}{}{0ex}{}{\underbrace{a\cdot a\cdot a\cdot a\cdot \dots \cdot a}}{b\text{ copie di }a}$	iper3, esponenziazione	b reale, con alcune estensioni multivalore nei numeri complessi
4	$b^{}a$ o $a\uparrow \uparrow b$	$\genfrac{}{}{0ex}{}{\underbrace{a\uparrow (a\uparrow (a\uparrow (a\uparrow \cdots \uparrow a))...)}}{b\text{ 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$	$\genfrac{}{}{0ex}{}{\underbrace{a\uparrow \uparrow (a\uparrow \uparrow (a\uparrow \uparrow (a\uparrow \uparrow \cdots \uparrow \uparrow a))...)}}{b\text{ copie di }a}$	iper5, pentazione	a, b interi ≥ −1
6	$a\uparrow \uparrow \uparrow \uparrow b$ o $a{\uparrow }^{4}b$	$\genfrac{}{}{0ex}{}{\underbrace{a{\uparrow }^3(a{\uparrow }^3(a{\uparrow }^3(a{\uparrow }^3\cdots {\uparrow }^{3}a))...)}}{b\text{ copie di }a}$	iper6, esazione	a, b interi ≥ −1

Voci correlate

• Elevamento a potenza
• Tetrazione
• Numero di Graham

Collegamenti esterni

• Template:Collegamenti esterni