In questa lezione introduco un terzo formalismo per la formalizzazione di algoritmi: le funzioni ricorsive primitive. Con questo formalismo possiamo definire soltanto funzioni totali e, come vedremo, ciò è insufficiente per definire tutte le funzioni calcolabili.

Vediamo alcuni esempi classici.

Fattoriale

Definita con due equazioni: la prima è il caso base che si applica quando l’argomento è 0, la seconda è il caso ricorsivo che si applica per tutti i naturali positivi, ripetutamente finchè non ci si riconduce al caso base.

$$ \begin{cases} !(0) & = 1 \\ !(x+1) & = (x + 1) \times !(x) \\ !(x) & = x \times (x-1)! \end{cases} $$

Ovviamente, gli ultimi due casi sono equivalenti.

Un programma WHILE molto semplice:

fatt := 1
while 0 < x do
    fatt := fatt × x
    x := x - 1

Fibonacci

$$ \begin{cases} fib(0) & = 0 \\ fib(1) & = 1 \\ fib(x + 2) & = fib(x + 1) + fib(x) \\ \end{cases} $$

La funzione di Fibonacci può essere riscritta come formula chiusa non ricorsiva:

$$ fib(x) = {\sqrt 5 \over 5} ({1 + \sqrt 5 \over 2})^x - {\sqrt 5 \over 5} ({1 - \sqrt 5 \over 2})^x $$

λ-notazione

Usiamo la seguente λ-notazione per denotare una funzione a k argomenti:

$$ \lambda x_1,x_2,...,x_k.espressione $$

Questa notazione consente di definire funzioni anonime in modo molto compatto.

Una alternativa sono le funzioni con nome che possiamo scrivere in modo più familiare, ad esempio: \(somma(x, y) = x + y\) .

Funzioni ricorsive primitive

Questa è una classe di funzioni molto importante per la teoria della calcolabilità.

La classe delle funzioni primitive ricorsive è la minima classe di funzioni \(\mathcal{C} : \mathbb{N}^n, n \geq 0 \mapsto \mathbb{N}\) che hanno le seguenti propietà:

  1. Zero: \(\lambda x_1, ..., x_k.0 \text{ con } k \geq 0\)
  2. Successione: \(\lambda x.x+1\)
  3. Identità (o proiezioni): \(\lambda x_1, ..., x_k. x_i \text{ con } 1 \leq i \leq k\)

Queste 3 proprietà sono anche dette schemi primitivi di base. La classe C inoltre è chiusa per:

  1. Composizione: Se \(g_1,...,g_k \in \mathcal{C}\) sono funzioni in m variabili e \(h \in \mathcal{C}\) , è una funzione in k variabili, appartiene a C anche la loro composizione: \(\lambda x_1, ..., x_m . h(g_1(x_1,...,x_m), ..., g_k(x_1,...,x_m))\)
  2. Ricorsione primitiva: Se \(h \in \mathcal{C}\) è una funzione in k + 1 variabili, \(g \in \mathcal{C}\) è una funzione in k - 1 variabili, allora appartiene a C anche la funzione f in k variabili: \(\begin{cases}f(0,x_2,...,x_k) = g(x_2,...,x_k) \\ f(x_1 + 1,x_2,...,x_k) = h(x_1, f(x_1,...,x_k), x_2, ...., x_k)\end{cases}\) .

La proprietà 4 (composizione) ci permette di comporre non solo le funzioni ad 1 argomento, ma tutte le funzioni che hanno k argomenti possono essere composte con k funzioni ad m argomenti.

La proprietà 5 (ricorsione primitiva), è un po' più articolata. Se la compariamo con la definizione del fattoriale, possiamo notare alcune somiglianze: il caso base e il caso ricorsivo. La complicazione della definizione nasce dal voler trattare funzioni con un qualsiasi numero di argomenti. Infatti se poniamo che k = 1, si semplifica molto: \(\begin{cases}f(0) = g() \\ f(x_1 + 1) = h(x_1, f(x_1))\end{cases}\) .
Notiamo anche che g non ha argomenti: semplicemente è una costante. Se continuiamo con il paragone con il fattoriale, la costante è proprio 1, mentre la funzione h corrisponde con la funzione moltiplicazione.

Possiamo già dire che il fattoriale è una funzione ricorsiva primitiva.

La proprietà 1 e 2 ci consente di esprimere tutte le costanti naturali: applicando n volte il successore di 0 otteniamo qualsiasi naturale (vedi assiomi di Peano).

