Funzioni ricorsive primitive - tesi di Church-Turing
Buonasera e auguri a tutti!
Per arrivare al primo teorema di Gödel a lezione abbiamo visto velocemente alcuni fatti sulle funzioni ricorsive. Per prima cosa abbiamo detto che le funzioni che vogliamo definire devono essere la controparte rigorosa del concetto intuitivo di "funzione computabile".
Abbiamo definito le funzioni base, cioè: la funzione successore $$S:\mathbb N\to\mathbb N,\qquad S(x)=x+1,$$
la funzione zero $$Z:\mathbb N\to\mathbb N,\qquad Z(x)=0$$ e, per ogni $n\in\mathbb N$ e per ogni $i\in\{1,...,n\}$, la funzione proiezione $$P_i^n:\mathbb N^n\to\mathbb N,\qquad P_i^n(x_1,\dots,x_n)=x_i.$$
Per una definizione induttiva di funzione ricorsiva primitiva, abbiamo detto che le funzioni base sono ricorsive primitive.
Poi, date delle funzioni ricorsive primitive $g,k_1,...,k_h$, abbiamo detto che se $f$ è definita da $$f(x_1,\dots,x_n)=g(k_1(x_1,dots,x_n),\dots,k_h(x_1,\dots,x_n)),$$ allora $f$ è ricorsiva primitiva, e si dice che è ottenuta con lo schema di composizione.
Infine, date delle funzioni $g$ e $h$ ricorsive primitive, se $f$ è definita da
$$\begin{cases}
f(x_1,\dots,x_n,0) & =\ g(x_1,\dots,x_n),\\
f(x_1,\dots,x_n,S(y)) & =\ h\big(x_1,\dots,x_n,y,f(x_1,\dots,x_n,y)\big),
\end{cases}$$ allora $f$ è ricorsiva primitiva, e si dice che è ottenuta mediante lo schema di ricorsione.
Le funzioni fin qui definite sono dette ricorsive primitive, e vediamo ora che non sono sufficienti a catturare la nozione intuitiva di "computabilità" in quanto c'è una funzione computabile che non è ricorsiva primitiva. A lezione abbiamo dato per scontato qualche preliminare: abbiamo detto che si può fornire un'enumerazione di tutte le funzioni ricorsive primitive, in particolare chiamiamo $f_0,f_1,f_2,...$ tutte le funzioni ricorsive primitive di una variabile. Definiamo ora la funzione $$g:\mathbb N\to\mathbb N,\qquad g(n)=f_n(n)+1.$$ Osserviamo che $g$ è calcolabile: infatti (per un'altra premessa) dato $n$ si trova la funzione $f_n$ nella enumerazione, si calcola $f_n(n)$ dato che $f_n$ è calcolabile, e infine si aggiunge 1. Vediamo che però $g$ non è ricorsiva primitiva. Infatti, se lo fosse, dovrebbe trovarsi nell'enumerazione di sopra, diciamo al posto $k$. E cioè $g=f_k$. Ma allora, per definizione di $g$, $$f_k(k)=g(k)=f_k(k)+1,$$ assurdo.
Quindi aggiungiamo altre funzioni, aggiungendo un nuovo schema oltre a quelli di composizione e ricorsione. E chiamiamo ricorsive tutte le funzioni ottenute. Le funzioni base di prima sono ricorsive, e sia $g:\mathbb N^{n+1}\to\mathbb N$ una funzione ricorsiva tale che per ogni $n$-upla $(x_1,...,x_n)$ esista almeno un $y$ tale che $g(x_1,---,x_n,y)=0$. Allora la funzione $f$ definita da $$f(x_1,\dots,x_n)=\min\{y\mid g(x_1,\dots,x_n,y)=0\}$$ è ricorsiva e si dice che è ottenuta con lo schema di minimalizzazione.
Ora, la mia domanda è: perché non funziona più il gioco di prima della $g$ per dire che esistono funzioni calcolabili che non sono funzioni ricorsive? Le funzioni ricorsive sono così tante di più rispetto alle ricorsive primitive da essere più che numerabili? Grazie!
Per arrivare al primo teorema di Gödel a lezione abbiamo visto velocemente alcuni fatti sulle funzioni ricorsive. Per prima cosa abbiamo detto che le funzioni che vogliamo definire devono essere la controparte rigorosa del concetto intuitivo di "funzione computabile".
Abbiamo definito le funzioni base, cioè: la funzione successore $$S:\mathbb N\to\mathbb N,\qquad S(x)=x+1,$$
la funzione zero $$Z:\mathbb N\to\mathbb N,\qquad Z(x)=0$$ e, per ogni $n\in\mathbb N$ e per ogni $i\in\{1,...,n\}$, la funzione proiezione $$P_i^n:\mathbb N^n\to\mathbb N,\qquad P_i^n(x_1,\dots,x_n)=x_i.$$
Per una definizione induttiva di funzione ricorsiva primitiva, abbiamo detto che le funzioni base sono ricorsive primitive.
Poi, date delle funzioni ricorsive primitive $g,k_1,...,k_h$, abbiamo detto che se $f$ è definita da $$f(x_1,\dots,x_n)=g(k_1(x_1,dots,x_n),\dots,k_h(x_1,\dots,x_n)),$$ allora $f$ è ricorsiva primitiva, e si dice che è ottenuta con lo schema di composizione.
Infine, date delle funzioni $g$ e $h$ ricorsive primitive, se $f$ è definita da
$$\begin{cases}
f(x_1,\dots,x_n,0) & =\ g(x_1,\dots,x_n),\\
f(x_1,\dots,x_n,S(y)) & =\ h\big(x_1,\dots,x_n,y,f(x_1,\dots,x_n,y)\big),
\end{cases}$$ allora $f$ è ricorsiva primitiva, e si dice che è ottenuta mediante lo schema di ricorsione.
Le funzioni fin qui definite sono dette ricorsive primitive, e vediamo ora che non sono sufficienti a catturare la nozione intuitiva di "computabilità" in quanto c'è una funzione computabile che non è ricorsiva primitiva. A lezione abbiamo dato per scontato qualche preliminare: abbiamo detto che si può fornire un'enumerazione di tutte le funzioni ricorsive primitive, in particolare chiamiamo $f_0,f_1,f_2,...$ tutte le funzioni ricorsive primitive di una variabile. Definiamo ora la funzione $$g:\mathbb N\to\mathbb N,\qquad g(n)=f_n(n)+1.$$ Osserviamo che $g$ è calcolabile: infatti (per un'altra premessa) dato $n$ si trova la funzione $f_n$ nella enumerazione, si calcola $f_n(n)$ dato che $f_n$ è calcolabile, e infine si aggiunge 1. Vediamo che però $g$ non è ricorsiva primitiva. Infatti, se lo fosse, dovrebbe trovarsi nell'enumerazione di sopra, diciamo al posto $k$. E cioè $g=f_k$. Ma allora, per definizione di $g$, $$f_k(k)=g(k)=f_k(k)+1,$$ assurdo.
Quindi aggiungiamo altre funzioni, aggiungendo un nuovo schema oltre a quelli di composizione e ricorsione. E chiamiamo ricorsive tutte le funzioni ottenute. Le funzioni base di prima sono ricorsive, e sia $g:\mathbb N^{n+1}\to\mathbb N$ una funzione ricorsiva tale che per ogni $n$-upla $(x_1,...,x_n)$ esista almeno un $y$ tale che $g(x_1,---,x_n,y)=0$. Allora la funzione $f$ definita da $$f(x_1,\dots,x_n)=\min\{y\mid g(x_1,\dots,x_n,y)=0\}$$ è ricorsiva e si dice che è ottenuta con lo schema di minimalizzazione.
Ora, la mia domanda è: perché non funziona più il gioco di prima della $g$ per dire che esistono funzioni calcolabili che non sono funzioni ricorsive? Le funzioni ricorsive sono così tante di più rispetto alle ricorsive primitive da essere più che numerabili? Grazie!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo