Notazione a frecce di Knuth

Da Wikipedia, l'enciclopedia libera.

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[modifica | modifica wikitesto]

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 \ge 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 ad una 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 è una operazione unaria), addizione, moltiplicazione e esponenziazione, rcome:

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 pern ≥ 4 estende queste operazioni di base oltre l'esponenziazione in quella che può essere scritta 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[modifica | modifica wikitesto]

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:

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[modifica | modifica wikitesto]

n Operazione
(Hn(a, b))
Definizione Nomi Dominio
0 1 + b { 1 + {\underbrace{1 + 1 + 1 + \cdots + 1} \atop{b \mbox{ copies of 1}}} } iper0, incremento, funzione sussessiva, arbitrario
1 a + b { a + {\underbrace{1 + 1 + 1 + \cdots + 1} \atop{b \mbox{ copies of 1}}} } iper1, addizione arbitrario
2 a\cdot b { {\underbrace{a + a + a + \cdots + a}} \atop{b \mbox{ copies of } a} } iper2, moltiplicazione arbitrario
3 a^b or a \uparrow b { {\underbrace{a \cdot a \cdot a \cdot a \cdot \ldots \cdot a}} \atop{b \mbox{ copies of } a} } iper3, esponenziazione b reale, con alcune estensioni mutlivalore 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{ copies of } a} } iper4, tetrazione a ≥ 0 o un intero, b un intero ≥ −1[nb 1] (con alcune estensioni proposte)
5 a \uparrow\uparrow\uparrow b or a \uparrow^3 b { {\underbrace{a \uparrow\uparrow (a \uparrow\uparrow (a \uparrow\uparrow (a \uparrow\uparrow \cdots \uparrow\uparrow a))...)}} \atop{b \mbox{ copies of } a} } iper5, pentazione a, b interi ≥ −1[nb 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{ copies of } a} } ipyper6, esazione a, b interi ≥ −1[nb 1]

Note[modifica | modifica wikitesto]

Voci correlate[modifica | modifica wikitesto]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica


Errore nell'uso delle note: Sono presenti dei marcatori <ref> per un gruppo chiamato "nb" ma non è stato trovato alcun marcatore <references group="nb"/> corrispondente, o manca la chiusura </ref>