« TC: Programas y Funci… « || Inicio || » TC: Conjuntos Recursi… »

TC: Funciones Recursivas

Última modificación: 9 de Noviembre de 2017, y ha tenido 14 vistas

Etiquetas utilizadas: || || ||

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).

Definició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 $(x_1,...,x_n)\in {\Bbb N}^n$ 

$$h(x_1,...,x_n)\simeq f(g_1(x_1,...,x_n),...,g_k(x_1,...,x_n))$$ 

Definición: 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 $(x_1,...,x_n)\in {\Bbb N}^n$

$$\begin{cases}
f(x_1,...,x_n,0) & \simeq & g(x_1,...,x_n)\\
f(x_1,...,x_n,y+1) & \simeq & h(x_1,...,x_n,y,f(x_1,...,x_n,y)),\quad \mbox{ para todo } y \in {\Bbb N}
\end{cases}$$

Observaciones:

  • 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$).

Esto 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 admitimos que en la definición por recursión primitiva sea $n=0$. En dicho caso las ecuaciones que definen la función $f:{\Bbb N}\ - \to {\Bbb N}$ son:

$$\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. Expresaremos que $f$ ha sido definida por recursión primitiva a partir de $a$ y $h$, escribiendo $f={\bf R}(a,h)$.

Definició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)$.

Nota: 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 $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 termina.

Definición: 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$$

Definición: 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}$ pertenecen a ${\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}$.

Observaciones:

  • Puesto que ${\cal P}$ 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 recursivas. Para ello probaremos que:
    • La propiedad es cierta para las funciones básicas.
    • Si $f,g_1,...,g_k$ son $k+1$ funciones recursivas verificando la propiedad, 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 dicha propiedad.
    • Si $g$ y $h$ son dos funciones recursivas que verifican la propiedad y están en las condiciones de la definición por recursión primitiva, entonces $R(g,h)$ también verifica la propiedad.
    • Si $f$ es recursiva y verifica la propiedad, 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,...,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_j)_\mu$.

Funciones Recursivas Totales y Primitivas Recursivas

Existen dos clases de funciones recursivas que merecen destacarse: las Funciones Recursivas Totales y las Funciones Primitivas Recursivas

  • La clase de las Funciones Recursivas Totales se denotará por ${\cal R}$.
  • La clase de las Funciones Primitivas Recursivas, ${\cal PR}$, 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.

Observaciones:

  • 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).
  • Sabemos que ${\cal PR} \subseteq {\cal R} \subseteq {\cal P}$. De hecho, como veremos más adelante, ${\cal PR} \subset {\cal R} \subset {\cal P}$.

Ejemplos:

  • 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: 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}))$
  • 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}$$ 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$).
  • La función diferencia aritmética, ${{ \ {- \!\!\! -}^{\!\! \!\! \!\! \scriptsize{\bullet} } \ \ } }:{\Bbb N}^2 \to {\Bbb N}$, definida como: $$x {{ \ {- \!\!\! -}^{\!\! \!\! \!\! \scriptsize{\bullet} } \ \ } } y=\begin{cases} 0 & \mbox{ si }x\leq y\\ x-y & \mbox{ si } x>y \end{cases}$$ 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 {{ \ {- \!\!\! -}^{\!\! \!\! \!\! \scriptsize{\bullet} } \ \ } } y$ (por inducción sobre $y$). Luego ${{ \ {- \!\!\! -}^{\!\! \!\! \!\! \scriptsize{\bullet} } \ \ } } \in {\cal PR}$. A partir de ahora, y como no hay posible confusión, notaremos esta función con el símbolo habitual de $-$.
  • 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}$$ Basta observar que $sg={\bf R}(0,C_1^2)\in{\cal PR}$.
  • 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}$$ ya que se tiene que $\overline{sg}={\bf R}(1,C_0^2)\in {\cal PR}$.
  • La función suma: $$\begin{cases} x+0 & = & x\\ x+(y+1) & =  & (x+y)+1 \end{cases}$$ O escriito de otro modo: $$\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}$.
  • La función producto: $$\begin{cases} x\cdot 0 & = & 0\\ x\cdot (y+1) & = & (x\cdot y)+x\end{cases}$$ O escrito de otro modo: $$\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}$.
  • $F(x,y)=|x-y|$ es recursiva. En efecto, $F(x,y)=|x-y|=(x {{ \ {- \!\!\! -}^{\!\! \!\! \!\! \scriptsize{\bullet} } \ \ } } y)+(y {{ \ {- \!\!\! -}^{\!\! \!\! \!\! \scriptsize{\bullet} } \ \ } } x)$, luego $$F={\bf C}(+;{\bf C}({{ \ {- \!\!\! -}^{\!\! \!\! \!\! \scriptsize{\bullet} } \ \ } };\Pi_1^2,\Pi_2^2),{\bf C}({{ \ {- \!\!\! -}^{\!\! \!\! \!\! \scriptsize{\bullet} } \ \ } };\Pi_2^2,\Pi_1^2)))\in {\cal R}.$$
  • Existen funciones recursivas que no son totales. 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.

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:
Y <- 0
  • Las funciones de proyección:
