Funzione di Ackermann: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m Bot: es:Función de Ackermann è una voce che è stata in vetrina; modifiche estetiche |
Esempio di valore della funzione e del perchè compare in matematica |
||
Riga 19:
<br /><br />
La funzione di Ackermann è un esempio di [[funzione ricorsiva]] che non è [[funzione primitiva ricorsiva|primitiva ricorsiva]] poiché cresce più velocemente di qualsiasi funzione ricorsiva primitiva.
Il valore cresce molto rapidamente anche per valori molto piccoli di m e n. Per esempio, ''A''(4,2) è un numero integero of 19 729 cifre.<ref>[http://www.kosara.net/thoughts/ackermann42.html Decimal expansion of A(4,2)] {{Wayback|url=http://www.kosara.net/thoughts/ackermann42.html|date =20080317104411}}</ref> Per confronto, il [[Numero di Avogadro]] ha solo 64 cifre.
Il meccanismo di calcolo della funzione è estremamente semplice quanto pesante dal punto di vista computazionale. La definizione data può essere vista come quella di una famiglia di funzioni al variare di un parametro individuato dalla prima variabile. Per ogni valore del parametro si ha una funzione che è ottenuta iterando la funzione precedente per un numero di volte individuato dalla seconda variabile. In quest'ottica le prime funzioni della famiglia sono funzioni familiari come l'[[addizione]], la [[moltiplicazione]] e la [[potenza (matematica)|potenza]], e successivamente si hanno funzioni sempre più complesse:
Line 28 ⟶ 30:
Risulta quindi una funzione con una complessità estremamente elevata anche per valori di input semplici.
L'inversa della funzione di Ackermann compare in alcune dimostrazioni di scienze informatiche, come nell'algoritm [[Union Find]]
== Voci correlate ==
| |||