Notazione a frecce di Knuth
# 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\$ 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 (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 |
