Funzione di Ackermann: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m Bot: Aggiungo il tag <references /> mancante |
m smistamento lavoro sporco e fix vari |
||
Riga 20:
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 <math>m</math> e <math>n</math>. Per esempio, <math>A(4,2)</math> è un numero intero di 19 729 cifre.<ref>[http://www.kosara.net/thoughts/ackermann42.html Decimal expansion of A(4,2)]
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:
| |||