02_programmi_ricorsive.tex

\chapter{Funzioni Ricorsive}
\label{lemma diagonalizzazione}

Lo scopo di questo capitolo \`e quello di dimostrare l'equivalenza tra
i concetti di calcolabilit\`a con registri e calcolabilit\`a con
programmi.  Iniziamo dunque a definire i programmi.

\section{I programmi}
Nella sezione precedente abbiamo visto come il contenuto dei registri,
nelle macchine a registri, possa essere modificato attraverso
determinate \emph{istruzioni} che la macchina \`e in grado di
riconoscere. Una sequenza di queste semplici istruzioni costituisce un
\emph{programma}.


\begin{programmi}
Chiamiamo programma P una sequenza finita non nulla di istruzioni etichettate
\end{programmi}

Chiameremo $x_i$, $x_j$ e $x_k$ variabili dove $i,j,k \in \mathbb{N}$. Assumeremo come convenzione,
che l'output di $P$ deve essere messo (dal programmatore) nella variabile $x_0$.
Inoltre l'ennupla $a_1, a_2, ..., a_n \in \mathbb{N}^k $ fornita come input al nostro programma verrà memorizzato nelle prime n variabili $x_1, ..., x_n$.
Assumiamo anche che tutte le variabili utilizzare nel nostro programma siano automaticamente inizializzate a zero e scriveremo $P(a_1, a_2, ..., a_n)$ per dire che eseguiamo $P$ con l'input $a_1, a_2, ..., a_n$.

Le istruzioni del programma possono essere:

\begin{enumerate}
\item $x_j \leftarrow 0$ assegna ad $x_j$ il valore zero. (azzeramento)
\item $x_j \leftarrow x_i $ assegna il contenuto di $x_i$ a $x_j$ (trasferimento)
\item $x_j \leftarrow x_j+1$ aumenta il contenuto di $x_j$ di uno e 
  riassegna il risultato come valore a $x_j$ (successsore)
\item $\textrm{if }(condizione) $ then goto $\alpha$ else goto $\beta$ con
  $\alpha$ e $\beta$ etichette di istruzioni del programma. (salto)
\end{enumerate}
	
Esempi di condizioni possono essere il confronto fra due variabili, il confronto di
una variabile con un numero naturale ecc..

\begin{nota}
Nella (\emph{4}) come condizione \`e possibile utilizzare 
una qualunque formula atomica di un linguaggio che usi le relazioni
$=,\geq,<$ e le operazioni $+,-,successore,\ldots $ e le loro
composizioni.
\end{nota}



\begin{extra}
Si scriva un programma in cui sia presente un'istruzione del tipo
(\emph{4}) avente per condizione $x_i\neq x_j$. (\emph{Suggerimento}:
si pensi ad una funzione in $(x_i,\ldots ,x_j)$ il cui valore sia
diverso da $0$ quando $x_i\neq x_j$)
\end{extra}	

\begin{extra}
Mostrare, con qualche esempio, che \`e possibile sostituire alla
condizione della (\emph{4}) una qualsiasi espressione di
calcolo \newline booleano classico.
\end{extra}	

Per eseguire una \emph{computazione} la macchina deve essere
fornita di un \emph{programma} $P$ e di una \emph{configurazione
  iniziale} (input), che pu\`o essere, ad esempio, una sequenza $a_1, a_2,
...$ di numeri naturali.
Supponiamo che $P$ sia composto da $s$ istruzioni $I_1, I_2,...,
I_s$.

Allora la macchina inizia la computazione eseguendo $I_1$, poi $I_2$,
e cos\`i via, a meno che non si incontri un'istruzione di \emph{goto}
che fa saltare la computazione in una delle $s$ istruzioni. La
computazione si ferma quando, e solo quando non c'\`e una prossima
istruzione oppure incontriamo la parola chiave \textbf{stop}.
Possiamo illustrare questo attraverso un esempio.
	
\begin{esempio} Consideriamo il seguente programma con $s=6$ istruzioni:
\begin{mylisting}
$I_1$: $\textrm{if }x_1 > x_2$ then goto $I_2$ else goto $I_5$
  \\ $I_2$: $x_2 \leftarrow x_2+1$\\ $I_3$: $x_3 \leftarrow
  x_3+1$\\ $I_4$: $\textrm{if }x_1 \neq x_2$ then goto $I_2$ else goto
  $I_5$\\ $I_5$: $x_0 \leftarrow x_3$\\
\end{mylisting}
E con la seguente configurazione iniziale:
\begin{mylisting}
$x_0 = 0, x_1 = 9, x_2 = 7, x_3 = 0, ...$
\end{mylisting}
Durante il calcolo le variabili vengono modificate come segue:
\begin{mylisting}	
$x_0 = 0, x_1 = 9, x_2 = 7, x_3 = 0, ...$ ($I_1: x_1 > x_2$)\\ $x_0 =
  0, x_1 = 9, x_2 = 8, x_3 = 0, ...$ ($I_2$)\\ $x_0 = 0, x_1 = 9, x_2
  = 8, x_3 = 1, ...$ ($I_3$)\\ $x_0 = 0, x_1 = 9, x_2 = 8, x_3 = 1,
  ...$ ($I_4: x_1 \neq x_2$)\\ $x_0 = 0, x_1 = 9, x_2 = 9, x_3 = 1,
  ...$ ($I_2$)\\ $x_0 = 0, x_1 = 9, x_2 = 9, x_3 = 2, ...$
  ($I_3$)\\ $x_0 = 0, x_1 = 9, x_2 = 9, x_3 = 2, ...$ ($I_4: x_1 =
  x_2$)\\ $x_0 = 2, x_1 = 9, x_2 = 9, x_3 = 2, ...$ ($I_5$)\\
\end{mylisting}	
\end{esempio}

\begin{nota}		
Al momento non poniamo la nostra concentrazione su quale funzione
calcola questo programma, ma ci limitiamo ad illustrare in quale modo
opera un programma in senso puramente meccanico.
\end{nota}

\begin{extra}
Dare un programma che memorizza in $x_0$ 1 se $x_1 > x_2$ e 0
altrimenti.
\end{extra}	

Per comprendere il significato del programma e l'andamento della
computazione \`e spesso conveniente desciverlo in modo informale
attraveso un \emph{Flow Chart}, per esempio il flow chart
rappresentante il programma dell'Esempio 1.1 \`e dato in Figura
1. Notare che i test contenuti nei rombi rappresentano le istruzioni
\emph{if then else} (4) che hanno quindi due prosecuzioni in base al
risultato del test; mentre i rettangoli sono le istruzioni di
successore o assegnazione che continuano sempre con la prossima
istruzione.
		
\begin{figure}[h] 
\begin{tikzpicture}[node distance = 1.6 cm, auto]
 % Place nodes
   \node[noblock] (start) {START};
    \node [decision, below of=start] (I1) {$x_1 > x_2$};
    \node [block, below of=I1] (I2) {$x_2 \leftarrow x_2 + 1$};
    \node [block, below of=I2] (I3) {$x_3 \leftarrow x_3 + 1$};
    \node [decision, below of=I3] (I4) {$x_1 \neq x_2$};
    \node [block, below of=I4] (I5) {$x_0 \leftarrow x_3$};
   \node[noblock,below of=I5] (stop) {STOP};

    
    % Draw edges 
   \path [line] (start) -- (I1); \path [line] (I1) --
   node{yes}(I2); \path [line] (I1.east) -- ++(1.0,0) -- ++(0,-1) |-
   node [near start] {no}(I5.east); \path [line] (I2) -- (I3); \path
   [line] (I3) -- (I4); \path [line] (I4.west) -- ++(-.8,0) --
   ++(-.8,0) |- node [near start] {yes}(I2.west); \path [line] (I4)
   --node{no} (I5); \path [line] (I5) -- (stop);
\end{tikzpicture}
\caption{Flow Chart}   
	
\end{figure}
	
Dall'esempio 1 notiamo inoltre come il comando \emph{goto} nella
definizione dell'\emph{if} renda possibile l'esecuzione di cicli,
infatti l'istruzione $I_4$ riporta l'esecuzione all'istruzione $I_2$
tante volte fino a quando la condizione $x_1 \neq x_2$ non viene
soddisfatta.
	
Pi\`u in generale possiamo dire che il comando \emph{goto} pu\`o
essere utilizzato per simulare quello che nei linguaggi ad alto livello conosciamo come 
ciclo \emph{for}. 
Infatti con $n$ fissato il ciclo:\\
$$ \left[
\begin{array}{l}
for \; $i = 1$ \; to \; $n$\\ \ \ \ \ \left[P\;
programma]\right. \\ next \; $i$\\
\end{array} \right.
\
$$ 
viene implementato dal programma nell'Esempio 1.2 dove $n$ è un opportuna variabile
che riceve in input il valore di $n$.

\newpage

\begin{esempio}

\begin{minipage}[c]{.50\textwidth}
\begin{mylisting}
 $I_1: x_i \leftarrow 0 $\\ 
 $I_2: x_i \leftarrow x_i + 1 $ \\
 $I_3: $ if $ n<x_i $ then goto stop else goto $I_4$ \\
 $I_4:  \left[ P\; programma \right ] $ \\
 $I_5: x_i \leftarrow x_i+1 $ \\
 $I_6 $ if $n < x_i $ then \\ \hspace{\stretch{1}} goto stop  else goto $I_4$\\

\end{mylisting}
\end{minipage}
\hspace{5mm}%
\begin{minipage}[c]{.50\textwidth}
\begin{tikzpicture}[node distance = 1.6 cm, auto]
    % Place nodes 
\node[noblock] (start) {START}; 
\node [block, below of=start] (I1) {$x_i \leftarrow 0$};
\node [block, below of=I1] (I2) {$x_i \leftarrow x_i+ 1$};
\node [decision, below of=I2] (I3) {$n < x_i$};
\node [block, below of=I3] (I4) {$ \left [ P \right] $};
\node [block, below of=I4] (I5) {$x_i \leftarrow x_i+ 1$};
\node [decision, below of=I5] (I6) {$n < x_i$};
\node[noblock,below of=I6] (stop) {STOP};

    % Draw edges
\path [line] (start) -- (I1);
\path [line] (I1) -- (I2);
\path [line] (I2) -- (I3);
\path [line] (I3.west) -- ++(-.8,0) -- ++(-.8,0) |- node [near start] {yes}(stop.west);
\path [line] (I3) -- node{no} (I4);
\path [line] (I4) -- (I5);
\path [line] (I5) -- (I6);
\path [line] (I6.east) -- ++(+.10,0) -- ++(+.8,0) |- node [near start] {no}(I4.east);
\path [line] (I6) --node{yes} (stop);

\end{tikzpicture}
\end{minipage}

\end{esempio}

\vspace{5mm}% 
	
\newpage

Ci chiediamo adesso, le quattro istruzioni che abbiamo introdotto sono tutte necessarie? 
E' possibile toglierne qualcuna e continuare a calcolare le stesse funzioni?
E immediato verificare che l'istruzione di trasferimento $x_j \leftarrow x_i$ può
essere scritta in funzione delle altre. Vediamo l'esempio:

\begin{esempio} utilizziamo le altre tre istruzioni per simulare il comportamento dell' istruzione di trasferimento:
\begin{mylisting}
$I_1$: $\textrm{if }x_j = x_i$ then goto stop else goto $I_2$\\
$I_2$: $x_j \leftarrow 0$\\
$I_3$: $x_j \leftarrow x_j +1$\\ 
$I_4$: $\textrm{if }x_j = x_i$ then goto stop else goto $I_2$\\
\end{mylisting}
\end{esempio}

Abbiamo quindi introdotto l'istruzione di trasferimento al solo fine di semplificare 
la scrittura dei nostri programmi.

Un altra domanda che sorge è: "senza l'istruzione di salto
riusciamo a calcolare le stesse funzioni di quante ne calcoleremo con tutte e quattro? Ebbene si può dimostrare che 
le uniche funzioni che possiamo calcolare senza l'istruzione di salto sono del tipo

\begin{enumerate}
\item $f(x) = m \, \, m \in  \mathbb{N} $ 
\item $f(x) = x+ m \, \,  \forall x ,  m \in  \mathbb{N} $ 
\end{enumerate}

\begin{extra}
Dimostrare che senza l'istruzione di if .. goto calcoliamo solo funzioni del tipo (1) e (2).
\end{extra}

\begin{extra}
Dimostrare che senza l'istruzione di if .. goto calcoliamo solo funzioni che sono totali.
\end{extra}

Questo fatto ci mostra che con tutta la sua semplicità l'istruzione di salto 
è importantantissima per calcolare quanto c'e di calcolabile e ciò si traduce nel fatto che
se il nostro linguaggio di programmazione preferito non disponesse dell' istruzione di salto 
esso servirebbe a ben poco.

Notiamo anche il fatto che non tutti i moderni linguaggi di programmazione 
dispongono dell'istruzione goto dovuto al fatto che l'uso questa istruzione 
è generalmente considerato indice di cattiva programmazione
ma ciò è stato rimpiazzato dall'uso delle cosiddette strutture di controllo iterative (for e while)
che implicitamente permettono di saltare in maniera controllata da un punto 
all'altro del programma.


\subsection{Funzioni calcolabili con un programma}

Abbiamo visto dei capitoli precedenti come in maniera naturale "leghiamo" il
concetto di macchina al concetto di funzione, così come in questo 
capitolo abbiamo legato il concetto di programma a quello di funzione.
Cioè è naturale pensare il calcolo del valore di una qualsiasi funzione $f(a_1, a_2, ... , a_n)$ 
per mezzo di un programma $P$ con configurazione iniziale $a_1, a_2, ... , a_n$.

In generale, la funzione associata ad un programma è parziale, anziché totale, in quanto tra le caratteristiche dei nostri programmi, rientra la
posibilità che, per certi input non venga prodotto alcun output.

Si consideri ad esempio il seguente programma:
	
\begin{mylisting}
$I_1$: if $x_i = x_i $ then goto $I_1$ else goto stop
\end{mylisting}	

che non termina mai. La condizione è sempre vera è ciò causa l'esecuzione
continua della stessa istruzione. La funzione calcolata
da questo programma la chiameremo funzione sempre indefinita.

Diamo adesso una definizione di funzione calcolabile con un programma.

\begin{programmi}
Una funzione $f$ si dice \emph{calcolabile da un programma} se,
$\exists$ un programma $P$ tale che per ogni $(a_1,...,a_n) \in \mathbb{N}^k$ 
$P(a_1,...,a_n)$ termina sse $(a_1,...,a_n) \in dom(f) $ e  $x_0=a$ se 
$f(a_1,...,a_n) = a$
\end{programmi}

\subsection{Equivalenza tra programmi e macchine a registri}

E' facile verificare che con una macchina a registri si possono
eseguire le stesse operazioni viste all'inizio della sezione (e
viceversa), e in effetti vale il seguente teorema.
\begin{progabaco}
Ogni funzione \'e computabile con un programma se e solo se \'e
computabile con una macchina a registri.
\end{progabaco}
\textsc{Dimostrazione} $(\Rightarrow)$ Vediamo come le macchine a
registri sono in grado di calcolare le quattro istruzioni che
costituiscono un programma:\\

\begin{enumerate}
\item 
 $x_j \leftarrow 0$ \hspace{10mm} \xymatrix{ \roundentry{j-}
  \ar@(ul,ul)[] \ar@(ul,dl)[] \ar[r] & stop }
 \vspace{10mm}

\item $x_j \leftarrow x_i $ \hspace{10mm} \xymatrix{ \roundentry{j-}  
  \ar@(ul,ul)[] \ar@(ul,dl)[] \ar[r] & \roundentry{i-} \ar[d]  \ar[r] &  
  \roundentry{42-} \ar@(dr,d)[d] \ar[r] & stop \\ & \roundentry{j+} \ar[d] & \roundentry{i+} \ar[u]
  \\ & \roundentry{42+} \ar@(dl,dl)[uu]}
\vspace{10mm}

\item $x_j \leftarrow x_j+1$ \hspace{10mm} \xymatrix{ \roundentry{j+}
  \ar@(ul,ul)[] \ar[d] \\ ...  }
\vspace{10mm}

\item $\textrm{if }x_i \neq0$ then goto $\alpha$ else goto
  $\beta$ \hspace{10mm} \xymatrix{ \roundentry{i-} \ar@(ul,ul)[]
  \ar[d] \ar[r] & \beta\\ \roundentry{i+} \ar[d] \\ \alpha }

\end{enumerate}
	
$(\Leftarrow)$ Si tratta di simulare con (1)$\rightarrow$(4) le
operazioni di una macchina a registri:
\begin{enumerate}
\item esegue l'incremento di uno, la prima operazione elementare di
  una macchina a registri;\\ \\
\hspace{10mm} \xymatrix{\roundentry{j+} \ar@(ul,ul)[] \ar[d] \\ ...}
\hspace{10mm} $x_j \leftarrow x_j+1$

\item la seconda operazione elementare sulle macchine a registri si
  ottiene usando (4) e ponendo in $\alpha$ un'istruzione che sottragga
  1 al registro se non \'e vuoto, altrimenti il programma esegue
  l'istruzione $else$ $\beta$, che corrisponde all'operazione di
  procedere a destra.\\ \\ \xymatrix{ \roundentry{i-} \ar@(ul,ul)[]
    \ar[d] \ar[r] & \beta\\ \alpha }
 \hspace{10mm} $\textrm{if }x_i \neq 0$ then goto $\alpha$ else goto
 $\beta$ \\ con $\alpha = x \stackrel{\centerdot}{-} 1$ e $\beta=$
 'procedi a destra'.
\end{enumerate}

\hspace{\stretch{1}} $\Box$\\
\begin{esempio}[Differenza]
\ Come esempio riportiamo il calcolo della funzione differenza
definita come segue:\\
\begin{center}
$n \stackrel{\centerdot}{-} m= \left\{ \begin{array}{ll} n-m &
    \textrm{se } m \leq n\\ 0 & \textrm{altrimenti}
\end{array} \right.$
\end{center} 

\begin{figure}[h]
\hspace{0cm} \xymatrix{ \roundentry{1-} \ar[r] \ar@(dr,d)[d] & stop
  \\ \roundentry{2-} \ar@(ul,ul)[] \ar[u] \ar[r] & \roundentry{1-}
  \ar[d] \ar[r] & stop \\ & \roundentry{42+} \ar@(d,dl)[u] }
\caption{Macchina a registri che calcola la differenza definita sui
  naturali $n \stackrel{\centerdot}{-} m$}
\end{figure}
	
\ \\ Tale funzione viene calcolata dalla macchina a registri in Figura
2 e dal programma o che abbiamo esaminato nell'Esempio 1.1.
\end{esempio}
	
	
Il teorema appena enunciato stabilisce la completa equivalenza tra i
concetti di calcolabilità con registri e calcolabilità con
programmi. Si noti come attraverso queste equivalenze si giunga ad un
livello di astrazione sempre maggiore, e come proprio questa
progressione ci fornisca strumenti via via pi\'u versatili attraverso
i passaggi per la dimostrazione dei teoremi di incompletezza.
				

\section{Funzioni primitive ricorsive}
Vogliamo definire ora una classe che comprenda tutte e sole le
funzioni calcolabili. Seguiremo a tale scopo Post, il quale si serve
di una definizione ricorsiva. Una definizione \`e detta
\emph{ricorsiva} quando ci\`o che \`e da definirsi viene definito
facendo ricorso a istanze pi\`u elementari dello stesso problema.
Tale metodo consiste nel:
\begin{itemize}
 \item fissare un insieme di funzioni iniziali immediatamente
   calcolabili quale base della procedura di definizione
 \item indicare alcune regole per derivare altre funzioni ricorsive da
   quelle date in partenza (regole che ovviamente preservino la
   calcolabilità delle funzioni derivate)
 \item escludere dalla classe delle funzioni ricorsive quelle funzioni
   che non siano le iniziali o da queste derivabili.
\end{itemize}
Diamo dunque la seguente definizione:

\begin{programmi}
Si dice \emph{funzione primitiva ricorsiva} un elemento della
classe definita induttivamente a partire dalle seguenti funzioni:
\begin{itemize}
\item [a.] la funzione nulla $z$ tale che $z(x)=0$;
\item [b.] la funzione proiezione $p^n_i$ tale che $p_i^n(x_1,\ldots
  ,x_n)=x_i$ $\forall i\leq n$
\item [c.]la funzione successore $s$ tale che $s(x) = x+1$;
\end{itemize}
\end{programmi}
	
Le regole per produrre nuove funzioni sono:
\begin{enumerate}
\item le operazioni di \emph{\emph{composizione}}, che date le
  funzioni primitive ricorsive $f: \mathbb{N}^k \rightarrow
  \mathbb{N}$ e $g_i : \mathbb{N}^n \rightarrow \mathbb{N}$ per $i= 1,
  ... , k$ permette di ottenere una funzione $h : \mathbb{N}^n
  \rightarrow \mathbb{N}$ per cui:\\ $
  h(x_1,.....,x_n)=f(g1(x_1,.....,x_n),....., g_k (x_1,.....,x_n))$
  \\ anch'essa primitiva ricorsiva.
\item lo schema di \emph{\emph{ricorsione primitiva}}, che date
  le funzioni primitive ricorsive $f: \mathbb{N}^k \rightarrow
  \mathbb{N}$ e $g : \mathbb{N}^{k+2} \rightarrow \mathbb{N}$, allora
  \`e primitiva ricorsiva anche la funzione $h : \mathbb{N}^{k+1}
  \rightarrow \mathbb{N}$ che soddisfi il sistema di equazioni:
\begin{center}
$\left\{ \begin{array}{ll} h(x_1,.....,x_n,0)= f(x_1,.....,x_n)
    \\ h(x_1,.....,x_n,s(y))=g(x_1,.....,x_n, y, h(x_1,.....,x_n,y))
				\end{array} \right.$
\end{center}
\end{enumerate}
\vspace{5mm}%
	
La classe delle funzioni primitive ricorsive \`e dunque \emph{chiusa
  rispetto alle operazioni di composizione e ricorsione
  primitiva}. Ora vedremo che questa classe di funzioni, che abbiamo
appena definito in termini matematici, \`e calcolabile dai programmi.


\begin{thm}
\emph{Ogni funzione primitiva ricorsiva è eseguibile da un programma
(e quindi calcolabile).}\end{thm}
\begin{proof}
Dobbiamo fare un programma per le tre funzioni di base, per la
composizione generalizzata e la ricorsione. Come sappiamo l' output è
per convenzione in $x_{0}$. Assumiamo anche in questa dimostrazione che 
se un programma P utilizza una variabile per la prima volta prima di usarla
azzeri il suo contenuto. Questa assunzione deve essere fatta perché
quando parleremo di ricorsione e composizione delle funzioni 
i programmi verranno eseguiti uno dopo l'altro e tra le loro possibilità rientra quella 
di utilizzare le stesse variabili usate dai programmi precedenti. Ciò assicura
che azzerando la variabile prima dell'uso non si trovino valori `sporchi`.

\begin{itemize}
\item[a.] Facciamo un programma per la funzione zero:
\begin{mylisting}
$I_1$: $x_{0}\leftarrow0$
\end{mylisting}

\item[b.] Il programma per il successore:\begin{mylisting}$I_1$:
  $x_{1}\leftarrow x_{1}+1$ \\$I_2:x_{0}\leftarrow x_{1} $\end{mylisting}

\item[c.] La proiezione:\begin{mylisting}$I_1$: $x_{0}\longleftarrow
  x_{i}$\end{mylisting}
\end{itemize}

\begin{enumerate}
\item La composizione: siano $F, G_1, G_2, \dots, G_k$ programmi che calcolano
  le funzioni $f,g_{1},...g_{k}$ rispettivamente. Dobbiamo far vedere che
  riusciamo ad esibire un programma $H$ che calcola la funzione $h$.
  L'output di ogni
  funzione viene salvato in $x_{0}$; quindi, poich\'e vogliamo salvare
  tutti i risultati intermedi del calcolo di $g_{1},\dots,g_{k}$
  dobbiamo copiare di volta in volta $x_0$ in una variabile che siamo
  sicuri che non sia usata da uno dei programmi. Inoltre dobbiamo
  riservarci dello spazio per le variabili di input poich\'e qualche
  programma potrebbe modificarle durante la sua esecuzione.  Per
  sapere dove possiamo salvare tutti questi valori dobbiamo sapere
  quali variabili vengono utilizzate dai programmi.
  Sia quindi
  $$\rho(Q)=max\left\{ i|x_{i}\leftarrow...\in Q\right\}$$
  il massimo indice di una variabile assegnata in $Q$ e
  $$\varepsilon=max\left\{
  \rho(G_{1}),....,\rho(G_{k}),\rho(F),k,n\right\}$$
  il massimo indice utilizzato nei programmi $F, G_1, \dots, G_k$.

Costruiamo il programma $H$ che calcola la composizione come segue:
salviamo l'input, che si trova in $x_{1},\dots,x_{n}$ in
$x_{\varepsilon+1},\dots,x_{\varepsilon+n}$, eseguiamo il programma
$G_1$ e copiamo l'output in $x_{\varepsilon+n+1}$:

\begin{mylisting}
$x_{\varepsilon+1}\leftarrow x_{1}$\\
$\vdots$\\
$x_{\varepsilon+n}\leftarrow x_{n}$\\
$[G_{1}]$\\
$x_{\varepsilon+n+1}\leftarrow x_{0}$
\end{mylisting}

Copiamo l'input:
\begin{mylisting}
$x_{1}\leftarrow x_{\varepsilon+1}$\\
$\vdots$\\
$x_{n}\leftarrow x_{\varepsilon+n}$
\end{mylisting}

Eseguiamo $G_{2}$ e copiamo l'output in $x_{\varepsilon+n+2}$;
ripetiamo questa operazione per tutti gli altri programmi fino ad
applicare il programma $G_{k}$ e copiare il suo output in
$x_{\varepsilon+n+k}$.

A questo punto tutti gli input per F si trovano in
$x_{\varepsilon+n+1},\dots,x_{\varepsilon+n+k}$.  Copiamo questi
valori in $x_{1},\dots,x_{k}$ e applichiamo il programma F:

\begin{mylisting}
$x_{1}\leftarrow x_{\varepsilon+n+1}$\\
$\vdots$\\
$x_{k}\leftarrow x_{\varepsilon+n+k}$\\
$[F]$
\end{mylisting}

Dopo questa sequenza di operazioni il risultato della composizione si
trova in $x_{0}$.

\item La ricorsione: sia $F$ un programma che calcola $f$ e $G$ un
  programma per $g$. Per realizzare un programma $H$ che calcola $h$
  dobbiamo innanzitutto salvare le variabili di input e i risultati
  parziali di $f$ e $g$ in variabili non utilizzate dai due programmi
  $F$ e $G$.

  Sia $\rho(Q)=max\left\{ i|x_{i}\leftarrow\dots \in Q\right\}$ il
  massimo indice utilizzato nel programma Q; definiamo
  $\varepsilon=max\left\{ \rho(F),\rho(G),k+2\right\}$ il massimo
  indice utilizzato per entrambi i programmi.

Allora, prima copiamo l'input e mettiamo 0 in $x_{\varepsilon+k+2}$
per cominziare la ricorsione (per calcolare $h(x,0)$). Adesso possiamo
applicare il programma $F$.

Poi dobbiamo guardare se l'$y$ che ci è stato dato all'inizio che copiamo
in $x_{\varepsilon+k+3}$ è uguale
a zero; se è cosi, il programma deve terminare. Se non è cosi, il
programma deve calcolare $h(x,s(y))$ (la prima volta $s(y)$ sarà
1). Il programma G utilizza come input $x_{1},\dots,x_{k}$ per
$x_{1},\dots,x_{k}$, $x_{k+1}$ per $y$ e $x_{k+2}$ per il risultato
parziale $h(x,y)$. Quindi dobbiamo mettere l'input iniziale in
$x_{1},\dots,x_{k}$, il risultato al passo precedente che si trova in
$x_{\varepsilon+k+2}$ dobbiamo copiarlo in $x_{k+1}$ e, dopo aver
eseguito $G$, dobbiamo copiare il suo output da $x_{0}$ in $x_{k+2}$.
Infine calcoliamo il successore di $y$ e controlliamo se equivale
all'$y$ iniziale: in caso affermativo dobbiamo terminare, altrimenti
torniamo ad eseguire il ciclo. Allora, il programa sarà:

\begin{mylisting}
$x_{\varepsilon+1}\leftarrow x_{1}$\\
$\vdots$\\
$x_{\varepsilon+k}\leftarrow x_{k}$\\
$x_{\varepsilon+k+3}\leftarrow x_{k+1}$ \\
$[F]$\\
$x_{\varepsilon+k+2}\leftarrow x_{0}$\\
$x_{\varepsilon+k+1}\leftarrow 0$\\
$I_t:\; $if$\; x_{\varepsilon+k+3}=x_{\varepsilon+k+1}\; $then goto$\;stop$ else goto $I_{t+1}$\\
$I_{t+1}:x_{1}\leftarrow x_{\varepsilon+1}$\\
$\vdots$\\
$x_{k}\leftarrow x_{\varepsilon+k}$\\
$x_{k+1}\leftarrow x_{\varepsilon+k+1}$\\
$x_{k+2} \leftarrow x_{\varepsilon+k+2}$\\
$[G]$\\
$x_{\varepsilon+k+2} \leftarrow x_0$\\
$x_{\varepsilon+k+1}\leftarrow x_{\varepsilon+k+1}+1$\\
$if \; x_0=x_0\; $ then goto $I_t$ else ...
\end{mylisting}
\end{enumerate}
\end{proof}

% Controllare
\subsection{Esempi di funzioni primitive ricorsive}

\begin{esempio}[somma]
$h:\mathbb{N}^2 \to \mathbb{N}$, $h(x,y)=x+y$.
Possiamo usare lo schema semplificato
$\left\{ \begin{array}{ll}
	x+0=x\\
	x+s(y)=s(x+y)
\end{array}\right.$.\\
Nel nostro schema di ricorsione la stessa funzione si ottiene con $h$
tale:\newline
$$\begin{array}{ll}
	h(x,0)=f(x)=p_1^1(x)=x\\
	h(x,s(y))=g(x,y,h(x,y))=s(p_3^3(x,y,h(x,y)))=s(h(x,y)).
\end{array}$$\newline
\end{esempio}
%
\begin{esempio}[prodotto]

 $h:\mathbb{N}^2 \to \mathbb{N}$, $h(x,y)=x \cdot y$ che possiamo scrivere
come
$\left\{ \begin{array}{ll}
	x \cdot 0=0\\
	x \cdot s(y)= x \cdot y + x
\end{array}\right.$ e quindi: \newline
$$\begin{array}{ll}
	h(x,0)=f(x)=z(x)\\
	h(x,s(y))=g(x,y,h(x,y))=p_3^1(x,y,h(x,y))+p_3^3(x,y,h(x,y)).
\end{array}$$\newline
\end{esempio}
%
\begin{esempio}[fattoriale] Per adattare la definizione della funzione
fattoriale
$h:\mathbb{N} \to \mathbb{N}$, $h(x)=x!$ allo schema generale si considera
$\left\{ \begin{array}{ll}
	0!=1\\
	s(y)! = y! \cdot s(y)
\end{array}\right.$ e quindi si pu\`o prendere $h$ come segue: \newline
$$\begin{array}{ll}
	h(x,0)=f(x)=s(z(x))=1\\
	h(x,s(y))=g(x,y,h(x,y))= s(p_3^2(x,y,h(x,y)))) \cdot p_3^3(x,y,h(x,y))=
\\
	\hspace{1.8cm} = s(y)\cdot h(x,y).
	\end{array}$$\newline
\end{esempio}
%
%
\begin{esempio}[elevamento a potenza] $h:\mathbb{N}^2 \to \mathbb{N}$,
$h(x,y)=x^y$:
$\left\{ \begin{array}{ll}
	x^0=1\\
	x^{s(y)} = x^y \cdot x
\end{array}\right.$ e quindi: \newline
$$\begin{array}{ll}
	h(x,0)=f(x)=s(z(x))=1\\
	h(x,s(y))=g(x,y,h(x,y))= p_3^1(x,y,h(x,y)) \cdot p_3^3(x,y,h(x,y)) =
x\cdot h(x,y).
	\end{array}$$\newline
\end{esempio}
%
%
\begin{esempio}[predecessore] $p:\mathbb{N} \to \mathbb{N}$ tale che
$\left\{ \begin{array}{ll}
	p(0)=0\\
	p(s(y)) = y
\end{array}\right.$ e quindi: \newline
$$\begin{array}{ll}
	p(0)=f=0\\
	p(s(y))=g(y,p(y))= p_2^1(y,p(y)).
	\end{array}$$\newline
\end{esempio}
%
%
\begin{esempio}[sottrazione] $h:\mathbb{N}^2 \to \mathbb{N}$,
$ h(x,y) = \left\{ \begin{array}{ll}
	x \stackrel{\centerdot}{-} y \ se \ y \leq x\\
	0 \ altrimenti
\end{array}\right.$ dunque: \newline
$$\begin{array}{ll}
	h(x,0)=f(x)=x\\
	h(x,s(y))=p(h(x,y)).
	\end{array}$$\newline
\end{esempio}
%
%
\begin{esempio}[segno] $sgn:\mathbb{N} \to \left\{0,1\right\}$,
$ sgn(y) = \left\{ \begin{array}{ll}
	0 \ se \ y = 0\\
	1 \ se \ y > 0
\end{array}\right.$ che si pu\`o scrivere come:
 \[ sgn(y) = y \stackrel{\centerdot}{-} p(y) \]
che \`e primitiva ricorsiva per quanto visto negli esempi precedenti.
\end{esempio}
%
%
\begin{esempio}[controsegno] $\overline{sgn}:\mathbb{N} \to
\left\{0,1\right\}$,
$ \overline{sgn}(y) = \left\{ \begin{array}{ll}
	1 \ se \ y = 0\\
	0 \ se \ y > 0
\end{array}\right.$ che si pu\`o pensare come:
 \[ \overline{sgn}(y) = 1 \stackrel{\centerdot}{-} sgn(y) \]
dunque \`e primitiva ricorsiva.
\end{esempio}
%
%
\begin{esempio}[] $f(\overrightarrow{x},y)= \sum_{i=0}^{y} g(\overrightarrow{x},
i)$ con $g$ primitiva ricorsiva, allora:\\
 $ f(\overrightarrow{x}, 0) = g(\overrightarrow{x}, 0)  $ \\
 $ f(\overrightarrow{x}, s(y)) = f(\overrightarrow{x}, y) +
g(\overrightarrow{x}, s(y)). $
\end{esempio}
%
%
\begin{esempio}[] $f(\overrightarrow{x},y)= \prod_{i=0}^{y}
g(\overrightarrow{x}, i)$ con $g$ primitiva ricorsiva, allora:\\
$	f(\overrightarrow{x}, 0) = g(\overrightarrow{x}, 0) $ \\
$ 	f(\overrightarrow{x}, s(y)) = f(\overrightarrow{x}, y) \cdot
g(\overrightarrow{x}, s(y)). $
\end{esempio}
%
%
\begin{esempio}[] $ \chi_{\geq}(x,y) = \left\{ \begin{array}{ll}
	1 \ se \ x \geq y\\
	0 \ altrimenti
\end{array}\right.$
\[ \chi_{\geq}(x,y) = sgn (s(x) \stackrel{\centerdot}{-} y) . \]
\end{esempio}
%
%
\begin{esempio}[valore assoluto] Basta scriverlo come
\[ \left|x - y \right| = (x \stackrel{\centerdot}{-} y) + ( y
\stackrel{\centerdot}{-} x) \]
oppure
\[ \left|x - y \right| = (x \stackrel{\centerdot}{-} y) \chi_{\geq}(x,y)  +
( y \stackrel{\centerdot}{-} x) (1 - \chi_{\geq}(x,y)) .\]
\end{esempio}
%
%
\begin{esempio}[] $f(\overrightarrow{x}) = \left\{ \begin{array}{ll}
	g_1(\overrightarrow{x})\ se\ vale\  R(\overrightarrow{x})\\
	g_2(\overrightarrow{x})\ altrimenti
\end{array}\right.$ con \\$\chi_R(\overrightarrow{x}) = \left\{
\begin{array}{ll}
	1\ se\ R(\overrightarrow{x})\ vale\\
	0\ altrimenti
\end{array}\right.$ con $g_1(\overrightarrow{x})$, $g_2(\overrightarrow{x})$
e $\chi_R(\overrightarrow{x})$ primitive ricorsive.\\
Allora
\[ f(\overrightarrow{x}) = g_1(\overrightarrow{x}) \chi_R(\overrightarrow{x}) +
 g_2(\overrightarrow{x}) (1 - \chi_R(\overrightarrow{x})). \]
\end{esempio}
%

% Alessandro Onnivello
\section{Dalle funzioni primitive ricorsive alle funzioni ricorsive}

Nel paragrafo precedente abbiamo definito l'insieme delle funzioni
primitive ricorsive; possiamo dire che queste siano sufficienti per
rappresentare tutte le funzioni calcolabili da una macchina di Turing?
La risposta è negativa, come andremo ora a dimostrare.

\begin{prop}\label{PRsonoTotali}
Le funzioni primitive ricorsive sono totali.
\end{prop}
\begin{proof}
Si dimostra per induzione sulla struttura delle funzioni primitive
ricorsive.  Poichè le funzioni di base sono funzioni totali dobbiamo
verificare che la composizione e la ricorsione primitiva preservano la
totalità delle funzioni composte.

Per la composizione dobbiamo verificare che la funzione composta
$f(g_1, \dots, g_k)$ è totale. Per ipotesi induttiva
(strutturale) $f,g_1,\dots,g_k$ sono totali. Per la totalità di
$g_1,\dots,g_k$ tutti gli argomenti di $f$ sono definiti e, poichè $f$
è totale, anche la composizione è definita.

Per la ricorsione primitiva dobbiamo dimostrare che
$h:\mathbb{N}^{k+1} \to \mathbb{N}$ è definita $\forall y \in
\mathbb{N}$ e $\forall \vec{x} \in \mathbb{N}^k$.

$$h(\vec{x},y)=\left\{
\begin{array}{ll} h(\vec{x}, 0) = f(\vec{x})\\
                  h(\vec{x}, s(y)) = g(\vec{x},y,h(\vec{x},y))
\end{array} \right.$$

Si dimostra per induzione su $y$.

$y = 0$: $h(\vec{x}, 0) = f(\vec{x})$\\ $f$ è totale per ipotesi
induttiva quindi $\forall \vec{x} \in \mathbb{N}^k (\vec{x}, 0) \in
dom(h)$ come atteso

$y + 1$: $h(\vec{x}, y + 1) = g(\vec{x}, y, h(\vec{x}, y))$\\
$h(\vec{x}, y)$ è totale per ipotesi induttiva su $y$ quindi
$h(\vec{x}, y)$ è definita. Poichè $g$ totale per ipotesi induttiva e
$h(\vec{x}, y)$ è definita allora $\forall \vec{x} \in \mathbb{N}^k \;
(\vec{x}, y + 1) \in dom(h)$.
\end{proof}

Ora, per quanto detto nella precedente proposizione, l'insieme delle funzioni
primitive ricorsive permette di rappresentare solo funzioni calcolabili totali
ma, come abbiamo visto nel primo capitolo, le macchine di Turing possono
calcolare anche funzioni parziali. Quindi possiamo affermare che le
funzioni primitive ricorsive non rappresentano tutte le funzioni Turing
calcolabili.

Ma limitandoci al caso delle funzioni totali, possiamo dire che queste
siano tutte primitive ricorsive? Anche in questo caso la risposta è
negativa come vedremo nel prossimo paragrafo.

\section{Metodo diagonale di Cantor}
Per poter dimostrare che l'insieme delle funzioni primitive ricorsive
non contiene tutte le funzioni totali calcolabili andremo ora a
introdurre il metodo diagonale (o diagonalizzazione) di Cantor.  Il
metodo di diagonalizzazione è una tecnica dimostrativa, ideata da
Georg Cantor per provare la non numerabilità dei numeri reali, che
risulta molto utile anche nell'ambito della logica matematica e della
teoria della computabilità come vedremo in seguito.

Il metodo diagonale di Cantor consiste nel costruire una funzione $\chi$
che differisce da un'insieme infinito di funzioni $\chi_0,\chi_1,\dots$
effettivamente enumerabile. Si costruisce quindi la seguente tabella
dove ogni colonna contiene una funzione unaria e le righe contengono
la sequenza dei naturali, ovvero tutti i possibili argomenti.
\begin{table}[!h]
\begin{center}
\begin{tabular}{|c|c|c|c|c}

\hline
 & $\chi_0$ & $\chi_1$ & $\chi_2$ & $\ldots$\\
\hline
0 & $\chi_0(0)$ & $\chi_1(0)$  & $\chi_2(0)$  & $\ldots$\\
\hline
1 & $\chi_0(1)$ & $\chi_1(1)$  & $\chi_2(1)$  & $\ldots$\\
\hline
2 &  $\chi_0(2)$ & $\chi_1(2)$  & $\chi_2(2)$  & $\ldots$\\
\hline
$\vdots$ & $\vdots$ &       $\vdots$  & $\vdots$  & $\ddots$\\

\end{tabular}
\end{center}
\caption{Metodo diagonale di Cantor}
\end{table}

A questo punto possiamo costruire una funzione $\chi$ in modo tale che
differisca da ogni funzione enumerata nella tabella; vogliamo quindi
costruire una funzione tale che $\forall i \; \chi(i) \neq
\chi_{i}(i)$, ovvero che differisce da ogni altra funzione elencata
nella tabella almeno sulla diagonale. Questa nuova funzione, creata
tramite una procedura effettiva, non può appartenere all'insieme di
partenza, poichè altrimenti differirebbe da sè stessa sulla diagonale.

\begin{prop}\label{TotCalcNonNum}
Data una qualunque lista \emph{effettiva} di tutte le funzioni totali
calcolabili, unarie per semplicit\`a, $f_{0},\; f_{1},\; f_{2},
\cdots$ esiste sempre una funzione $g$ totale calcolabile che non
compare nella lista.
\end{prop}
\begin{proof}
Sia $f_{0},\; f_{1},\; f_{2}, \cdots$ una lista effettiva di funzioni
totali calcolabili, allora costruiamo la funzione $g$ nel seguente
modo:

\begin{center}
$g: \mathbb{N} \to \mathbb{N}$\\
$g(x) = f_{x}(x) + 1$
\end{center}
\begin{table}[!h]
\begin{center}
\begin{tabular}{|c|c|c|c|c}

\hline
 & $f_0$ & $f_1$ & $f_2$ & $\ldots$\\
\hline
0 & $f_0(0) \mathbf{+1}$ & $f_1(0)$  & $f_2(0)$  & $\ldots$\\
\hline
1 & $f_0(1)$ & $f_1(1) \mathbf{+1}$  & $f_2(1)$  & $\ldots$\\
\hline
2 &  $f_0(2)$ & $f_1(2)$  & $f_2(2) \mathbf{+1}$  & $\ldots$\\
\hline
$\vdots$ & $\vdots$ &       $\vdots$  & $\vdots$  & $\ddots$\\
\end{tabular}
\end{center}
\caption{Funzione di diagonalizzazione $\mathbf{g}$}
\label{diagG}
\end{table}

$g$ è sicuramente totale calcolabile poichè, essendo la lista di
funzioni effettiva è quindi possibile, dato un qualsiasi $n \in
\mathbb{N}$, calcolare l'ennesima funzione, valutarla in $n$ ed
aggiungerci 1. È chiaro che $g$ non può appartenere alla lista, poichè
presa una qualsiasi colonna $n$ della tabella~\ref{diagG} che
rappresenta l'immagine dell'ennesima funzione, alla riga ennesima
$g(n) \neq f_{n}(n)$ poichè per definizione $g(n)=f_{n}(n)+1$. Perciò
non esiste alcun $n$ tale che $f_{n}(x)=g(x)$ per ogni $x \in
\mathbb{N}$ e quindi $g$ non è contenuta nella nostra lista.
\end{proof}

Fatto questo ragionamento, ne consegue che non è possibile enumerare
in modo effettivo tutte le funzioni totali calcolabili.

Possiamo usare ora la proposizone~\ref{TotCalcNonNum} per dimostrare il seguente

\begin{thm}\label{diagRic} Esiste una funzione totale calcolabile che non
è primitiva ricorsiva.
\end{thm}

\begin{proof}
Dobbiamo innanzitutto costruire una lista \emph{effettiva} di tutte le
funzioni primitive ricorsive (per semplicit\`a, supponiamole ad un
argomento).

Cerchiamo di scrivere informalmente un algoritmo che ci permetta di
listare tutte queste funzioni (in seguito vedremo come si pu\`o fare
in modo rigoroso).  Una tale enumerazione si pu\`o ottenere nello
stesso modo in cui si ottiene una lista di teoremi a partire dagli
assiomi di una teoria. Si prende prima una funzione base, poi si
``contano'' tutte le funzioni ottenute da questa mediante una sola
applicazione di composizione e/o ricorsione. Poi si prende la seconda
funzione e tutte le funzioni derivate mediante una applicazione delle
due regole da quest'ultima e/o dalle funzioni gi\`a ottenute al passo
precedente, e cos\`i via. In questa maniera non si tralascia alcuna
funzione e ad ogni passo la lista \`e finita. Abbiamo cos\`i ottenuto
una enumerazione effettiva per tutte le funzioni dell'insieme
$\mathcal{PR}$.\\ Ma per quanto detto nella
proposizone~\ref{TotCalcNonNum} sappiamo che le funzioni totali non
sono enumerabili effettivamente quindi questo implica che esiste una
funzione totale calcolabile che non appartiene l'enumerazione che
abbiamo appena definito e che quindi non appartiene all'insieme
$\mathcal{PR}$.
\end{proof}

A questo punto ci chiediamo: cosa ci manca per avere tutte le funzioni
calcolabili?
Ripensando a quanto visto fino ad ora, il problema pu\`o stare o nel pretendere
di avere una lista effettiva delle funzioni calcolabili (cosa che per\`o \`e
ragionevole a farsi: lo abbiamo visto poco fa), o nell'imporre la propriet\`a di
totalit\`a alle funzioni. Dunque vediamo se lasciando cadere questa assunzione
riusciamo a classificare tutte le funzioni calcolabili.


\section{Le funzioni ricorsive}
Avendo osservato che le funzioni primitive ricorsive non
esauriscono tutte le funzioni calcolabili, il passo successivo \`e  quello di
estenderle ulteriormente. In particolare ci sar\`a bisogno di trovare
anche funzioni parziali nella nostra definizione di ``ricorsivit\`a''. Perci\'o
introduciamo
la seguente funzione: \\

f. \textbf{minimizzazione}: sia $f: \mathbb{N}^{d+1} \to \mathbb{N}$ (anche
parziale)\\
definiamo la funzione di minimizzazione $h: \mathbb{N}^{d} \to \mathbb{N}$ come
$$ h(\vec{x}):= \mu_{y}(f(\vec{x},y)) $$
dove

\[\mu_{y}(f(\vec{x},y)) = 
\begin{cases}
il \; minimo \; y \; tale \; che: \\
\qquad (i) \; f(\vec{x},z)\downarrow \; \forall z \leq y \; e \\
\qquad (ii) \; f(\vec{x},y)=0 & \text{se y esiste,} \\
non \; definita \; & \text{se $\exists z < y \; f(\vec{x},z) \uparrow$}\\
 & \text{o se $f(\vec{x},y)\neq 0 \; \forall y \in \mathbb{N} $}
\end{cases} \]

con $\mu$ che prende il nome di operatore di minimizzazione.
\begin{thm} Le funzioni ricorsive sono b-programma-calcolabili.
\end{thm}
\begin{proof} Poich\`e abbiamo gi\`a dimostrato che le tre funzioni di base
(funzione zero, successore e proiezioni), la composizione generalizzata e la
ricorsione primitiva sono calcolabili da un b-programma ci resta solo da far
vedere che questo vale anche per la minimizzazione. Infatti se
$f:\mathbb{N}^{d+1} \to \mathbb{N}$ \`e computabile con un b-programma $\alpha$
allora possiamo eseguire la seguente assegnazione:
$$x_i \leftarrow f(\vec{x_{j}}, x_k)$$
(dove con $\vec{x_{j}}$ vogliamo rappresentare in modo compatto una lista di d
variabili di input)che significa "`dai come input $\vec{x_{j}}$ e $x_k$ al
b-programma $\alpha$ che calcola $f(\vec{x_{j}}, x_k)$ e dai output risultante
come valore a $x_i$"'. Dunque il b-programma che calcola la funzione di
minimizzazione su $\vec{x}$ \`e il seguente:\\
   \begin{mylisting}
       $x_0 \leftarrow 0$ \\
       $loop$: $\vec{x_{1}} \leftarrow \vec{x}$\\
       $x_{d+2} \leftarrow f(\vec{x_{1}}, x_0)$\\
       if $x_{d+2} = 0$ then goto $stop$\\
       $x_0 \leftarrow x_0 + 1$\\
       goto $loop$
  \end{mylisting}
\end{proof}

Una volta dimostrato che la minimizzazione è calcolabile dai
b-programmi possiamo dare la seguente
\begin{defi} Una funzione $f:\mathbb{N}^{d} \to \mathbb{N}$ (totale o
parziale) si dice \emph{ricorsiva} se si ottiene dalle funzioni
iniziali (a.--c.) applicando la composizione, la ricorsione e la
minimizzazione (d.--f.).
\end{defi}

Una cosa importante da notare \`e che l'utilizzo dell'operatore $\mu$ consente
di ottenere funzioni parziali anche a partire funzioni totali, come vedremo nei
seguenti esempi.
\begin{esempio} data $f:\mathbb{N} \to \mathbb{N}$ definita nel seguente modo:
$$f(x)= \left\{ \begin{array}{ll}
il \; min \; y \; t. \, c. \; x+y=0 & se \; \exists \; y\\
non \; definita & se \; x+y \neq 0 \; \forall y \in \mathbb{N}\\
\end{array} \right.$$
utilizzando la minimizzazione pu\`o essere scritta nel seguente modo:
$$f(x)= \mu_{y}(x+y)$$

Si noti che, essendo $x \in \mathbb{N}$, se $x \neq 0 \; f$ non \`e definita
anche se la funzione somma su cui viene applicato l'operatore di minimizzazione
\`e totale.
\end{esempio}

\begin{esempio} data $f:\mathbb{N}^{2} \to \mathbb{N}$ definita nel seguente
modo:
$$f(x,y)= \left\{ \begin{array}{ll}
x/y & se \; y \vert x\\
non \; definita & se \; y \nmid x\\
\end{array} \right.$$
pu\`o essere scritta nel seguente modo:
$$f(x,y) = \mu_{z}(\vert (z*y) - x \vert) $$
anche in questo caso la funzione $g(x,y,z)=\vert (z*y) - x \vert$ \`e totale, ma
combinata con l'operatore di minimizzazione consente di ottenere la funzione
parziale $f$.
\end{esempio}

\section{Relazioni ricorsive}
\begin{defi} $R \subseteq \mathbb{N}^{n}$ è una \emph{relazione
ricorsiva} se esiste una funzione ricorsiva $\chi_R$ che assume solo valori 0 e
1 e che soddisfa
$$\chi_R(x_1, \ldots, x_n):= \left \{ \begin{array}{ll}
                                      1 & (x_{1}, x_{2}, \cdots, x_{n}) \in R\\
                                      0 & (x_{1}, x_{2}, \cdots, x_{n}) \not \in
 R\\
                                      \end{array} \right. $$
\end{defi}
\begin{prop} Se $R, S \subseteq \mathbb{N}^{n}$ sono relazioni
ricorsive allora anche $R\land S$, $R \vee S$, $\neg R$ sono relazioni
ricorsive. Inoltre, se $w \in \mathbb{N}$, anche $\forall y \leq
w. R(x_1, \ldots, x_{n-1}, y)$ e $\exists y \leq w. R(x_1, \ldots,
x_{n-1}, y)$ sono relazioni ricorsive.
\end{prop}
\begin{proof} Si pone
\begin{itemize}
\item $\chi_{R\land S} = \chi_R \chi_S$;
\item $\chi_{R\vee S} = \chi_R + \chi_S - \chi_R  \chi_S$;
\item $\chi_{\neg R} = 1 - \chi_R$;
\item $\chi_{\forall y
\leq w. R(x_1, \ldots, x_{n-1}, y)} = \prod_{i=0}^{w} \chi_R(x_1, \ldots,
x_{n-1},i)$;
\item $\chi_{\exists y
\leq w. R(x_1, \ldots, x_{n-1}, y)} = sgn(\sum_{i=0}^{w} \chi_R(x_1, \ldots,
x_{n-1},i))$
\end{itemize}
\end{proof}

Grazie alla definizione data sopra, ci \`e possibile giustificare la
\emph{definizione per casi} delle funzioni ricorsive.

Supponiamo di avere una funzione $f: \mathbb{N}^{n} \to n$ t. c.
$$f(\vec{x}):= \left \{ \begin{array}{ll}
                    g_1(\vec{x}) & $se $ \vec{x} \in R_{1}\\
                    \vdots \\
                   g_k(\vec{x}) & $se $ \vec{x} \in R_{k}\\
                    \end{array} \right.$$
con $g_{1}, g_{2}, \cdots, g_{k}:\mathbb{N}^{n} \to \mathbb{N}$ funzioni
ricorsive e dove $R_{1}, R_{2}, \cdots, R_{k} \subseteq \mathbb{N}^{n}$ sono
relazioni ricorsive mutualmente esclusive ed esaustive, ossia abbiamo che:
\begin{itemize}
\item $\sum_{i=1}^{k} \chi_{R_{i}}(\vec{x})=1$ e che
\item se $R_{i}(\vec{x})$ vale allora $\forall j \neq i \; \chi_{R_{i}}(\vec{x})
\cdot \chi_{R_{j}}(\vec{x})=0$.
\end{itemize} 
Possiamo quindi prendere le funzioni caratteristiche $\chi_{R_{1}},
\chi_{R_{2}}, \cdots, \chi_{R_{k}}$ e definire la funzione $f$ come:
$$f(\vec{x})= \sum_{i=1}^{k} g_i(\vec{x})\chi_{R_{i}}(\vec{x})$$ e
quindi essendo $f$ ottenuta per composizione di funzioni ricorsive \`e
anch'essa ricorsiva.  Quindi se vogliamo descrivere una funzione che
assume valori diversi in casi diversi lo possiamo fare mantenendoci
all'interno delle funzioni primitive ricorsive. Questo può permetterci
di definire funzioni come quella del prossimo esempio.

\begin{esempio} Data la seguente funzione:
\[ f: \mathbb{N}^{2} \to \mathbb{N} \]
\[ f(x,y)= \begin{cases}
x-y	& \text{se $x \geq y$}\\
x+y & \text{se $x<y$}
\end{cases}\]
la sua definizione per casi \`e la seguente:\\
$f(x,y) = \sum_{i=1}^{2} g_{i} \cdot \chi_{R_{\geq}}(x,y) = (x-y)\cdot
\chi_{R_{\geq}}(x,y) + (x+y)\cdot \neg \chi_{R_{\geq}}(x,y) $
Si lascia come esercizio al lettore il trovare $\chi_{R_{\geq}}$.
\end{esempio}

% Alessandro Bruni

\section{Equivalenze}

Per riassumere il percorso seguito finora presentiamo il seguente schema.
Ad ogni passaggio abbiamo introdotto un linguaggio pi\`u
raffinato senza per\`o aggiungere nuove funzioni:
 ogni volta abbiamo aggiunto qualcosa che fosse definibile in
termini del precedente e quindi in particolare di macchine di Turing.
\begin{align*}
{\rm Macchine\ }&{\rm di\ Turing\ }\\
\bigcup &|\\
{\rm Macchine\ }&{\rm a\ registri\ }\\
\bigcup &|\\
{\rm Progra}&{\rm mmi}\\
\bigcup &|\\
{\rm Funzioni\ }&{\rm ricorsive\ }\\
\bigcup &| \; {\rm?}\\
{\rm Macchine\ }&{\rm di\ Turing\ }\\
\end{align*}

È valida valida l'ultima inclusione? in caso affermativo tutti i
concetti di funzioni calcolabili descritti fino ad ora sono tra loro
equivalenti. Il seguente teorema dimostra che quest'inclusione è
effettivamente valida.

\begin{thm}[Le funzioni Turing-calcolabili sono ricorsive]
Ovvero, per ogni MdT possiamo costruire una funzione ricorsiva che la calcola.
\end{thm}

\begin{proof}
Dobbiamo innanzitutto trovare un modo per rappresentare il nastro (ovvero la
memoria) della MdT. Per semplicità di esposizione poniamoci nel caso $\sigma =
\{ B, 1 \}$, poichè ogni altro alfabeto finito può avere una rappresentazione
simile nei naturali, scegliendo una rappresentazione in base $|\sigma|$
dell'input.

Una MdT computa una funzione $f: \mathbb{N}^k \rightarrow \mathbb{N}$,
possibilmente parziale, quindi lo stato del nastro all'inizio della
computazione è una sequenza di caratteri che contiene le variabili in
input:
$$\dots BB\overline{x_1+1}B\overline{x_2+1}B...B\overline{x_k+1}BB\dots $$
mentre alla fine del calcolo la macchina dovrebbe lasciare nel nastro
il risultato della funzione che calcola:
$$\dots BB\overline{f(x_1,\dots,x_k)+1}BB\dots $$

Diamo ora le seguenti definizioni, per meglio comprendere la nostra codifica
del nastro in $\mathbb{N}$.

\begin{defi}[Numerale sinistro]
Si definisce numerale sinistro la sequenza di caratteri, letti da sinistra a
destra a partire dal primo 1, che si trovano strettamente a sinistra della
testina della MdT, dove 1 rappresenta la cifra 1 e $B$ rappresenta la cifra 0.
\end{defi}
\begin{defi}[Numero sinistro]
Si dice numero sinistro l'interpretazione nei naturali del numerale sinistro,
ovvero quel numero $n \in \mathbb{N}$ la cui rappresentazione in base 2 è
esattamente il numerale sinistro.
\end{defi}
\begin{defi}[Numerale destro]
È la sequenza di caratteri a destra della testina (compreso quello sopra la
testina stessa) lette da destra verso sinistra, a partire dal primo 1 che
compare sul nastro.
\end{defi}
\begin{defi}[Numero destro]
È l'interpretazione nei naturali del numerale destro.
\end{defi}

È facile comprendere da queste definizioni che il nastro e la testina della
macchina di Turing possono essere rappresentati da una coppia di interi, ovvero
il numero sinistro e il numero destro. Inoltre il carattere esattamente sotto
la testina è 1 se il numero destro è dispari, 0 se pari.

\begin{esempio}
Per questa macchina di Turing
\begin{align*}
\dots BB11B&111B1111BB \dots\\
&\,\uparrow
\end{align*}
il numerale sinistro è 1101, il numero sinistro è 13; il numerale destro è
1111011, il numero destro è 123.
\end{esempio}

Ora dobbiamo poter simulare su questa coppia di numeri le operazioni che la
macchina di Turing svolge sul nastro. Queste sono:
\begin{enumerate}
 \item scrivere un 1 nella casella sulla quale sta la testina;
 \item scrivere uno 0 sulla casella;
 \item spostare la testina a destra (R);
 \item spostare la testina a sinistra (L);
\end{enumerate}

Per le prime due è facile trovare una funzione ricorsiva che modifica il
numero destro in modo da rappresentare la scrittura di un 1 o di uno 0: nel
primo caso basta sommare 1 se il numero è pari (ovvero nella posizione
sottostante alla testina della MdT simulata vi è uno 0), nel secondo caso è
sufficente sottrarre 1 se il numero è dispari.

Definiamo quindi le funzioni che svolgono queste due operazioni:
$$w_1(x) = \left\{
\begin{array}{ll}
x+1 & \text{se } 2 \mid x\\
x & \text{se } 2 \nmid x
\end{array}
\right.$$
che simula l'operazione di scrivere un 1, e
$$w_B(x) = \left\{
\begin{array}{ll}
x & \text{se } 2 \mid x\\
x-1 & \text{se } 2 \nmid x
\end{array}
\right.$$
che simula l'operazione di scrivere uno 0.

Per simulare lo spostamento della testina sul nastro bisogna osservare come
cambiano i numerali quando la testina si muove a destra o a sinistra. Siano $l$
e $r$ rispettivamente il numero sinistro e il numero destro prima dello
spostamento della testina, $l'$ ed $r'$ il numero sinistro ed il numero destro
dopo lo spostamento della testina.
\begin{enumerate}
 \item Se la testina si muove verso sinistra ed $l$ è pari allora vuol
   dire che a sinistra della testina c'è uno 0, che passa da cifra
   meno significativa del numerale sinistro ad essere la cifra meno
   significativa del numerale destro.  Quindi $l' = l/2$ ed $r' = r
   \cdot 2$.
 \item Se la testina si muove verso sinistra ed $l$ è pari allora vuol
   dire che a sinistra della testina c'è un 1, che passa dal numerale
   sinistro al numerale destro; quindi $l' = (l-1)/2$ ed $r' = r \cdot
   2 + 1$.
 \item Se la testina si muove verso destra e la cifra meno
   significativa del numerale destro è un 1, questa passa al numerale
   sinistro per cui: $l' = l \cdot 2 + 1$, $r' = (r-1)/2$.
 \item Se la testina si muove verso destra e la cifra meno
   significativa del numerale destro è uno 0, $l' = l \cdot 2$ e $r' =
   r/2$.
\end{enumerate}

Vediamo ora come codificare le quintuple $\langle q_i, S_i, S_j,
\{L,R\}, q_j \rangle$ che descrivono una macchina di Turing.

Queste definiscono una funzione di transizione $\tau : \mathbb{N}^2
\rightarrow \mathbb{N}^3$ e, poichè le nostre funzioni ricorsive sono
tutte della forma $f:\mathbb{N}^k \rightarrow \mathbb{N}$, dobbiamo
trovare una funzione di codifica delle ennuple $\nu: \mathbb{N}^n
\rightarrow \mathbb{N}$ ed una classe di funzioni di proiezione
$\nu_i: \mathbb{N} \rightarrow \mathbb{N}$ che estrapolano la
proiezione dell'i-esima componente dall'ennupla codificata nei
naturali.

Delle funzioni adatte a questo scopo sono le seguenti:
$$\nu(\vec{x}) = \prod_{i=1}^n p_i^{x_i}$$ per la codifica
e $$\nu_i(w) = \max_x.p_i^x \mid w$$ per la decodifica dell'i-esima
componente, dove $p_i$ indica l'i-esimo numero primo. Queste funzioni
sfruttano l'unicità della fattorizzazione in numeri primi dei
naturali.

La funzione di codifica è chiaramente primitiva ricorsiva, in quanto
composizione di funzioni primitive ricorsive, ovvero il prodotto e
l'elevamento a potenza.

Per verificare che anche la funzione di proiezione è primitiva
ricorsiva dobbiamo introdurre gli operatori di minimizzazione e
massimizzazione limitata, rispettivamente $\mu_{w<n}[f](\vec{x})$ e
$\max_{w<n}[f](\vec{x})$, che calcolano il minimo e il massimo $w \in
[0,n]$ tale per cui $f(\vec{x}, w) = 0$.

$$\mu_{w<n}[f](\vec{x}) = \sum_{i=0}^n sgn\left(\prod_{j=0}^i
f(\vec{x},w)\right)$$

Sia $h(\vec{x},y) = f(\vec{x},n-y)$, definiamo la funzione di
massimizzazione in questo modo:

$$\max_{w<n}[f](\vec{x}) = n-\mu_{w<n}[h](\vec{x})$$

Chiaramente sia la minimizzazione che la massimizzazione limitate sono
funzioni primitive ricorsive, in quanto definite in termini di altre
funzioni primitive ricorsive.

Ora definiamo la funzione caratteristica della divisione:

\begin{align*}
div(x,y) =& \left\{
\begin{array}{ll}
1 & \text{se } x \mid y\\
0 & \text{se } x \nmid y
\end{array}
\right. \\
=& \, sgn\left( \left| \mu_{w<y+1}.\left|x \cdot w - y \right| - (y+1)\right|
\right)
\end{align*}

Infine possiamo definire la funzione di proiezione nel seguente modo:
$$\nu_i(w) = \max_{x<w}.\left| div(p_i^x, w) - 1\right|$$ e quindi
abbiamo dimostrato che anche la massimizzazione è primitiva rcorsiva.

Con gli strumenti che ci siamo appena procurati possiamo ora costruire
la codifica della funzione di transizione. Intanto ci serve una mappa
dei simboli che usiamo per descrivere la macchina di Turing nei
naturali:
\begin{align*}
q_i &\rightsquigarrow i+1\\
B &\rightsquigarrow 0\\
1 &\rightsquigarrow 1\\
L &\rightsquigarrow 1\\
R &\rightsquigarrow 2\\
\end{align*}

La funzione di transizione, dato un insieme $S$ di regole per la
macchina di Turing, è la seguente:
$$\tau(x,y) = \left\{
\begin{array}{ll}
\nu(u,v,w) & \text{se $\langle q_i, S_i, S_j, D, q_j \rangle \in
  S$}\\ & \text{e $q_i \rightsquigarrow x$, $S_i \rightsquigarrow y$,
  $S_j \rightsquigarrow u$, $D \rightsquigarrow v$, $q_j
  \rightsquigarrow w$}\\ \nu(0,0,0) & \text{se non si applica nessuna
  regola}
\end{array}
\right.$$ è una funzione definita per casi su un insieme finito di
regole $S$, per cui, come dimostrato nei paragrafi precedenti, è
primitiva ricorsiva.

Codifichiamo ora la funzione che esegue sul nastro la tripla ottenuta
dalla funzione di transizione. Siano $left(l,r)$ e $right(l,r)$ le
funzioni che simulano lo spostamento della testina rispettivamente a
sinistra ed a destra secondo le regole date in precedenza. Un passo
della MdT è codificato dalla seguente funzione:

$$step(l,r,x) = \left\{
\begin{array}{ll}
left(l, w_0(r)) \cdot p_3^{\nu_3(x)} & \text{se }\nu_1(x) = 0, \nu_2(x) = 1\\
left(l, w_1(r)) \cdot p_3^{\nu_3(x)} & \text{se }\nu_1(x) = 1, \nu_2(x) = 1\\
right(l, w_0(r)) \cdot p_3^{\nu_3(x)} & \text{se }\nu_1(x) = 0, \nu_2(x) = 2\\
right(l, w_1(r)) \cdot p_3^{\nu_3(x)} & \text{se }\nu_1(x) = 1, \nu_2(x) = 2\\
\end{array}
\right.$$

Questa funzione, definita per ricorsione primitiva, ci da lo stato
della macchina dopo $t$ passi:
\begin{align*}
f(l,r,0) &= \nu(l,r,1)\\
f(l,r,t+1) &= step(\nu_1(n), \nu_2(n), \tau(\nu_3(n), \nu_2(n) \mod 2) )
\end{align*}
con $n = f(l,r,t)$.

Vediamo come codificare una k-tupla di una funzione ricorsiva nel valore $r$.
Intanto codifichiamo un singolo elemento:
\begin{align*}
g(r,0) &= 2\cdot r + 1\\ 
g(r,x+1) &= 2\cdot f(r, x) + 1\\
\end{align*}
usando questa funzione codifichiamo la tupla:
$$cod(x_1, \dots, x_n) = g(\dots 2\cdot g(0, x_n), x_1)$$
e decodifichiamo il risultato:
$$dec(r) = \mu_x.r+1\dot{-}2^x$$

Ora non ci resta che costruire la funzione che esegue la macchina di
Turing sull'input e che ritorna la codifica del nastro alla
terminazione: $$MdT(\vec{x}) = dec(\nu_2(f(0,cod(\vec{x}),\mu_t .
|\nu_3(f(0,cod(\vec{x}),t)) = 0|)))$$

In questo modo abbiamo definito una funzione ricorsiva che svolge
l'intera computazione di una macchina di Turing, se questa termina, ed
è indefinita altrimenti. In effetti si può dire qualcosa in più: fino
alla fine della nostra costruzione abbiamo usato solo funzioni
primitive ricorsive, quindi totali per la
Proposizione~\ref{PRsonoTotali}. Ovvero è sempre possibile sapere qual
è lo stato della computazione della macchina di Turing (rappresentato
dai numerali sinistro e destro) ad un dato tempo $t$, la vera
incognita sta nella terminazione della macchina, com'era giusto
aspettarsi.

È interessante inoltre notare che la costruzione di questa funzione è
quasi del tutto indipendente dalla macchina di Turing che andiamo a
simulare con la nostra funzione ricorsiva, se non per la funzione di
transizione $\tau$ che non è altro che la rappresentazione
dell'insieme di regole date in pasto alla macchina. Potremmo dunque
benissimo pensare sostituire $\tau$ con un'altra funzione, più
sofisticata, che prende in input le quintuple codificate, lo stato
iniziale e il carattere letto e ritorna la tripla che codifica il
carattere da scrivere, la direzione in cui spostare la testina e lo
stato finale; questa funzione è in grado di prendere una qualsiasi
macchina di Turing codificata ed eseguirla su un qualsiasi
input. Inserendo questa particolare funzione di transizione e
sostituendola nel nostra prova otteniamo la macchina di Turing
universale, in grado cioè di eseguire una qualunque macchina di
Turing.

Abbiamo quindi dimostrato che per ogni macchina di Turing esiste una
funzione ricorsiva che la computa ed abbiamo visto come costruirla.
\end{proof}


\subsection{Tesi di Church-Turing}
Poichè tutti questi (ed altri) tentativi di definire tutto ciò che è
effettivamente calcolabile portano alla stessa classe di funzioni, si
può pensare che la nostra nozione intuitiva di calcolabilità coincida
esattamente con ognuna di queste definizioni.


% Giuseppe Ferri

\section{Esempio di funzione non ricorsiva}
La definizione di funzione non ricorsiva che si intende dare è basata sul processo di definizione delle funzioni ricorsive. In particolare, si definisce un \emph{sistema di nomi di arietà} per le funzioni ricorsive.

\begin{itemize}
 \item La funzione unaria \emph{zero} che ad ogni input associa il valore 0 viene denotata con il nome \emph{$Z^1$}, dove l'indice 1 ricorda che si tratta di una funzione ad un argomento.
\item La funzione unaria \emph{succ} che ad ogni input \emph{x} associa il valore \emph{x}+1 viene denotata con il nome \emph{$S^1$}, dove l'indice 1 ricorda che si tratta di una funzione ad un argomento.
\item La funzione \emph{n}-aria \emph{$proj^n_i$}, con \emph{$1 \leq i\leq n$}, che ad ogni ennupla (\emph{$x_1,...,x_n$}) associa il valore \emph{$x_i$} viene denotata con il nome \emph{$P^n_i$}, dove l'indice \emph{n} ricorda che si tratta di una funzione a \emph{n} argomenti.
\item Se \emph{$F^m$},  \emph{$G^n_1$},...,\emph{$G^n_m$} sono i nomi delle \emph{m} + 1 funzioni \emph{f}, \emph{$g_1$},...,\emph{$g_m$} rispettivamente la prima di arietà \emph{m} e, tutte le altre, di arietà \emph{n}, allora \emph{$C^n$[$F^m$,$G^n_1$,..., $G^n_m$]} è il nome della funzione \emph{h} di arietà \emph{n} ottenuta componendo \emph{f} con le funzioni \emph{$g_1,...,g_m$}, ossia \emph{$h(\vec{x}) = f(g_1(\vec{x}),...,g_m(\vec{x}))$}.
\item Se \emph{$K^n$} e \emph{$G^{n+2}$} sono i nomi delle funzioni \emph{k} e \emph{g} di arietà rispettivamente \emph{n} e \emph{n+2} allora \emph{$R^{n+1}$[$K^n$, $G^{n+2}$]} è il nome della funzione \emph{f} di arietà \emph{n+1} ottenuta per ricorsione primitiva da \emph{k} e \emph{g}, ossia \emph{$f(0, \vec{y}) =k(\vec{y})$} e \emph{$f(x+1, \vec{y}) =g(x, \vec{y}, f(x, \vec{y}))$}.
\item Se \emph{$G^{n+1}$} è il nome della funzione \emph{g} di arietà \emph{n+1} allora \emph{$M^n$[$G^{n+1}$]} è il nome della funzione \emph{f} di arietà \emph{n} ottenuta da \emph{g} per minimizzazione, ossia \emph{$f(\vec{x}) := \mu y.g(\vec{x}, y) = 0$}.
\end{itemize}


Possiamo quindi dare la seguente definizione.

\begin{defi}[Funzione ricorsiva]
Una funzione è \emph{ricorsiva} se e solo se ha un nome.
\end{defi}
 
In effetti una funzione ricorsiva può avere molti nomi, tuttavia un nome \emph{F} definisce esattamente una funzione ricorsiva che indicheremo con \emph{$f_F$} quando vorremmo mettere l'accento sul fatto che la definizione della funzione dipende dal suo nome.
\begin{esempio}
[somma]
La funzione somma si può definire induttivamente come:
$$\left\{
\begin{array}{ll} y + 0 = y\\
                 y + succ(x)= succ(x + y)
\end{array} \right.$$
Si pone il segno di addizione + in forma più esplicita, ottenendo:
$$\left\{
\begin{array}{ll} somma(0, y) = y\\
                 somma(succ(x), y) = succ(somma(x, y))
\end{array} \right.$$
Ed infine mettiamo queste equazioni nel formato ufficiale per la ricorsione:

$$\left\{
\begin{array}{ll} somma(0, y) = P^1_1(y)\\
                 somma(succ(x), y) = C^3[S^1, P^3_3](x, y, somma(x, y))
\end{array} \right.$$

ed in breve si ottiene il nome da dare alla somma:
$$Sum^2 := R^2[P^1_1, C^3[S^1, P^3_3]]$$	
\end{esempio}

\begin{esempio}
[prodotto]

$$\left\{
\begin{array}{ll} prod(x, 0) = zero(x) = Z^1(x)\\
                 prod(x, succ(y)) = somma(x, prod(x, y)) = C^3[Sum^2, P^3_1, P^3_3]](x, y, prod(x, y))
\end{array} \right.$$
Quindi il nome del prodotto è: 
$$Prod^2 := R^2[Z^1, C^3[Sum^2, P^3_1, P^3_3]]$$	
\end{esempio}




\begin{defi}[Grado di un nome]
Il \emph{grado del nome F di una funzione ricorsiva}, indicato con \emph{$\delta$(F)}, è il numero di simboli che appaiono nella scrittura di F, cioè il numero di Z, S, $P^n_i$, C[-,-,...,-], R[-,-] e M[-].
\end{defi}

Notiamo che ci sono una infinità numerabile di funzioni ricorsive di qualsiasi grado visto che possiamo costruire infiniti nomi utilizzando questi segni. Tuttavia, se poniamo un vincolo al numero di segni utilizzabili vale il seguente teorema. 

\begin{thm}[Finitezza]
 Il numero di funzioni ricorsive di arietà 1 a cui si può dare un nome utilizzando al più n simboli è finito.
\end{thm}

\begin{proof}
Se per costruire il nome posso usare al massimo \emph{n} segni, allora posso al più utilizzare \emph{Z, S, C, R, M} e $P^k_i$ con \emph{$k \leq n$} e con questi posso solo scrivere nomi di lunghezza finita; perciò il numero di nomi diversi possibile è finito.
 \end{proof}

Vediamo ora come definire una funzione e dimostrare che non è ricorsiva.

\begin{defi}[Produttività di una funzione ricorsiva]
La \emph{produttività $p_F$} della funzione ricorsiva $f_F$ di nome F è il valore di $f_F$ su 0 se tale valore esiste ($f_F$ potrebbe essere una funzione parziale), 0 altrimenti.
\end{defi}

Possiamo allora definire la funzione di produttività \emph{p} nel modo seguente: $$p(n)=max_{\delta(F)\leq 2n + 1} p_F$$

Si nota che la funzione di produttività \emph{p} è ben definita visto che, in conseguenza del teorema di finitezza, per ogni numero naturale \emph{n}, c'è un numero finito di funzioni ricorsive il cui nome si scrive con al massimo \emph{2n} + 1 simboli e quindi è possibile calcolare il massimo tra questo numero finito di valori.\\
Per dimostrare che la funzione di produttività non è ricorsiva ne studiamo alcune proprietà molto elementari.

\begin{prop}Per ogni n, $p(n) \geq n$.
\end{prop}
\begin{proof} 
Consideriamo il nome da dare alla funzione unaria che ad ogni input associa il valore n:
$$N_n := C[S, C[S,...C[S, Z]...]]$$
dove ci sono \emph{n} coppie \emph{C} e \emph{S}. 
Osserviamo che $\delta(N_n) = 2n + 1$ e quindi con \emph{2n} + 1 segni possiamo definire una funzione ricorsiva in grado di produre almeno \emph{n} come output quando applicata a 0.
\end{proof}

\begin{prop}Per ogni n, $p(n + 1) > p(n)$.
\end{prop}
\begin{proof} 
Consideriamo una funzione ricorsiva \emph{f} il cui nome \emph{F} richiede al massimo 2\emph{n} + 1 simboli e che produca come output \emph{p(n)} quando applicata a 0. Allora la funzione di nome \emph{C[S, F]} richiede al massimo 2 + 2\emph{n} + 1 = 2(\emph{n} + 1) + 1 simboli e produce su 0 un output pari a \emph{$p(n) + 1 > p(n)$} e quindi \emph{$p(n + 1) \geq p(n) + 1 > p(n)$}. 
\end{proof}

La proposizione precedente mostra chiaramente che la funzione \emph{p} è strettamente monotona e quindi per ogni \emph{i} e \emph{j}, se \emph{$p(i) \leq p(j)$} allora \emph{$i \leq j$}.

\begin{prop}Per ogni n, $p(n + 5) \geq 2n$.
\end{prop}
\begin{proof} 
Vediamo come definire una funzione ricorsiva che raddoppi il suo input. Definiamo per ricorsione una funzione \emph{d} così definita:
$$\left\{
\begin{array}{ll} d(0) = 0\\
                d(x + 1) = succ(succ(d(x))
\end{array} \right.$$
 Allora è immediato verificare che un nome per questa funzione è 
$$D := R[M[Z], C[S, C[S, P^2_2]]]$$ 
che richiede 8 segni.
Se ora noi componiamo la funzione di nome \emph{$N_n$} che abbiamo definito in precedenza con la funzione di nome \emph{D} appena introdotta otteniamo il nome \emph{C[D, $N_n$]} che richiede $1 + 8 + 2n + 1 \leq 2(n + 5) + 1$ segni e definisce una funzione unaria che su input 0 produce output 2\emph{n}. 
\end{proof}

Siamo ora in grado di dimostrare che la funzione \emph{p} non può essere ricorsiva.


\begin{thm}La funzione di produttività non è ricorsiva.
\end{thm}
\begin{proof}
Supponiamo che \emph{p} sia una funzione ricorsiva. \\ Allora dovrebbe avere un nome \emph{P} e tale nome avrebbe un certo numero \emph{$k_p$} di simboli. Consideriamo ora il nome \emph{C[P, C[P, $N_n$]]}. Si tratta di un nome che richiede 1+ \emph{$k_p$} + 1 + \emph{$k_p$} + 2\emph{n} + 1 = 2(\emph{n} + 1 + \emph{$k_p$}) + 1 segni e che descrive una funzione ricorsiva il cui valore su 0 è uguale a \emph{p(p(n))}. Quindi \emph{$p(n + 1 + k_p) \geq p(p(n))$}. Ma allora in virtù della stretta monotonia della funzione \emph{p} otteniamo che, per ogni \emph{n}, \emph{$n + 1 + k_p \geq p(n)$}. \\Visto che tale disequazione vale per ogni \emph{n}, il risultato deve valere anche quando sostituiamo a \emph{n} il valore \emph{n + 5} ottenendo \emph{$n + 6 + k_p \geq p(n + 5)$}. Ma ora, in virtù della proposizione precedente, possiamo ricavare \emph{$n + 6 + k_p \geq p(n + 5) \geq 2n$} da cui si deduce che, per ogni \emph{n},  \emph{$k_p \geq n - 6$} che è assurdo visto che \emph{$k_p$} è il numero, fissato in partenza per ipotesi, dei simboli necessari per scrivere il nome della funzione di produttività. 
 \end{proof}