title: Notazione a frecce di Knuth
text: # 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 |
  