March 1
La funzione di Ackermann - dal nome del suo scopritore, il matematico tedesco del 20 ° secolo Wilhelm Ackermann - è una delle funzioni più importanti nel campo dell'informatica. L'ingresso della funzione è di due numeri interi positivi, x ed y, e l'uscita è A (x, y) in forma di un numero intero positivo.
La definizione formale della funzione di Ackermann è:
A (x, y) = y + 1 se x = 0,
A (x, y) = A (x-1, 1) se y = 0,
o altrimenti A (x, y) = A (x-1, A (x y-1)).
La funzione è semplice da programmare, ma la sua caratteristica principale è la velocità con cui il suo valore cresce. Anche i valori di ingresso piccoli producono grandi numeri - A (4,2) è un intero con un totale di 19.729 cifre.
La funzione di Ackermann è Turing calcolabile, il che significa che il suo valore può essere calcolato con una macchina di Turing - una macchina di calcolo immaginaria inventata da matematico inglese Alan Turing. In altre parole, può essere valutato per tutti i possibili valori di input.
La funzione di Ackermann è l'esempio più semplice di una funzione calcolabile Turing che non è ricorsiva primitiva. In altre parole, la funzione Ackermann non può essere calcolato utilizzando semplici "per" loops, che applicano una sola operazione di un numero predeterminato di volte. Piuttosto, può essere calcolato solo utilizzando un ciclo "while", che continua a ripetere e azione fino una condizione di test associato restituisce false. Il numero di iterazioni, o ripetizioni, della ricorsione, o ciclo di feedback, necessaria per calcolare la funzione di Ackermann non è noto in anticipo. Il numero di iterazioni è, infatti, parte del calcolo e aumenta il calcolo continua.
Come primo argomento agli aumenti di funzione Ackermann, si va in modo efficace da operazioni aritmetiche classiche, come l'addizione e la moltiplicazione, ai poteri e le torri di potenza. Molto grandi numeri, ad esempio un googolplex - 1 seguito da un googol o 10 ^ 100, zeri - possono essere espressi come una torre di potenza, nella forma 10 ^ (10 ^ 100) o, in inglese, 10 alla potenza di (10 alla potenza di 100). I valori crescono così in fretta che hanno bisogno di una particolare forma di notazione abbreviata, nota come la notazione freccia su di Knuth. Infatti, la funzione di Ackermann dimostra l'esistenza di una serie infinita di nuove operazioni aritmetiche, o hyperoperations, che sono noti collettivamente come Grzegorczyk Gerarchia.