Definizione generale. Le funzioni ricorsive primitive sono una classe di funzioni matematiche definite su numeri naturali (ℕ → ℕ, o più generalmente ℕⁿ → ℕ) costruite a partire da un insieme minimo di funzioni di base, mediante due sole operazioni combinatorie: la composizione e la ricorsione primitiva. Gödel le utilizzò come strumento tecnico centrale nella dimostrazione dei teoremi di incompletezza (1931), per dimostrare che ogni proprietà “effettivamente calcolabile” della sintassi di un sistema formale può essere codificata aritmeticamente.

Le funzioni di base. La classe delle funzioni ricorsive primitive parte da tre tipi di funzioni elementari, considerate “banalmente calcolabili”:

1. funzione zero: Z(x) = 0, per ogni x;
2. funzione successore: S(x) = x + 1;
3. funzioni di proiezione (o identità): Pᵢⁿ(x₁, …, xₙ) = xᵢ, che selezionano l’i-esimo argomento tra n.

Le operazioni di costruzione. A partire da queste funzioni base, si costruiscono nuove funzioni tramite due sole regole:

1. Composizione: se g è una funzione a m argomenti, e h₁, …, hₘ sono funzioni a n argomenti, allora è possibile definire:

f(x₁, …, xₙ) = g(h₁(x₁, …, xₙ), …, hₘ(x₁, …, xₙ)).

In pratica: si “incastrano” funzioni già definite l’una dentro l’altra, esattamente come nella composizione ordinaria di funzioni matematiche.

2. Ricorsione primitiva: questa è l’operazione più caratteristica e potente. Data una funzione g (a n argomenti) e una funzione h (a n+2 argomenti), si definisce una nuova funzione f (a n+1 argomenti) tramite lo schema:

• caso base: f(x₁, …, xₙ, 0) = g(x₁, …, xₙ);
• passo induttivo: f(x₁, …, xₙ, y+1) = h(x₁, …, xₙ, y, f(x₁, …, xₙ, y)).

In altre parole, il valore della funzione per y+1 si ottiene sfruttando il valore già calcolato per y — esattamente come nella definizione ricorsiva a cui siamo abituati (es. il fattoriale o la successione di Fibonacci). Una funzione ricorsiva primitiva è, per definizione, qualsiasi funzione ottenibile dalle funzioni base tramite un numero finito di applicazioni di composizione e ricorsione primitiva.

Esempi concreti.

Addizione: definita per ricorsione primitiva sul secondo argomento:

• add(x, 0) = x
• add(x, y+1) = S(add(x, y))

Moltiplicazione: definita usando l’addizione già costruita:

• mult(x, 0) = 0
• mult(x, y+1) = add(mult(x, y), x)

Fattoriale:

• fact(0) = 1
• fact(y+1) = mult(fact(y), y+1)

Predecessore (con convenzione pred(0) = 0):

• pred(0) = 0
• pred(y+1) = y

Si può notare come, con pazienza, quasi tutte le funzioni aritmetiche “usuali” (potenza, funzione resto, massimo comun divisore, ecc.) siano costruibili con questo schema.

Il ruolo cruciale nei Teoremi di Incompletezza. Gödel utilizzò le funzioni ricorsive primitive come cardine tecnico della sua dimostrazione, per un motivo preciso: Gödel osservò (e successivamente Church, Kleene e Turing confermarono con approcci indipendenti) che la classe delle funzioni ricorsive primitive coincide, in larghissima parte, con l’intuizione di “funzione calcolabile mediante un algoritmo”. Questo fu un passo fondamentale verso la formalizzazione del concetto di calcolabilità, che sfociò poi nella tesi di Church-Turing.

La codifica gödeliana (Gödel numbering). Per dimostrare l’incompletezza, Gödel doveva:

1. codificare ogni formula e ogni dimostrazione del sistema formale come un numero naturale (la celebre numerazione di Gödel, basata sulla fattorizzazione unica in numeri primi);
2. dimostrare che proprietà sintattiche come “x è il codice di una formula ben formata” o “x è il codice di una dimostrazione valida di y” sono esprimibili come funzioni (o predicati) ricorsive primitive;
3. dimostrare che, essendo ricorsive primitive, queste proprietà sono a loro volta rappresentabili all’interno del sistema aritmetico stesso (tramite un lemma di rappresentabilità).

Questo passaggio è essenziale: se la nozione di “dimostrazione valida” non fosse esprimibile aritmeticamente in modo così elementare, tutta la costruzione dell’enunciato autoreferenziale G (“questo enunciato non è dimostrabile”) non potrebbe essere formulata all’interno del sistema formale. Ma perché “primitiva” e non semplicemente “ricorsiva”? È importante notare una precisazione storica e tecnica: le funzioni ricorsive primitive non esauriscono tutte le funzioni intuitivamente calcolabili. Esistono funzioni calcolabili (come la funzione di Ackermann, scoperta pochi anni dopo) che crescono troppo rapidamente per essere catturate da questo schema, pur essendo effettivamente calcolabili con un algoritmo. Per questo motivo, negli anni successivi (1934), lo stesso Gödel — nelle sue Lezioni di Princeton — introdusse la nozione più generale di funzione ricorsiva generale (su suggerimento di una lettera di Herbrand), che ammette anche la ricorsione non limitata (o minimizzazione, l’operatore μ), risultando equivalente in potenza computazionale alle funzioni Turing-calcolabili e al λ-calcolo di Church. Questo passaggio dalle funzioni ricorsive primitive alle funzioni ricorsive generali fu un tassello decisivo nella nascita della teoria della calcolabilità. Facciamo un riassunto.

Concetto	Definizione
Funzioni di base	Zero, successore, proiezioni
Composizione	Incastro di funzioni già definite
Ricorsione primitiva	Definizione per casi: base + passo induttivo che usa il valore precedente
Classe risultante	Sottoinsieme proprio delle funzioni calcolabili (non tutte le funzioni calcolabili sono catturate)
Ruolo in Gödel (1931)	Strumento per codificare sintassi e dimostrabilità come proprietà aritmetiche
Limite	Non catturano funzioni “a crescita troppo rapida” (es. funzione di Ackermann)