Oggi passiamo ad una nuova classe di funzioni ricorsive: le funzioni ricorsive generali. Come anticipato, attraverso questo schema è possibile definire anche le funzioni parziali.

Ci si può riferire a questa classe anche con il termine funzioni µ-ricorsive, per la presenza dell’operatore di minimizzazione µ che ricerca i minimi numeri naturali di una proprietà data.

Nota: d’ora in avanti indicherò con lettere greche minuscole (di solito φ e ψ) le funzioni parziali.

Come abbiamo visto ieri tramite la funzione diagonale, le funzioni totali sono calcolabili, ma non sono tutte le funzioni calcolabili, ce ne mancano alcune: le funzioni parziali. La necessità di formalizzare anche le funzioni parziali nasce dal fatto che hanno senso di esistere molte funzioni parziali intuitivamente calcolabili (e.g. la funzione divisione intera div(x, y) che non è definita se y = 0).

La diagonalizzazione non si applica alle funzioni parziali. Vediamo:

che è equivalente alla funzione diagonale che abbiamo visto ieri per le funzioni totali: \(g(x) = f_x(x) + 1\) .

Supponiamo che φ (ed f) sia rappresentata dall’n-esimo algoritmo: ieri abbiamo detto che \(\forall n.g(n) \ne f_n(n)\) perché la f vale sempre 1 in meno di g. Lo stesso non possiamo dire di φ e ψ perché sappiamo che \(\exists x. \psi_x(x)\uparrow\) .

Funzioni ricorsive generali

Definizione: la classe \(\mathcal{R}\) delle funzioni µ-ricorsive o ricorsive generali è la minima classe che soddisfa le condizioni:

1. le proprietà 1-5 delle funzioni ricorsive primitive.
2. (Minimizzazione) Se \(\varphi(x_1,...,x_n,y) \in \mathcal{R}\) in n + 1 variabili, allora è ricorsiva generale la funzione:
   $$ \psi(x_1,...,x_n) = \mu y[\varphi(x_1,...,x_n,y) = 0 \wedge \forall z \leq y . \varphi(x_1,...,x_n,z) \downarrow] $$

Qui il significato di \(\mu y\) è quello di trovare il minimo \( y \in \mathbb{N}\) per cui è vera la proprietà tra parentesi.
Nel caso in cui \(\varphi(x_1,...,x_n,y) \in \mathcal{C}\) possiamo semplificare la definizione in quanto una funzione ricorsiva primitiva converge per ogni argomento:

Una funzione \(\psi\) così definita è intuitivamente calcolabile perché l’algoritmo intuitivo che la calcola è composto da un ciclo che parte con y = 0 e calcola \(\varphi(x_1,...,x_n, 0)\) , se è 0 allora \(\psi(x_1,...,x_n) = 0\) , altimenti incrementa y e continua.

In pratica l’operatore µ corrisponde ad un ciclo while che incrementa y ad ogni iterazione. Potrebbe accadere che il ciclo non termini mai perchè la \(\varphi\) restituisce sempre valori diversi da 0 o perché per i primi k naturali la \(\varphi\) diverge almeno una volta: in entrambi i casi la funzione non converge e non possiamo calcolarla: abbiamo trovato una funzione parziale.

Esempio di funzione µ-ricorsiva parziale: la funzione ovunque indefinita è l’archetipo delle funzioni parziali ed è ovviamente calcolabile.

La funzione \(\varphi\) è una funzione ricorsiva primitiva che presi due argomenti restituisce la costante 3. È banalmente ovunque definita e totale e non vale mai 0. La funzione \(\psi\), che fa uso dell’operatore µ applicato a y, non riuscirà mai a trovare un caso in cui \(\phi(x, y) = 0\) e quindi risulterà che \(\psi\) è ovunque indefinita.

Nota: le funzioni µ-ricorsive totali possono essere chiamate ricorsive per ragioni storiche. Quindi, per esempio, la funzione di Ackermann è ricorsiva, ma non è ricorsiva primitiva.

µ-calcolabilità

Analogamente a quanto detto per le macchine di Turing e per i programmi WHILE, diciamo che una funzione è µ-calcolabile quando la sua definizione è µ-ricorsiva.

Sia le funzioni µ-calcolabili, che quelle WHILE-calcolabili, che quelle Turing calcolabili, formano esattamente la stessa classe di funzioni calcolabili. Possiamo dire che sono Turing equivalenti.

Tesi di Church-Turing

Le funzioni (intuitivamente) calcolabili sono tutte e sole le funzioni (parziali) Turing-calcolabili.

È una tesi sulla natura delle funzioni calcolabili, indipendentemente formulata da Alonzo Church e Alan Turing nel 1936.

Questa tesi è accettata quasi universalmente e non può essere provata formalmente in quanto il concetto di “intuitivamente calcolabile” è solo definito informalmente. Tutti i tentativi di formalizzazione della calcolabilità che sono avvenuti successivamente, si sono dimostrati Turing-equivalenti e hanno rafforzato ancora di più la tesi di Church-Turing.