Y <- X_i
  • La función sucesor: 
Y <- X
Y <- Y + 1

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:

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.

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$:

    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.

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)$:

[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: 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. 

Problema: ¿Es toda función $\mathtt{GOTO}$-computable recursiva? Veremos que la respuesta es SÍ: 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

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

Definición: 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}$.

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: 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:

  • ($1\Rightarrow 2$) Sea $f(\vec{x})=1 {{ \ {- \!\!\! -}^{\!\! \!\! \!\! \scriptsize{\bullet} } \ \ } } \chi_A(\vec{x})=C_1^n(\vec{x}){{ \ {- \!\!\! -}^{\!\! \!\! \!\! \scriptsize{\bullet} } \ \ } } C_A(\vec{x})={\bf C}({{ \ {- \!\!\! -}^{\!\! \!\! \!\! \scriptsize{\bullet} } \ \ } };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|$.

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:

  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}$.

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$$

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$ conjuntos recursivos tales que $\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})
+...+ f_k(\vec{x}) \cdot \chi_{A_k}(\vec{x}).$$

Nota: 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.

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

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)}$$

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}$$

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}$$

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)$

Proposición: Si $P$ es un predicado recursivo, entonces $g \in {\cal R}$.

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.$

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}))$.

Ejemplos:

  • La función cociente: ${\displaystyle \lfloor \frac{x}{y}\rfloor}=min_{t\leq x}((t+1)\cdot y >x)$.
    Ya que $P(x,y,t)\equiv((t+1)\cdot y >x)\equiv((t+1)\cdot y - (x+1)=0)$ es primitivo recursivo.
  • La función resto: $rm(x,y)=x - (\lfloor \frac{x}{y} \rfloor \cdot y)$
  • $f:{\Bbb N}\to {\Bbb N}$, definida por $f(x)=$ "el menor primo mayor que $x$''.
    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)$
  • $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

Definición: Definimos como $\langle x,y \rangle=2^x\cdot (2y+1) - 1$, la llamada función par.

Proposición: La función par verifica:

  • Es una función de ${\Bbb N}^2$ en ${\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)), \hspace{1cm} 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$.

Definición: 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.

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: $[a_1,...,a_n]=[b_1,...,b_n] \Leftrightarrow \forall i\ (1\leq i\leq n \rightarrow a_i=b_i)$

Definición: 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)$.

Observaciones:

  • 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}$.

  • 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}$.

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$.
  • 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$.

Nota: 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$.

Ejemplo de codificación de programas: Se $P$ el programa:

[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: 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.

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 habíamos visto en la sección anterior.

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:

Teorema:  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 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.

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}$.

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.

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))$

Notación: ${\cal P}^{(n)}=\{f:{\Bbb N}^n- \to {\Bbb N}:\ f \in {\cal P}\}$, las funciones recursivas $n$-arias.

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 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)}$.

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}$.

« TC: Programas y Funci… « || Inicio || » TC: Conjuntos Recursi… »