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 , definita ricorsivamente come segue:


(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, come:

e pern ≥ 4 estende queste operazioni di base oltre l'esponenziazione in quella che può essere scritta Notazione a frecce di Knuth come

...
...

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:

  • una singola freccia verso l'alto rappresenta un elevamento a potenza,
  • una doppia freccia verso l'alto () rappresenta una tetrazione, ovvero una potenza ricorsiva,
  • tre frecce () 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:

volte
e via dicendo.

Esempi[modifica | modifica wikitesto]

n Operazione
(Hn(a, b))
Definizione Nomi Dominio
0 iper0, incremento, funzione sussessiva, arbitrario
1 iper1, addizione arbitrario
2 iper2, moltiplicazione arbitrario
3 or iper3, esponenziazione b reale, con alcune estensioni mutlivalore nei numeri complessi
4 or iper4, tetrazione a ≥ 0 o un intero, b un intero ≥ −1[1] (con alcune estensioni proposte)
5 or iper5, pentazione a, b interi ≥ −1[1]
6 or ipyper6, esazione a, b interi ≥ −1[1]

Note[modifica | modifica wikitesto]

  1. ^ a b c Let 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. This solution is unique because a[n-1]b > 1 for all a > 1, b > 0 (prova da ricorsione).

Voci correlate[modifica | modifica wikitesto]

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