Visualizza wikitesto di Notazione a frecce di Knuth

{{F|matematica|agosto 2012}}

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 [[esponenziazione|esponenziale]] sarebbero impossibili da scrivere, come il [[numero di Graham]].

== Definizione ==
La ''sequenza di iperoperazione'' è una sequenza di operazioni binarie <math>H_n(a,b) \,:\, (\mathbb{N}_0)^3 \rightarrow \mathbb{N}_0\,\!</math>, definita ricorsivamente come segue:

:<math>
  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}\,\!
</math>

(Notare che ''n'' = 0, l'[[operazione binaria]] essenzialmente si riduce a un'operazione unaria ([[Assiomi di Peano|funzione successiva]]) ignorando il primo argomento.)

Per ''n'' = 0, 1, 2, 3, questa definizione riproduce le operazioni di base dell'aritmetica della [[Assiomi di Peano|funzione successiva]] (che è un'operazione unaria), addizione, moltiplicazione e [[esponenziazione]], come:

:<math>H_0(a,b) = b + 1\,\!,</math>
:<math>H_1(a,b) = a + b\,\!,</math>
:<math>H_2(a,b) = a \cdot b\,\!,</math>
:<math>H_3(a,b) = a^{b}\,\!,</math>
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
:<math>H_4(a,b) = a\uparrow\uparrow{b}\,\!,</math>
:<math>H_5(a,b) = a\uparrow\uparrow\uparrow{b}\,\!,</math>
:...
:<math>H_n(a,b) = a\uparrow^{n-2}b \text{ per } n \ge 3\,\!,</math>
:...

== Descrizione ==
Questa [[Panoramica storica delle notazioni matematiche|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 (<math>\uparrow \uparrow</math>) rappresenta una [[tetrazione]], ovvero una [[potenza ricorsiva]];
* tre frecce (<math>\uparrow \uparrow \uparrow</math>) 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:<br />
<math>3\uparrow \uparrow 3=3^{3^3}=3^{27}=7625597484987</math><br />
<math>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. 
</math> volte<br />
e via dicendo.

== Esempi ==
{| class="wikitable"
|-
! ''n''
! Operazione<br />(''H<sub>n</sub>''(''a'', ''b''))
! Definizione
! Nomi
! Dominio
|-
! 0
| <math>1 + b</math>
| <math>{ 1 + {\underbrace{1 + 1 + 1 + \cdots + 1} \atop{b \mbox{ copie di 1}}} }</math>
| iper0, incremento, [[assiomi di Peano|funzione successiva]], 
| arbitrario
|-
! 1
| <math>a + b</math>
| <math>{ a + {\underbrace{1 + 1 + 1 + \cdots + 1} \atop{b \mbox{ copie di 1}}} }</math>
| iper1, [[addizione]]
| arbitrario
|-
! 2
| <math>a\cdot b</math>
| <math>{ {\underbrace{a + a + a + \cdots + a}} \atop{b \mbox{ copie di } a} }</math>
| iper2, [[moltiplicazione]]
| arbitrario
|-
! 3
| <math>a^b</math> o <math>a \uparrow b</math>
| <math>{ {\underbrace{a \cdot a \cdot a \cdot a \cdot \ldots \cdot a}} \atop{b \mbox{ copie di } a} }</math>
| iper3, [[esponenziazione]]
| ''b'' reale, con alcune estensioni multivalore nei [[numeri complessi]] 
|-
! 4
| <math>^{b}a</math> o <math>a \uparrow\uparrow b</math>
| <math>{ {\underbrace{a \uparrow (a \uparrow (a \uparrow (a \uparrow \cdots \uparrow a))...)}} \atop{b \mbox{ copie di } a} }</math>
| iper4, [[tetrazione]]
| ''a'' ≥ 0 o un intero, ''b'' un intero ≥ −1<ref name="nega">Sia ''x'' = ''a''[''n''](-1). Dalla formula ricorsiva, ''a''[''n'']0 = ''a''[''n''-1](''a''[''n''](-1)) => 1 = ''a''[''n''-1]''x''. Una soluzione è ''x'' = 0, perché ''a''[''n''-1]0 = 1 da definizione quando ''n'' ≥ 4. Questa soluzione è unica, perché ''a''[''n''-1]''b'' > 1 per ogni ''a'' > 1, ''b'' > 0 (prova da ricorsione).</ref> (con alcune estensioni proposte) <!-- first option matches the first option in hyper3, second option matches the second option in hyper3 -->
|-
! 5
| <math>a \uparrow\uparrow\uparrow b</math> o <math>a \uparrow^3 b</math>
| <math>{ {\underbrace{a \uparrow\uparrow (a \uparrow\uparrow (a \uparrow\uparrow (a \uparrow\uparrow \cdots \uparrow\uparrow a))...)}} \atop{b \mbox{ copie di } a} }</math>
| iper5, [[pentazione]]
| ''a'', ''b'' interi ≥ −1<ref name="nega"/>
|-
! 6
| <math>a \uparrow\uparrow\uparrow\uparrow b</math> o <math>a \uparrow^4 b</math>
| <math>{ {\underbrace{a \uparrow^3 (a \uparrow^3 (a \uparrow^3 (a \uparrow^3 \cdots \uparrow^3 a))...)}} \atop{b \mbox{ copie di } a} }</math>
| iper6, esazione
| ''a'', ''b'' interi ≥ −1<ref name="nega"/>
|}

== Note ==
<references/>

== Voci correlate ==
* [[Elevamento a potenza]]
* [[Tetrazione]]
* [[Numero di Graham]]

== Collegamenti esterni ==
* {{Collegamenti esterni}}

{{Portale|matematica}}

[[Categoria:Notazioni matematiche]]