Funzione ricorsiva: differenze tra le versioni

 

== Definizione ==

 

 

L'operatore μ è così definito:

 

:<math>\begin{align}

\mu,y:(f(y, x_1, \ldots, x_n)=0)\ &\stackrel{\mathrm{def}}{=} \text{ il più piccolo } y \text{ tale che } f(y, x_1, \ldots, x_n)=0\ \ \text{ (se esiste)}

Le funzioni ricorsive primitive sono quindi un sottoinsieme delle funzioni ricorsive. Si noti che mentre le funzioni ricorsive primitive sono sempre totali (NB: non tutte le funzioni totali sono ricorsive primitive), le funzioni ricorsive possono essere parziali, ovvero possono non essere definite per alcuni valori di input: infatti, l'operatore minimizzazione non restituisce alcun valore nel caso in cui la funzione a cui è applicato non si annulla per nessun valore dell'argomento.

 

 

== Esempi di funzioni ricorsive ==

:<math>\varphi_i(y) = f(y) </math>

 

:<math>

g(x, y) =

\begin{cases}

\\ 0 & \mbox{altrimenti }

\end{cases}

\begin{cases}

1 & \mbox{se } g(x, x)=0 \mbox{, cio} \grave{e} \mbox{ se } \varphi_x(x) \mbox{ non } \grave{e} \mbox{ definita}

\end{cases}

</math>