La classe C è la minima classe che soddisfa le proprietà 1-5. Per dimostrare che una funzione f faccia parte di C è necessario e sufficente dimostrare che ci sia una successione finita o derivazione della seguente forma:

$$ f_1,f_2,...,f_n \text{ tale che } f = f_n $$

\(\forall i \text{ tale che } 1 \leq i \leq n\) vale uno dei due casi:

  • \(f_i \in \mathcal{C}\) per le proprietà 1, 2 o 3 (cioè f è definita secondo gli schemi di base)
  • \(f_i\) è ottenuta mediante applicazione delle regole 4 e 5 da \(f_j, j \lt i\) , che risulta definita da funzioni definite precedentemente.

Esempio di funzione ricorsiva primitiva: \(f_5 = \lambda x,y.x+y\) (la somma di due naturali).

$$ \begin{align} &f_1 = \lambda x.x & (3 \\ &f_2 = \lambda x . x + 1 & (2 \\ &f_3 = \lambda x_1,x_2,x_3. x_2 & (3 \\ &f_4 = f_2(f_3(x_1, x_2, x_3)) & (4 \\ &f_5 = \begin{cases}f_5(0,x_2) = f_1(x_2) \\ f_5(x_1 + 1, x_2) = f_4(x_1, f_5(x_1,x_2), x_2)\end{cases} & (5 \end{align} $$

È un formalismo molto verboso! Però è anche formale, semplice e elegante. Meno semplice è capire che quelle 5 funzioni così combinate calcolino la somma!

Usando la regola di valutazione interna dinistra (redex interno) vogliamo calcolare 2 + 3 e otteniamo:

$$ \begin{align} & \underline{f_5(2,3)} = \\ & f_4(1, \underline{f_5(1, 3)}, 3) = \\ & f_4(1, f_4(0, \underline{f_5(0,3)}, 3), 3) = \\ & f_4(1, f_4(0, \underline{f_1(3)}, 3), 3) = \\ & f_4(1, \underline{f_4(0, 3, 3)}, 3), 3) = \\ & f_4(1, f_2(\underline{f_3(0, 3, 3)}), 3) = \\ & f_4(1, \underline{f_2(3)}, 3) = \\ & \underline{f_4(1, 4, 3)} = \\ & f_2(\underline{f_3(1, 4, 3)}) = \\ & \underline{f_2(4)} = \\ & 5 \end{align} $$

Alternativamente con la regola di valutazione esterna:

$$ \begin{align} & \underline{f_5(2,3)} = \\ & \underline{f_4(1, f_5(1, 3), 3)} = \\ & \underline{f_2(f_3(1, f_5(1, 3), 3))} = \\ & \underline{f_3(1, f_5(1, 3), 3)} + 1 = \\ & \underline{f_5(1, 3)} + 1= \\ & \underline{f_4(0, f_5(0,3), 3)} + 1 = \\ & \underline{f_2(f_3(0, f_5(0, 3), 3))} + 1 = \\ & \underline{f_3(0, f_5(0, 3), 3)} + 1 + 1 = \\ & \underline{f_5(0,3)} + 2 = \\ & \underline{f_1(3)} + 2 = \\ & 5 \end{align} $$

Possiamo estendere questo formalismo con dello zucchero sintattico, in modo da renderlo più espressivo.
Costruiamo altre funzioni concedendoci qualche facilitazione:

$$ \begin{align} & f_6 = f_5(f_1(x), f_1(x)) = \lambda x. 2 \times x \\ & f_7 = \lambda x,y.y \\ & f_8 = \lambda x,y.x \\ & \begin{cases} pred(0) & = & 0 \\ pred(x + 1) & = & f_8(x, pred(x)) \end{cases}\\ \end{align} $$

La funzione pred, che ovviamente restituisce il precedente, ha bisogno di \(f_8\), solo perché ciò è richiesto per applicare la regola 5.

$$ \begin{align} & f_9(x, y, z) = pred(f_3(x,y,z)) \\ & \begin{cases} f_{10}(0,y) & = & f_1(y) \\ f_{10}(x + 1, y) & = & f_9(x, f_{10}(x,y), y) \end{cases} \\ \end{align} $$

Qui \(f_9\) restituisce il precedente del secondo dei suoi argomenti, mentre \(f_{10}\) restituisce la differenza tra il primo e il secondo argomento.

Usando un formalismo esteso, che ci semplifica la vita, possiamo definire le operazioni aritmetiche come funzioni ricorsive primitive:

$$ \begin{align} &Somma & \begin{cases} 0 + y & = y \\ (x + 1) + y & = (x + y) + 1 \end{cases} \\ &Moltiplicazione & \begin{cases} 0 \times y & = 0 \\ (x + 1) \times y & = (x \times y) + y \end{cases} \\ &Potenza & \begin{cases} x^0 & = 1 \\ x^(y+1) & = x \times (x \times x^y) \end{cases} \end{align} $$

Esempi di funzioni ricorsive primitive notevoli:

  • \(R=\{x \in \mathbb{N} | x \text{ è un numero primo}\}\)
  • la funzione \((x)_i\) che restituisce l’esponente dell’i-esimo fattore \(p_i\) della fattorizzazione di \(x = p_0^{x_0}p_1^{x_1}\cdot\cdot\cdot p_k^{x_k}\)
  • le funzioni di codifica

Possiamo sfruttare queste funzioni per definire una codifica delle macchine di Turing.

Ogni quintupla \((q_i,\sigma_j,q_k,\sigma_l,D) \in \delta\) è codificata come:

$$ p_0^{i+1} \times p_1^{j+1} \times p_2^{k+1} \times p_3^{l+1} \times p_4^{m_D} $$
con \(p_0 < p_1 < p_2 < p_3 < p_4\) numeri primi.

Con il teorema di unica fattorizzazione notiamo che questa funzione proposta è iniettiva perché a ogni quintupla viene associato un solo naturale. Tuttavia non è surgettiva perché non è detto che dato un naturale riesca a ottenere una MdT valida. Quindi non è una codifica vera e propria.

Possiamo codificare sequenze di quintuple ed ottenere sequenze di naturali, che possiamo codificare a loro volta con un procedimento simile alla codifica a coda di colomba, ottenedo un singolo intero che codifica un’intera MdT M.

Esiste una funzione di codifica biunivoca che è stata proposta per la prima volta da Kurt Gödel. Il procedimento viene chiamato gödelizzazione.

In fondo un computer carica in memoria un programma sotto forma di una sequenza di bit che possiamo interpretare come un numero naturale.

Funzione di Ackermann

Non è definibile mediante gli schemi di ricorsiva primitiva (1-5), ma è una funzione totale con una definizione che a intuito torna.
Si tratta della funzione così definita:

$$ \begin{cases} & A(0, 0, y) & = y \\ & A(0, x + 1, y) & = A(0, x, y) + 1 \\ & A(1, 0, y) & = 0 \\ & A(z + 2, 0 ,y) & = 1\\ & A(z + 1, x + 1, y) & = A(z, A(z + 1, x, y), y) \end{cases} $$

Da cui possiamo derivare che:

$$ \begin{align} & A(0, x, y) & = y + x \\ & A(1, x, y) & = x \times y \\ & A(2, x, y) & = y^x \\ & A(3, x ,y) & = y^{y^{\cdot^{\cdot^{\cdot^y}}} \rbrace x \text{ volte} } \end{align} $$

La funzione di Ackermann cresce più velocemente di qualsiasi funzione ricorsiva primitiva e chiama sè stessa ricorsivamente più di qualsiasi f.r.p. e infatti non appartiene alla classe C (non lo dimostriamo).

Come vedremo, non esiste un formalismo capace di esprimere tutte e sole le funzioni totali.

Diagonalizzazione

La diagonalizzazione è una tecnica che possiamo sfruttare per dimostrare che non possiamo calcolare tutte le funzioni totali per mezzo di un formalismo che riesce ad esprimere solo funzioni totali.

Teorema: La classe C delle funzioni primitive ricorsive non contiene tutte le funzioni intuitivamente calcolabili.

Schema di dimostrazione:

  1. Ogni derivazione di una funzione ricorsiva primitiva è una stringa finita di simboli presi da un alfabeto finito. Quindi tali rappresentazioni si possono enumerare, per esempio con la funzione di Gödel, e indichiamo con \(f_n\) la funzione definita dalla n-esima derivazione.
  2. Definisci una funzione diagonale \(g(x) = f_x(x) + 1\) . Questa funzione è intuitivamente calcolabile: prendi la x-esima funzione primitiva ricorsiva, applicala con argomento il suo stesso indice x e somma 1. Inoltre g è totale perché composta da funzioni totali.
  3. La funzione g non si trova nella lista delle funzioni ricorsive primitive, perché \(\forall n.g(n) \neq f_n(n) \Rightarrow \forall n.g \ne f_n\) cioè g non compare nell’elenco e quindi non è una funzione ricorsiva primitiva.

In realtà questo argomento può essere applicato ad ogni formalismo che riesce a rappresentare soltanto funzioni totali: basta associare ogni funzione definita dal formalismo con una macchina di Turing come nel passo 1 e proseguire.