Nel 1928 il matematico tedesco Wilhelm Friederich Ackermann (Herscheid, 29 marzo 1896 – Lüdenscheid, 24 dicembre 1962) definì una funzione di grande importanza teorica, perché costituì il primo esempio di funzione ricorsiva, ma non primitiva ricorsiva.
Le funzioni primitive ricorsive sono quelle ottenibili applicando un numero finito di volte le tre seguenti funzioni base:
-
zero, funzione che produce zero per qualsiasi argomento;
-
successore, che dato un intero n produce n + 1;
-
selezione, che dati k argomenti e un intero n produce l’n-esimo argomento (con n ≤ k).
Queste funzioni possono essere combinate tramite gli operatori di composizione di funzioni e ricorsione.
Le approssimazioni di funzioni reali e le più comuni funzioni sugli interi (come divisione, fattoriale, calcolo dell’n-esimo numero primo) sono funzioni primitive ricorsive.
Le funzioni ricorsive, che corrispondono a quelle calcolabili tramite una macchina di Turing, si ottengono aggiungendo l’operatore di minimizzazione, che produce il minimo valore del primo argomento di una funzione che renda nullo il valore, se esiste.
Esistono infinite funzioni che sono ricorsive, ma non primitive ricorsive, ma non è facile individuarne una; Ackermann costruì il primo esempio:
I numeri A(n, n) sono noti come numeri di Ackermann. Il modo migliore per scriverli è tramite una notazione introdotta da Donald Ervin Knuth nel 1976 e così definita:
-
ab abbrevia a + a + a + a ... (somma di b addendi) ed equivale a a • b;
-
a ↑ b abbrevia a • a • a • a ... (prodotto di b termini) ed equivale a ab;
- a ↑↑ b abbrevia a ↑ a ↑ a ↑ a ... (a compare b volte);
-
a ↑↑↑ b abbrevia a ↑↑ a ↑↑ a ↑↑ a ... (a compare b volte);
-
a ↑↑↑↑ b abbrevia a ↑↑↑ a ↑↑↑ a ↑↑↑ a ... (a compare b volte);
-
e così via.
Attenzione però, che i calcoli devono essere svolti a partire da destra, quindi a ↑↑ 1 = a ↑ 1 = a; a ↑↑ 2 = a ↑ a = aa; a ↑↑ 3 = a ↑ (a ↑ a) = aaa.
La notazione di fatto definisce una sequenza di operazioni, ciascuna costituita dalla ripetizione della precedente, a partire dalla moltiplicazione come ripetizione dell’addizione, proseguendo con l’elevamento a potenza come moltiplicazione ripetuta, poi con l’elevamento a potenza iterato e così via.
L’n-esimo numero di Ackermann A(n, n) è definito come n ↑↑↑ ... n, con n frecce in mezzo, quindi il primo numero di Ackermann è 1 ↑ 1 = 1; il secondo è 2 ↑↑ 2 = 2 ↑ 2 = 4, il terzo è 3 ↑↑↑ 3 = 3 ↑↑ (3 ↑↑ 3) = 3 ↑↑ 333 = 3 ↑↑ 7625597484987 = 3 ↑ (7625597484987 ↑ 7625597484987) = 376255974849877625597484987.
Questo numero già è scomodo da scrivere come scala di potenze; per scrivere il quarto numero di Ackermann, 4 ↑↑↑↑ 4, non esiste altra notazione adeguata.
La dimostrazione del fatto che la funzione di Ackermann non è primitiva ricorsiva si basa proprio sul fatto che al crescere di n i numeri di Ackermann crescono più velocemente di qualsiasi funzione primitiva ricorsiva.
Bibliografia
- Koshy, Thomas; Fibonacci and Lucas Numbers with Applications, New York, John Wiley & Sons, 2001.