**TC: Funciones Recursivas**
# La clase de las Funciones Recursivas
Comenzaremos presentando tres procedimientos de definición de funciones. Intuitivamente, resultará evidente que si las funciones que se toman de partida para cada procedimiento son computables entonces también lo es la nueva función obtenida (más adelante daremos una prueba de ello).
!!!def:Definición: Composición
Dadas $f:{\Bbb N}^k - \to {\Bbb N}$ y $g_1,...,g_k:{\Bbb N}^n - \to {\Bbb N}$ diremos que $h:{\Bbb N}^n- \to {\Bbb N}$ se obtiene por **composición** a partir de $f,g_1,...,g_k$, o que $h$ es la composición de $f$ y $g_1,...,g_k$, y lo notaremos por $h={\bf C}(f;g_1,...,g_k)$, si para todo $\vec{x}\in {\Bbb N}^n$
$$h(\vec{x})\simeq f(g_1(\vec{x}),...,g_k(\vec{x}))$$
!!!def:Definición: Recursión Primitiva
Si $g:{\Bbb N}^n- \to {\Bbb N}$ y $h:{\Bbb N}^{n+2} - \to {\Bbb N}$ diremos que $f:{\Bbb N}^{n+1} - \to {\Bbb N}$ se obtiene por **recursión primitiva** a partir de $g$ y $h$ si para todo $\vec{x}\in {\Bbb N}^n$
$$\begin{cases}
f(\vec{x},0) & \simeq & g(\vec{x})\\
f(\vec{x},y+1) & \simeq & h(\vec{x},y,f(\vec{x},y)),\quad \mbox{ para todo } y \in {\Bbb N}
\end{cases}$$
!!!note: Observaciones
Notemos que:
* Dadas $g$ y $h$ como en la definición de la recursión primitiva, existe una única función $f$ verificando las condiciones expuestas. La unicidad puede probarse por inducción, pues si $f_1,f_2$ son tales que: $$\begin{cases}
f_i(\vec{x},0) & \simeq & g(\vec{x}) \\
f_i(\vec{x},y+1) & \simeq & h(\vec{x},y,f_i(\vec{x},y))
\end{cases}$$ Entonces, $\forall y \in {\Bbb N}\ \forall \vec{x} \in {\Bbb N}^n\ (f_1(\vec{x},y)\simeq f_2(\vec{x},y))$ (por inducción en $y$).
* La nota anterior nos permite introducir la notación $f={\bf R}(g,h)$, que leemos como **$f$ es la función definida por recursión primitiva a partir de $g$ y $h$**.
* Si las funciones auxiliares usadas en la composición y recursión primitiva son totales, las obtenidas también lo son.
* Como caso especial en la definición por recursión primitiva admitimos que $n=0$. En dicho caso las ecuaciones que definen la función $f:{\Bbb N}\ - \to {\Bbb N}$ pasan a ser: $$\begin{cases}
f(0) & = & a \\
f(x+1) & = & h(x,f(x))
\end{cases}$$ Es decir, en vez de la función $g$ tenemos una constante $a\in {\Bbb N}$ y la función $h$ es de aridad 2. Por abuso de notación, diremos que $f$ ha sido definida por recursión primitiva a partir de $a$ y $h$, escribiendo $f={\bf R}(a,h)$.
!!!def:Definición: $\mu$--recursión
Dada $f:{\Bbb N}^{n+1}- \to {\Bbb N}$, la función definida a partir de $f$ por $\mu$-**recursión** es la función $f_\mu:{\Bbb N}^n- \to {\Bbb N}$ dada por:
$$f_\mu(\vec{x})=\begin{cases}
min\{y:\ f(\vec{x},y)=0 \wedge \forall\ z < y\ (f(\vec{x},z)\downarrow)\} &
\mbox{, si
existe}\\
\uparrow & \mbox{, en otro caso}
\end{cases}$$
Escribiremos $f_\mu(\vec{x})=(\mu y)(f(\vec{x},y)=0)$.
La condición $\forall\ z < y\ (f(\vec{x},z)\downarrow)$ es importante para poder calcular $g$ de manera efectiva. Recordemos que $\mu$ puede verse como una búsqueda, ya que buscamos un valor de $y$ tal que $f(\vec{x},y)=0$, y si existe $z < y$ tal que $f(\vec{x},z)\uparrow$, entonces la búsqueda no terminaría.
!!!def:Definición: Funciones Básicas
Llamaremos **funciones básicas** a las siguientes:
* **La función sucesor**: $$S:{\Bbb N} \to {\Bbb N},\ S(x)=x+1$$
* **La función idénticamente nula (ó cero)**: $${\cal O}:{\Bbb N} \to {\Bbb N},\ {\cal O}(x)=0$$
* **Las proyecciones**: Para cada $n\geq 1$, y cada $i\ (1\leq i \leq n)$, definimos $\Pi_i^n:{\Bbb N}^n\to {\Bbb N}$, como $$\Pi_i^n(x_1,...,x_n)=x_i$$
!!!def:Definición: Funciones Recursivas
La clase de las **Funciones Recursivas**, ${\cal P}$, es la menor clase de funciones tal que:
1. Contiene a las funciones básicas.
2. Es cerrada bajo composición, recursión primitiva y $\mu$--recursión, es decir:
* Si $f:{\Bbb N}^k - \to {\Bbb N},\ g_1,...,g_k:{\Bbb N}^n- \to {\Bbb N} \in {\cal P}$, entonces ${\bf C}(f;g_1,...,g_k) \in {\cal P}$.
* Si $g:{\Bbb N}^n- \to {\Bbb N},\ h:{\Bbb N}^{n+2} - \to {\Bbb N}\in {\cal P}$, entonces ${\bf R}(g,h) \in {\cal P}$.
* Si $f:{\Bbb N}^{k+1}- \to {\Bbb N}\in {\cal P}$, entonces $f_\mu\in {\cal P}$.
!!!note:Observaciones
Notemos que:
* Puesto que ${\cal P}$ es la menor clase de funciones que verifica (1) y (2), si deseamos probar una propiedad, $\Psi$, para todas las funciones recursivas podemos hacerlo por _inducción sobre funciones recursivas_. Para ello probaremos que:
* $\Psi$ es cierta para las funciones básicas.
* Si $f,g_1,...,g_k \in {\cal P}$ verificando $\Psi$, y que están en las condiciones en que se definió la composición, entonces ${\bf C}(f;g_1,...,g_k)$ también verifica $\Psi$.
* Si $g$ y $h\in {\cal P}$ verifican $\Psi$ y están en las condiciones de la definición por recursión primitiva, entonces $R(g,h)$ también verifica $\Psi$.
* Si $f$ es recursiva y verifica $\Psi$, entonces $f_\mu$ también.
* Es fácil, por tanto, probar un resultado de construcción de funciones recursivas como el siguiente: Dada una función, $f$, son equivalentes:
* $f \in {\cal P}$.
* Existen $f_1,...,f_n$ tales que $f_n=f$ y para cada $i\leq n$ se tiene una de las situaciones siguientes:
* $f_i$ es una función básica, o bien,
* Existen $j,k < i$ tales que $f_i={\bf R}(f_j,f_k)$, o bien,
* Existen $j_1,\dots,j_r, k < i$ tales que $f_i={\bf C}(f_k;f_{j_1},...,f_{j_r})$, o bien,
* Existe $k < i$ tal que $f_i=(f_k)_\mu$.
# Funciones Recursivas Totales y Primitivas Recursivas
!!!def: Definición: ${\cal R}$ y ${\cal PR}$
Existen dos clases de funciones recursivas que merecen se destacadas: las **Funciones Recursivas Totales** y las **Funciones Primitivas Recursivas**.
* La clase de las **Funciones Recursivas Totales**, que se denotará por ${\cal R}$.
* La clase de las **Funciones Primitivas Recursivas**, ${\cal PR}$, que es la menor clase de funciones tal que:
1. contiene las funciones básicas y
2. es cerrada bajo composición y recursión primitiva.
!!!note
Notemos que:
* Puesto que ${\cal PR}$ es la menor clase de funciones que verifica (1) y (2), si deseamos probar una propiedad para todas las funciones recursivas podemos hacerlo por _inducción sobre funciones primitivas recursivas_.
* Si $f\in {\cal PR}$, entonces $f$ es total (se prueba por inducción sobre funciones primitivas recursivas). Es decir: ${\cal PR} \subseteq {\cal R} \subseteq {\cal P}$. De hecho, veremos más adelante que ${\cal PR} \subset {\cal R} \subset {\cal P}$.
Veamos a modo de ejemplos (pequeños lemas) algunas funciones primitivas recursivas que serán de utilidad más adelante.
!!!teorema:Lema: Función constante
Para cada $n\geq 1$, y cada $a\in {\Bbb N}$ la función constante $C_a^n:{\Bbb N}^n\to {\Bbb N}$, definida como: $$C_a^n(\vec{x})=a,\ \forall \vec{x} \in {\Bbb N}^n$$ es primitiva recursiva.
**Demostración**:
Por inducción en $a$:
* $\underline{a=0}$: $C_0^n(\vec{x})=O(\Pi_1^n(\vec{v}))$
* $\underline{a\rightarrow a+1}$: $C_{a+1}^n(\vec{x})=S(C_a^n(\vec{x}))$
!!!teorema:Lema: Función Predecesor
La función predecesor $pr:{\Bbb N} \to{\Bbb N}$, dada por: $$pr(x)=\begin{cases} 0 & \mbox{ si } x=0\\ x-1 & \mbox{ si } x\neq 0\end{cases}$$
**Demostración**:
Basta observar que $pr(0)=0$ y $pr(x+1)=x$, luego $pr={\bf R}(0,\Pi_1^2)$ (se trata de una definición por recursión en el caso especial $n=0$).
!!!teorema:Lema: Diferencia Aritmética
La función diferencia aritmética, $∸:{\Bbb N}^2 \to {\Bbb N}$, definida como: $$x ∸ y=\begin{cases} 0 & \mbox{ si }x\leq y\\ x-y & \mbox{ si } x>y \end{cases}$$
**Demostración**:
Sea $f:{\Bbb N}^2 \to {\Bbb N}$, dada por $f={\bf R}(\Pi_1^1,{\bf C}(pr,\Pi_3^3))$, se verifica que $f(x,y)=x ∸ y$ (por inducción sobre $y$). Luego $∸ \in {\cal PR}$.
A partir de ahora, y como no hay posible confusión, notaremos esta función con el símbolo habitual de $-$.
!!!teorema:Lema: Función signo
La función signo, $sg:{\Bbb N} \to {\Bbb N}$, dada por: $$sg(x)=\begin{cases} 0&\mbox{ si }x=0\\1&\mbox{ si }x\neq 0\end{cases}$$
**Demostración**:
Basta observar que $sg={\bf R}(0,C_1^2)\in{\cal PR}$.
!!!teorema:Lema: Función Signo Inverso
La función signo inverso, $\overline{sg}:{\Bbb N}\to {\Bbb N}$, dada por: $$\overline{sg}(x)=\begin{cases} 1&\mbox{ si }x=0\\0&\mbox{ si }x\neq 0\end{cases}$$
**Demostración**:
Basta tener en cuenta que que $\overline{sg}={\bf R}(1,C_0^2)\in {\cal PR}$.
!!!teorema: Lema: Función Suma
La función suma: $$\begin{cases} x+0 & = & x\\ x+(y+1) & = & (x+y)+1 \end{cases}$$
**Demostración**:
Basta tener en cuenta que:
$$\begin{cases} sum(x,0) & = & x\\ sum(x,y+1) & = & sum(x,y)+1=S(sum(x,y)) \end{cases}$$
Es decir, $sum={\bf R}(\Pi_1^1,{\bf C}(S;\Pi_1^3))\in {\cal PR}$.
!!!teorema:Lema Función Producto
La función producto: $$\begin{cases} x\cdot 0 & = & 0\\ x\cdot (y+1) & = & (x\cdot y)+x\end{cases}$$
**Demostración**:
Basta tener en cuenta que:
$$\begin{cases} f(x,0) & =& 0\\ f(x,y+1)& = & f(x,y)+x = sum(f(x,y),x) \end{cases}$$
Es decir, $f={\bf R}({\cal O},{\bf C}(sum;\Pi_3^3,\Pi_1^3))\in {\cal PR}$.
!!!teorema:Lema: Función Distancia
$F(x,y)=|x-y|$ es recursiva.
**Demostración**:
En efecto, $F(x,y)=|x-y|=(x ∸ y)+(y ∸ x)$, luego
$$F={\bf C}(+;{\bf C}(∸;\Pi_1^2,\Pi_2^2),{\bf C}(∸;\Pi_2^2,\Pi_1^2))\in {\cal R}$$
!!!note: Observación
Existen funciones recursivas que no son totales. Por ejemplo, si $f(x,y)=x+y$, entonces
$$g(x)=(\mu y)(f(x,y)=0)=\begin{cases} 0 & \mbox{si } x=0\\ \uparrow & \mbox{si } x\neq 0 \end{cases}$$
A continuación probaremos que toda función recursiva es $\mathtt{GOTO}$--computable.
!!!teorema:Proposición
Las funciones básicas son $\mathtt{GOTO}$-computables.
**Demostración:** Para cada función básica definiremos un programa que la calcula:
* La función nula:
```none
Y <- 0
```
* Las funciones de proyección:
```none
Y <- X_i
```
* La función sucesor:
```none
Y <- X
Y <- Y + 1
```
!!!teorema:Proposición
Sean $f:{\Bbb N}^k\to {\Bbb N}$ y $g_1,...,g_k:{\Bbb N}^n\to{\Bbb N}$ funciones $\mathtt{GOTO}$-computables, entonces $h={\bf C}(f;g_1,...,g_k)$ es $\mathtt{GOTO}$-computable.
**Demostración:** El siguiente programa calcula la composición:
```none
Z1 <- g1(X1,...,Xn)
...
Zk <- gk(X1,...,Xn)
Y <- f(Z1,...,Zk)
```
donde $f,\ g_1,\dots,\ g_k$ se usan como macros de un programa que las calcula.
!!!teorema:Proposición
Sean $g:N^n\to {\Bbb N}$ y $h:{\Bbb N}^{n+2} \to {\Bbb N}$ funciones $\mathtt{GOTO}$-computables, entonces $f={\bf R}(g,h)$ es $\mathtt{GOTO}$-computable.
**Demostración:** El siguiente programa calcula la recursión de $g$ y $h$:
```none
Y <- g(X1,...,Xn)
[A] IF X_{n+1} != 0 GOTO E
Z2 <- Y
Y <- h(X1,...,Xn,Z,Z2)
Z <- Z + 1
X_{n+1} <- X_{n+1} - 1
GOTO A
```
donde $g,\ h$ se usan como macros de un programa que las calcula.
!!!teorema:Proposición
Si $f:{\Bbb N}^{k+1}- \to {\Bbb N}$ es $\mathtt{GOTO}$--computable, entonces $f_\mu$ también es $\mathtt{GOTO}$--computable.
**Demostración:** El siguiente programa calcula $f_\mu(\vec{x})= (\mu y)(f(\vec{x},y)=0)$:
```none
[A] Z_2 <- f(X1,...,Xn,Y)
if Z_2 != 0 GOTO E
Y <- Y + 1
GOTO A
```
donde $f$ se usa como macro de un programa que la calcula.
!!!teorema:Teorema
Toda función recursiva es $\mathtt{GOTO}$-computable.
**Demostración:** Por inducción sobre funciones recursivas. Basta observar que, como acabamos de probar, las funciones básicas son $\mathtt{GOTO}$-computables, y la clase de las funciones $\mathtt{GOTO}$-computables es cerrada bajo composición, recursión primitiva y $\mu$--recursión. Como ${\cal P}$ es la menor que verifica esa propiedad, debe estar contenida en el conjunto de funciones $\mathtt{GOTO}$-computables.
!!!Tip: Problema
¿Es toda función $\mathtt{GOTO}$-computable recursiva? Veremos que la respuesta es SÍ: por lo que, finalmente, la clase de las funciones $\mathtt{GOTO}$-computables es igual a la de las funciones recursivas.
De hecho, la clase ${\cal P}$ se identifica con la clase de las funciones computables algorítmicamente. Éste es el contenido de lo que se conoce como **Tesis de Church**:
!!!note: Tesis de Church
Una función es algorítmicamente computable si y sólo si es recursiva.
Todos los modelos de computación conocidos dan lugar a la misma clase de funciones computables: la clase de las funciones recursivas.
# Predicados y Conjuntos Recursivos
!!!def:Definición: Predicados (Primitivos) Recursivos
Dado $A\subseteq {\Bbb N}^n$, diremos que $A$ es un conjunto **(Primitivo) Recursivo** si la función característica de $A$ es (primitiva) recursiva, es decir, si $\chi_A \in ({\cal PR})\ {\cal R}$.
La clase de los conjuntos recursivos se notará por ${\cal R}_*$ y las de los conjuntos primitivos recursivos por ${\cal PR}_*$. Como es habitual, identificaremos predicados sobre ${\Bbb N}^n$ con subconjuntos de ${\Bbb N}^n$ y, en consecuencia, ${\cal R}_*$ denotará también a la clase de los predicados recursivos y ${\cal PR}_*$ a la clase de los predicados primitivos recursivos.
!!!teorema:Teorema
Dado $A\subseteq{\Bbb N}^n$, son equivalentes:
1. $A\in {\cal R}_*$.
2. Existe $f \in {\cal R}$ tal que: $\forall \vec{x}\in {\Bbb N}^n (f(\vec{x})=0 \Leftrightarrow \vec{x} \in A)$.
3. Existen $k\in {\Bbb N}$ y $h\in {\cal R}$ tales que: $\forall \vec{x}\in {\Bbb N}^n (\vec{x}\in A \Leftrightarrow h(\vec{x})=k)$.
**Demostración:** $∸$
Haremos un camino de pruebas cíclico:
* ($1\Rightarrow 2$) Sea $f(\vec{x})=1 ∸ \chi_A(\vec{x})=C_1^n(\vec{x})∸ C_A(\vec{x})={\bf C}(∸;C_1^n,\chi_A)(\vec{x})$.
* ($2\Rightarrow 3$) Trivial.
* ($3\Rightarrow 1$) Sean $h$ y $k$ como en (3). Entonces $\chi_A(\vec x)=\overline{sg}(|h(\vec x)- C^n_k(\vec x)|)$ y, por tanto, $\chi_A={\bf C}(\overline{sg};{\bf C}(F;h,C^n_k))\in {\cal R}$, siendo $F(x,y)=|x-y|$.
!!!!teorema:Proposición
Sea $P_1$ y $P_2$ dos predicados sobre ${\Bbb N}^n$. Se verifica que:
1. Si $P_1,P_2\in {\cal R}_*$, entonces $P_1\lor P_2, \, P_1\land P_2\in {\cal R}_*$.
2. Si $P_1\in{\cal R}_*$, entonces $\lnot P_1\in {\cal R}_*$.
**Demostración:**
Basta tener en cuenta que:
1. $P_1\land P_2=P_1 \cdot P_2= {\bf C}({\scriptsize \bullet};P_1,P_2) \in {\cal R}$.
$(P_1\lor P_2)(\vec{x})=sg(P_1(\vec{x})+P_2(\vec{x}))$.
2. $\lnot P_1(\vec{x})=\overline{sg}(P_1(\vec{x}))={\bf C}(\overline{sg};P_1)(\vec{x})\in {\cal R}$.
!!!!teorema:Proposición
Sean $f:{\Bbb N}^n \to {\Bbb N}$ y $g:{\Bbb N}^m \to {\Bbb N}$. Si $f,g \in {\cal R}$, entonces $$B=\{(\vec{x},\vec{y}) \in {\Bbb N}^{n+m}:\ f(\vec{x})=g(\vec{y})\} \in {\cal R}_*.$$
**Demostración:** Basta observar que:
$$(\vec{x},\vec{y})\in B \Leftrightarrow f(\vec{x})=g(\vec{y}) \Leftrightarrow |f(\vec{x})-g(\vec{y})|=0 \Leftrightarrow {\bf C}(+;{\bf C}(-;f,g),{\bf C}(-;g,f))(\vec{x},\vec{y})=0$$
!!!!teorema:Proposición (Definición por casos)
Sean $f_1,...,f_k \in {\cal R}$, funciones de ${\Bbb N}^n$ en ${\Bbb N}$, y sean $A_1,...,A_k\subseteq {\Bbb N}^n$ una partición por conjuntos recursivos (es decir, $\bigcup_{i=1}^k A_i={\Bbb N}^n$, y si $i\neq j$ entonces $A_i\cap A_j=\emptyset$).
Sea $g:{\Bbb N}^n\to {\Bbb N}$ definida por:
$$g(\vec{x})=\begin{cases}
f_1(\vec{x})& \mbox{, si }\vec{x} \in A_1\\
\quad \vdots& \quad \vdots\\
f_k(\vec{x}) & \mbox{, si }\vec{x} \in A_k \end{cases}$$
Entonces $g\in {\cal R}$.
**Demostración:** Basta observar que:
$$g(\vec{x})=f_1(\vec{x}) \cdot \chi_{A_1}(\vec{x})+f_2(\vec{x}) \cdot \chi_{A_2}(\vec{x})
+\cdots+ f_k(\vec{x}) \cdot \chi_{A_k}(\vec{x})$$
!!!note
En todos los resultados presentados hasta ahora en esta sección, si los conjunto y funciones considerados en las hipótesis son primitivos recursivos, entonces las funciones y conjuntos que aparecen en la conclusión son también primitivos recursivos.
!!!!teorema:Proposición
Dada $f:{\Bbb N}^n\to {\Bbb N}$ **total**, son equivalentes:
1. $f\in {\cal R}$.
2. $G(f)\in {\cal R}_*$.
**Demostración:**
* ($1\Rightarrow 2$) $G(f)=\{(\vec{x},y):\ f(\vec{x})=y\}=\{(\vec{x},y):\ f(\vec{x})=\Pi_1^1(y)\}\in {\cal R}_*$
* ($2\Rightarrow 1$) $f(\vec{x})=(\mu y)((\vec{x},y)\in G(f))$, luego $f\in {\cal R}$.
## Suma, Producto y Cuantificación Acotadas
!!!def:Definición
Dada $f:{\Bbb N}^{n+1}\to {\Bbb N}$:
* La **suma acotada** definida por $f$ es la función ${(\sum f):{\Bbb N}^{n+1}\to {\Bbb N} }$, definida por: $$(\sum f)(\vec{x},y)=\sum_{k\leq y}f(\vec{x},k)$$
* El **producto acotado** definido por $f$ es la función $(\prod f):{\Bbb N}^{n+1}\to {\Bbb N}$, definida por: $${(\prod f)(\vec{x},y)=\prod_{k\leq y}f(\vec{x},k)}$$
!!!teorema:Proposición
Si $f$ es (primitiva) recursiva, entonces $\sum f,\ \prod f$ son (primitivas) recursivas.
**Demostración:**
* Para la suma acotada consideremos la siguiente definición por recursión:$$\begin{cases}(\sum f)(\vec{x},0) & = & f(\vec{x},0)=g(\vec{x})=f(\vec{x},O(\vec{x}))\\ (\sum f)(\vec{x},y+1) & = & (\sum f)(\vec{x},y)+f(\vec{x},y+1)\end{cases}$$
* Y para el producto, la definición por recursión queda: $$\begin{cases}(\prod f)(\vec{x},0) & = & f(\vec{x},0)\\ (\prod f)(\vec{x},0) & = & (\prod f)(\vec{x},y)\cdot f(\vec{x},y+1)\end{cases}$$
!!!teorema:Proposición
${\cal R}_*$ es cerrada bajo cuantificación acotada. Es decir, si $P$ es un predicado sobre ${\Bbb N}^{n+1}$ recursivo, entonces $(\exists y)_{\leq z} P$ y $(\forall y)_{\leq z} P$ son recursivos. Lo mismo es cierto para ${\cal PR}_*$.
**Demostración:**
Basta tener en cuenta que:
$$\begin{cases}(\exists y)_{\leq z} P(\vec{x},z) & = & sg(\sum_{y\leq z} P(\vec{x},y)) &=& sg((\sum P)(\vec{x},z))\\
(\forall y)_{\leq z} P(\vec{x},z) &=& \prod_{y\leq z}P(\vec{x},y) &=& (\prod P)(\vec{x},z)\end{cases}$$
!!!def:Definición
Sea $P(x_1,...,x_n,y)$ un predicado sobre ${\Bbb N}^{n+1}$. La función definida por **minimización acotada** a partir de $P$ es la función $g:{\Bbb N}^{n+1} \to {\Bbb N}$ dada por:
$$g(\vec{x},z)=\begin{cases}
min\{y\leq z:\ P(\vec{x},y)\}& \mbox{, si existe }y\leq z \mbox{ tal que } P(\vec{x},y)\\
0 & \mbox{, en otro caso}
\end{cases}$$
Escribiremos $g(\vec{x},z)=min_{y\leq z}P(\vec{x},y)=(\mu y)_{\leq z} P(\vec{x},y)$
!!!teorema:Proposición
Si $P$ es un predicado recursivo, entonces $g \in {\cal R}$ (definida como en la definición anterior).
**Demostración:**
Consideremos la función $h:{\Bbb N}^{n+1}\to {\Bbb N}$ definida por $\mu$--recursión de tal modo que $h(\vec{x},z)=(\mu y)(P(\vec x,y)\lor z>y)$. Entonces $h\in {\cal R}$. Puesto que $P$ es recursivo, el predicado $(\exists y)_{\leq z}P$ es recursivo y $g$ queda determinada por la siguiente definición por casos:
$$g(\vec{x},z)=\left\{
\begin{array}{ll}
h(\vec{x},z) & \mbox{, si }(\exists y)_{\leq z}P(\vec{x},y)\\
& \\
0 & \mbox{, en otro caso} \\
\end{array}\right.$$
!!!note:Corolario
Si $P(\vec{x},y)$ es un predicado (primitivo) recursivo sobre ${\Bbb N}^{n+1}$, y $h:{\Bbb N}^n\to {\Bbb N}$ es (primitiva) recursiva, entonces $f:{\Bbb N}^n\to {\Bbb N}$ definida por: $$f(\vec{x})=(\mu y)_{\leq h(\vec{x})} P(\vec{x},y)$$ es (primitiva) recursiva.
**Demostración:**
Sea $g(\vec{x},z)=(\mu y)_{\leq z} P(\vec{x},y)$, entonces $f(\vec{x})=g(\vec{x},h(\vec{x}))$.
Damos a continuación otra serie de funciones que hacen uso de los resultados anteriores y que nos serán de utilidad más adelante.
!!!teorema:Lema: Función Cociente
La función cociente: ${\displaystyle \lfloor \frac{x}{y}\rfloor}=min_{t\leq x}((t+1)\cdot y >x)$.
**Demostración:**
Ya que $P(x,y,t)\equiv((t+1)\cdot y >x)\equiv((t+1)\cdot y - (x+1)=0)$ es primitivo recursivo.
!!!teorema:Lema: Función Resto
La función resto: $rm(x,y)=x - (\lfloor \frac{x}{y} \rfloor \cdot y)$
!!!teorema: Lema: Menor primo mayor que $x$
$f:{\Bbb N}\to {\Bbb N}$, definida por $f(x)=$ _el menor primo mayor que_ $x$.
**Demostración:**
El predicado $Primo(y)\equiv(y>1 \wedge (\forall x)_{\leq y}(x\nmid y \vee x=y \vee x=1))$, donde $x\mid y\equiv(rm(x,y)=0)$ (y por tanto $x\nmid y\equiv \neg (x \mid y)$ es primitivo recursivo).
Sabemos que $f(x)\leq x!+1$, por tanto, $f(x)=(\mu y)_{\leq x!+1}(Primo(y)\wedge y>x)$
!!!teorema: Lema: $n$-ésimo primo
$P_n=$ *el $n$-ésimo primo*, se define por recursión como:
$$\begin{cases}
p_0=0 &\\
p_{n+1}=f(p_n) &
\end{cases}$$
# Números de Gödel
!!!def:Definición: Función Par
Definimos como $\langle x,y \rangle=2^x\cdot (2y+1) - 1$, la llamada **función par.**
!!!teorema:Proposición
La función par verifica:
* $\langle \dot , \dot \rangle: {\Bbb N}^2 \to {\Bbb N}$ biyectiva y primitiva recursiva.
* Si definimos $l,r:{\Bbb N}\to {\Bbb N}$ como
$$l(z)=(\mu x)_{\leq z}((\exists y)_{\leq z}(z=\langle x,y \rangle))$$
$$r(z)=(\mu y)_{\leq z}((\exists x)_{\leq z}(z=\langle x,y \rangle))$$
se tiene que:
* (**a**) $l,r \in {\cal PR}$,
* (**b**) $\langle l(z),r(z) \rangle=z$,
* (**c**) $l(\langle x,y \rangle)=x$,
* (**d**) $r(\langle x,y \rangle)=y$,
* (**e**) $l(z),r(z)\leq z$.
!!!def:Definición: Número de Gödel
Dada $(k_1,...,k_n)\in {\Bbb N}^n$, el **número de Gödel** de $(k_1,...,k_n)$ se define como:
$$[k_1,....,k_n]={\displaystyle \prod_{i=1}^n} p_i^{k_i}$$
Por tanto a cada sucesión numérica finita se le asocia un número (que la codifica), y cada número puede ser visto como una sucesión.
!!!Tip: Ejemplos
* $[3,1,2,0,1]=p_1^3\cdot p_2^1\cdot p_3^2\cdot p_4^0\cdot p_5^1=2^3\cdot 3^1\cdot 5^2\cdot 7^0\cdot 11^1=8\cdot 3\cdot 25\cdot 11=6600$
* $20=4 \cdot 5=2^2\cdot 5 \Rightarrow 20=[2,0,1]$
!!!teorema:Teorema
$$[a_1,...,a_n]=[b_1,...,b_n] \Leftrightarrow \forall i\ (1\leq i\leq n \rightarrow a_i=b_i)$$
!!!def:Definición: Longitud
Se define la longitud de una sucesión como:
$$Lt(x)=(\mu i)_{\leq x} ((x)_i\neq 0 \wedge (\forall j)_{\leq x}(j\leq i \vee (x)_j=0))$$
donde $(x)_i=(\mu t)_{\leq x}\neg (p_i^{t+1}\mid x)$.
!!!note:Observaciones
Es fácil probar que:
* Las funciones $Lt(x)$ y $(x)_i$ son primitivas recursivas.
* Para todo $i\geq 1$ se tiene que $(0)_i=0$ y $(1)_i=0$.
* Si $k>Lt(x)$, entonces $(x)_k=0$.
* $([a_1,...,a_n])_i=\begin{cases} a_i & 1\leq i\leq n\\ 0 & \mbox{ en otro caso}\end{cases}$
* Si $n\geq Lt(x)$, entonces $[(x)_1,...,(x)_n]=x$.
# Codificación de Programas: Aritmetización
A continuación veremos cómo asignar un número a cada $\mathtt{GOTO}$-programa de modo que se establezca una aplicación biyectiva entre el conjunto de los $\mathtt{GOTO}$-programas y ${\Bbb N}$.
!!!note:Codificación
* Comenzamos asignando un número no nulo a cada variable y etiqueta. Para ello, ordenamos las variables y etiquetas de la siguiente forma: $$Y,X_1,Z_1,X_2,Z_2,...,X_n,Z_n,...$$ $$A_1,B_1,C_1,D_1,E_1,A_2,B_2,C_2,...$$ Dada un variable, $V$, o etiqueta, $L$, el número correspondiente lo denotaremos por $\#(V)$ o $\#(L)$, y se define como: $$\#(Y)=1,\ \#(X_i)=2i,\ \#(Z_i)=2i+1$$ $$\#(A_i)=5(i-1)+1,\ \#(B_i)=5(i-1)+2$$ $$\#(C_i)=5(i-1)+3,\ \#(D_i)=5(i-1)+4,\ \#(E_i)=5i$$ Así, a cada variable corresponde un único número, y a cada número una única variable; y lo mismo puede decirse de las etiquetas.
* Ahora asignamos un número a cada instrucción de $\mathtt{GOTO}$ (etiquetada o no), de la siguiente forma: Si $I$ es una instrucción de $\mathtt{GOTO}$, el número de $I$ es:
$$\#(I)=\langle a, \langle b,c \rangle \rangle$$ donde:
1. Si $I$ tiene etiqueta $L$, entonces $a=\#(L)$ ($a=0$ si no tiene etiqueta).
2. Si $V=var(I)$, entonces $c=\#(V)-1$.
3. $b$ codifica el tipo de instrucción como:
1. Si $I$ es del tipo $V\leftarrow V$, entonces $b=0$.
2. Si $I$ es del tipo $V\leftarrow V + 1$, entonces $b=1$.
3. Si $I$ es del tipo $V\leftarrow V - 1$, entonces $b=2$.
4. Si $I$ es del tipo $IF\ V\neq 0\ GOTO\ L$, entonces $b=\#(L)+2$.
De este modo se define una aplicación biyectiva del conjunto de instrucciones de $\mathtt{GOTO}$ en ${\Bbb N}$.
!!!Tip: Ejemplos de codificación/decodificación de instrucciones:
* $I_1:\ X\leftarrow X + 1 \Rightarrow \#(I_1)=\langle 0,\langle 1,1\rangle \rangle=\langle 0,5\rangle =10$
* $I_2:\ [B]\ X\leftarrow X - 1 \Rightarrow \#(I_2)=\langle 2,\langle 2,1\rangle\rangle=\langle 2,11\rangle=91$
* $\#(I_3)=231$, hemos de calcular $x,y$ tales que $\langle x,y\rangle=231$, para ello, buscamos el mayor $x$ tal que $2^x\mid (231+1)$, en nuestro caso $x=3$, y despejamos el valor de $y$, resultando que $231=\langle 3,14\rangle$; repetimos el proceso con $14$, resultando que $14=\langle 0,7\rangle$, por tanto $231=\langle 3,\langle 0,7\rangle\rangle$, de donde: $I_3:\ [C]\ X_4\leftarrow X_4$.
!!!note:Codificación (continuación)
* Por último asignamos un número a cada programa $P$ de $\mathtt{GOTO}$. Si $P$ es $I_1,...,I_n$ entonces:
$$\#(P)=[\#(I_1),...,\#(I_n)]-1$$
Todo número determina un programa y números distintos determinan programas distintos:
Dado $n\in {\Bbb N}$, escribimos la factorización prima de $n+1=\prod_{i=1}^k p_i^{a_i}$. Si $I_1,...,I_k$ son instrucciones tales que $\#(I_i)=a_i$, entonces el programa $P:I_1,...,I_k$ es tal que $\#(P)=n$.
Si $n_1,n_2$ son dos números que codifican el mismo programa $P$, entonces:
$$k=Lt(n_1+1)=Lt(n_2+1) \wedge \forall\ i\leq k\ (n_1+1)_i=(n_2+1)_i$$
Luego $n_1+1=\prod_{i=1}^k p_i^{\#(I_i)}=\prod_{i=1}^{Lt(n_1+1)} p_i^{\#(I_i)}=\prod_{i=1}^{Lt(n_2+1)} p_i^{\#(I_i)}=n_2+1$, y así, $n_1=n_2$.
!!!Tip: Ejemplo de codificación de programas
Se $P$ el programa:
```none
[B] X <- X - 1
IF X != 0 GOTO B
```
Entonces el código asociado es: $\#(I_1)=91,\ \#(I_2)=94$, y por tanto: $$\#(P)=[91,94]-1=2^{91}\cdot 3^{94}-1$$
# El Teorema de la Forma Normal
!!!teorema:Teorema de la Forma Normal
Para cada $n>0$ existe una función, $U_n:{\Bbb N}^{n+1}- \to {\Bbb N}$, $\mathtt{GOTO}$-computable tal que para cada $\mathtt{GOTO}$-programa, $P$, si $\#(P)=m$ entonces:
$$\forall\ \vec{x}\in {\Bbb N}^n,\ U_n(\vec{x},m)\simeq \psi_P^{(n)}(\vec{x})$$
**Demostración:**
La demostración consiste en escribir un programa, $U_n$, que para cada programa, $P$, simule $P$ sobre cada entrada $X_1,...,X_n$. Tomaremos entonces $U_n=\psi_{U_n}^{(n+1)}$.
Dado un programa, $P$, una computación de $P$ es una sucesión de descripciones instantáneas cada una de las cuales es el sucesor de la descripción anterior. Cada descripción instantánea está a su vez dada por un número (la instrucción que debe ejecutarse a continuación) y un estado (que guarda los valores de las variables que están siendo usadas en el momento actual).
Dado que cada variable tiene asignado un número distinto de $0$, a través de la sucesión:
$Y,X_1,Z_1,X_2,Z_2,...,X_n,Z_n,...$
podemos representar un estado, $\sigma$, por un número:
$m=[\sigma(Y),\sigma(X_1),\sigma(Z_1),...]$
Por ejemplo, $\sigma=\{Y=3,\ X_1=2,\ Z_1=0,\ X_2=1\}$ corresponde al número de Gödel: $[3,2,0,1]=2^3 3^2 5^0 7^1=504$.
Modificar el estado de una descripción instantánea a la siguiente sólo conlleva sumar o restar $1$ a una de las variables, para llevar esto a cabo solo debemos multiplicar o dividir por el primo adecuado. Por ejemplo, en el caso anterior, sumar $1$ a $Z_1$ es equivalente a hacer el producto $m\cdot 5=[3,2,1,1]$; restar $1$ a $X_1$ es equivalente a hacer el calcular $\frac{m}{3}=[3,1,0,1]$; sumar $1$ a $Z_3$ es equivalente a hacer el producto $m\cdot 17=[3,1,0,1,0,0,1]$.
Para guardar una descripción instantánea del programa $P$ necesitamos dos variables:
* $K$: para guardar el número de la siguiente instrucción a ejecutar.
* $S$: para guardar el estado actual de las variables (número de Gödel).
En lo que sigue, y solo para facilitar la interpretación del programa universal, haremos uso de variables que no están permitidas en el lenguaje $\mathtt{GOTO}$. Por supuesto, es posible reescribirlo usando variables de trabajo permitidas.
El programa $U_n$ recibe como entrada los valores $X_1,...,X_n$ y el número que codifica el programa $P$ (en la variable $X_{n+1}$) y asignamos valores iniciales a las variables auxiliares básicas:
Creamos un bucle que irá pasando de una descripción instantánea a la siguiente hasta alcanzar una descripción instantánea terminal. El valor de $K=0$ se utilizará para las etiquetas de salida (aquellas que no aparecen etiquetando instrucciones).
* En $Z=[\#(I_1),...,\#(I_r)]$ están codificadas las instrucciones de $P$.
* La $K$-ésima instrucción es $(Z)_K=\#(I_K)$, que además, tendrá la forma: $\#(I_K)=\langle a,\langle b,c\rangle\rangle$, donde $a,b$ y $c$ reflejan la estructura de dicha instrucción según hemos indicado en las notas anteriores.
* Si llamamos $U=r((Z)_K)$, entonces $U=\langle b,c\rangle$, y por tanto, $r(U)+1=c+1=\#(var(I_K))$, y $l(U)=b$, el tipo de instrucción que ocupa la línea $K$.
El programa Universal $U_n$ quedaría entonces:
!!!note: Teorema (Función STEP)
Para cada $n>0$ el predicado $STP^{(n)}(x_1,...,x_n,y,t)$ definido en ${\Bbb N}^{n+2}$ como:
$$STP^{(n)}(x_1,...,x_n,y,t) \Leftrightarrow \begin{cases}
\mbox{existe una computación del programa que codifica $y$}&\\
\mbox{de longitud $\leq t+1$ comenzando por $x_1,...,x_n$}&
\end{cases}$$
es primitivo recursivo.
**Demostración:**
Una computación es una sucesión de descripciones instantáneas cada una de las cuales es el sucesor de la anterior. Cada descripción puede escribirse como un par $\langle i,z\rangle$, donde $i$ refleja el número de línea y $z$ la codificación del estado de las variables. Y viceversa, todo número puede ser visto como una descripción instantánea. Veamos cómo definir una función $Suc:{\Bbb N}^2\to {\Bbb N}$ que nos devuelva el código de la descripción instantánea sucesora.
En primer lugar describiremos algunas funciones útiles:
* $LBL(i,y)=l((y+1)_i)$: etiqueta de la $i$-ésima instrucción del programa codificado por $y$ ($0$ si no está etiquetada).
* $VAR(i,y)=r(r((y+1)_i))+1$: variable de la $i$-ésima instrucción del programa codificado por $y$.
* $INSTR(i,y)=l(r((y+1)_i))$: tipo de instrucción de la línea $i$-ésima del programa codificado por $y$.
* $LBL'(i,y)=l(r((y+1)_i))- 2$: etiqueta a la que envía la instrucción $i$-ésima del programa en caso de ser de tipo condicional.
Está claro que todas estas funciones son primitivas recursivas.
La definición de la función sucesora sería ($k$ es la longitud de $P$):
$$Suc((i,\sigma),P)=\begin{cases}
(i+1,\sigma)& \mbox{si $i\leq k\ \wedge\ I_i$ es de tipo $V\leftarrow V$}\\
(i+1,\sigma^+)& \mbox{si $i\leq k\ \wedge\ I_i$ es de tipo $V\leftarrow V+1$}\\
(i+1,\sigma^-)& \mbox{si $i\leq k\ \wedge\ I_i$ es de tipo $V\leftarrow V-1$}\\
(j,\sigma)& \mbox{si $i\leq k\ \wedge\ I_i$ es de tipo $IF\ V\neq 0\ GOTO\ L$}\\
&\quad \wedge\ j=\min\{n\leq k:\ L \mbox{ es la etiqueta de } I_n\}\\
(k+1,\sigma)& \mbox{en otro caso}\\
\end{cases}$$
La expresión numérica de cada caso anterior sería:
$$\begin{cases} SKIP(x,y) &\equiv& (INSTR(l(x),y)=0\ \wedge\ l(x)\leq Lt(y+1))\ \vee\\
& &\vee\ (INSTR(l(x),y) \geq 2\ \wedge\ (p_{Var(l(x),y)} \mid r(x)))\\
INCR(x,y)&\equiv &INSTR(l(x),y)=1\\
DECR(x,y) &\equiv& INSTR(l(x),y)=2\ \wedge\ p_{Var(l(x),y)} \mid r(x)\\
COND(x,y) &\equiv & INSTR(l(x),y)>2\ \wedge\ p_{Var(l(x),y)} \mid r(x)\ \wedge\\
& & (\exists i)_{\leq Lt(y+1)}\ (LBL(i,y)=LBL'(l(x),y)) \end{cases}$$
Quedando, por tanto, la función sucesor como la definición por casos:
$$Suc(x,y)=\begin{cases}
\langle l(x)+1,r(x)\rangle & \mbox{si } SKIP(x,y)\\
\langle l(x)+1,r(x)\cdot p_{Var(l(x),y)}\rangle & \mbox{si } INCR(x,y)\\
\langle l(x)+1,\lfloor \frac{r(x)}{p_{Var(l(x),y)} }\rfloor
\rangle& \mbox{si }
DECR(x,y)\\
\langle \min_{k\leq Lt(y+1)}\ (LBL(k,y)=LBL'(l(x),y)),r(x)
\rangle& \mbox{si
} COND(x,y)\\
\langle Lt(y+1)+1,r(x)\rangle & \mbox{en otro caso}
\end{cases}$$
Por tanto, $Suc\in {\cal PR}$, ya que se tiene de una definición por casos primitiva recursiva.
Sea ahora $INIT^{(n)}(x_1,...,x_n)=\langle 1,\prod_{i=1}^n (p_{2i})^{x_i}\rangle$, y definimos:
$$\begin{cases}
DESCINST^{(n)}(x_1,...,x_n,y,0)&=INIT^{(n)}(x_1,...,x_n) &\\
DESCINST^{(n)}(x_1,...,x_n,y,k+1)&=Suc(DESCINST^{(n)}(x_1,...,x_n,y,k),y)&\\
\end{cases}$$
Por tanto, $DESCINST \in {\cal PR}$. Por último, si definimos la propiedad **ser sucesión terminal** como:
$$TERM(x,y)\equiv (l(x)>Lt(y+1))$$
que es primitiva recursiva, se obtiene que:
$$STP^{(n)}(x_1,...,x_n,y,t) \Leftrightarrow TERM(DESCINST(x_1,...,x_n,y,t),y)$$
!!!teorema: Teorema de la Forma Normal (Kleene)
Existe $G \in {\cal PR}$, y para cada $n\geq 1$ un predicado primitivo recursivo $T_n\subseteq {\Bbb N}^{n+2}$ tal que para cada función $f:{\Bbb N}^n - \to {\Bbb N}$ $\mathtt{GOTO}$-computable existe $e\in {\Bbb N}$ verificando:
1. $f(\vec{x})\downarrow\ \Leftrightarrow\ (\exists z)(T_n(\vec{x},e,z))$
2. $f(\vec{x})\simeq G((\mu z) T_n(\vec{x},e,z))$
**Demostración:**
Dada $f$ en las condiciones anteriores, sea $P$ un programa tal que $f=\psi_P^{(n)}$, y sea $e=\#(P)$. Entonces, si $f(\vec{x})\downarrow$, existe $t\in {\Bbb N}$ tal que $STP^{(n)}(\vec{x},e,t)$, y además si $f(\vec{x})=m$, entonces
$$m=(r(DESCINST^{(n)}(x_1,...,x_n,e,t)))_1$$
Sea $T_n(\vec{x},e,z)$ el predicado:
$$STP^{(n)}(x_1,...,x_n,e,r(z)) \wedge (r(DESCINST^{(n)}(x_1,...,x_n,e,r(z)))_1=l(z))$$
Entonces, $T_n \in {\cal PR}$ y verifica el teorema.
!!!teorema:Corolario
Una función es $\mathtt{GOTO}$-computable si y sólo si es recursiva.
**Demostración:**
Nos falta probar que si es $\mathtt{GOTO}$-computable entonces es recursiva. Para ello, dada $f:{\Bbb N}^n\to {\Bbb N}$ $\mathtt{GOTO}$-computable, existe $e\in {\Bbb N}$ tal que $f(\vec{x})\simeq G((\mu z) T_n(\vec{x},e,z))$. Puesto que $G\in {\cal PR}$, $T_n\in {\cal PR}_*$, se tiene que $h(\vec{x})=(\mu z)T_n(\vec{x},e,z)$ es recursiva, y por tanto $f\in
{\cal P}$.
!!!teorema:Corolario
${\cal R}$ es la menor clase de funciones, ${\cal C}$, que verifica:
1. Contiene a las funciones básicas.
2. Es cerrada bajo composición y recursión primitiva.
3. Si $g\in {\cal C}$ y $\forall \vec{x}\ \exists y\ (g(\vec{x},y)=0)$, entonces $g_\mu \in {\cal C}$.
**Demostración:**
Obviamente, si ${\cal C}$ es una clase verificando las condiciones anteriores, entonces ${\cal C}\subseteq {\cal R}$.
Dada $f:{\Bbb N}^n\to {\Bbb N}$, $f\in {\cal R}$, por el teorema de la forma normal existe $e\in {\Bbb N}$ tal que:
$$f(\vec{x})\downarrow\ \Leftrightarrow\ (\exists z)(T_n(\vec{x},e,z)),\ \mbox{ y } f(\vec{x})=G((\mu z)(T_n(\vec{x},e,z)))$$
Sea $g(\vec{x},z)=1 - T_n(\vec{x},e,z)$, entonces $g\in {\cal R}$ y $\forall \vec{x}\ \exists z\ (g(\vec{x},z)=0)$. Luego $h=g_\mu \in {\cal C}$, y se tiene el resultado.
!!!def:Definición
La función recursiva de índice $e$ (en $n$ variables) es:
$$\varphi_e^{(n)}(\vec{x})=U_n(\vec{x},e)=G((\mu z) T_n(\vec{x},e,z))$$
!!!note: Notación
${\cal P}^{(n)}=\{f:{\Bbb N}^n- \to {\Bbb N}:\ f \in {\cal P}\}$, las funciones recursivas $n$-arias.
!!!teorema:Teorema
Para cada $n\in {\Bbb N},\ n\geq 1$, la sucesión $\langle \varphi_e^n:\ e\in {\Bbb N}\rangle$ es una enumeración efectiva de las funciones recursivas $n$-arias, es decir:
* $\forall e\in{\Bbb N},\ \varphi_e^n\in {\cal P}^{(n)}$
* Si $f\in {\cal P}^{(n)}$, entonces $\exists e\in {\Bbb N},\ \varphi_e^n\simeq f$
* (Función universal) Existe $U_n\in {\cal P}^{(n)},$ tal que $\forall \vec{x} \in {\Bbb N}^n,\ U_n(\vec{x},e)\simeq \varphi_e^n(\vec{x})$
!!!teorema: Teorema de la Función Universal
Existe $U:{\Bbb N}^2- \to {\Bbb N}$ recursiva tal que:
$$\forall n\ \forall f \in {\cal P}^{(n)}\ \exists e \in {\Bbb N}(f(\vec{x})\simeq U([\vec{x}],e))$$
**Demostración:**
Basta cambiar en el programa $U_n$ las dos primeras líneas por:
Lo que nos da un programa $U$, tal que la función buscada es $\psi_U^{(2)}$.
!!!note: La Función de Ackerman:
Definamos las siguientes funciones por recursión:
$$\begin{cases} A_0(x)& =x+2\\
A_{n+1}(x) &=A_n^x(2)=\overbrace{A_n(2)(....(A_n(2))...}^{x\ veces})\end{cases}$$
Esto define una sucesión de funciones $A_n:{\Bbb N}\to {\Bbb N}$, todas ellas primitivas recursivas.
Sea $A:{\Bbb N}^2\to {\Bbb N}$, definida por $A(n,x)=A_n(x)$, esto es:
$$\begin{cases}
A(0,y) &=y+2&\\
A(n+1,0) &=2&\\
A(n+1,y+1) &=A(n,A(n+1,y))&\\
\end{cases}$$
Entonces $A\in {\cal R}$ (ya que podemos probar que es $\mathtt{GOTO}$--computable), pero $A\notin {\cal PR}$.
(insert menu.md.html here)