Siguiente: Dos esquemas de reiteración Un nivel arriba: Funciones recursivas primitivas Anterior: Funciones recursivas primitivas

Conceptos básicos

Recordamos que $I\!\!N^*$ denota al conjunto de secuencias de números naturales, incluída entre ellas a la vacía, $\mbox{\it nil}$, y que este conjunto es numerable. Por tanto, módulo una función biyectiva podemos identificar a $I\!\!N^*$ con $I\!\!N$ mismo, y lo mismo podría hacerse para cada producto cartesiano $I\!\!N^n$, con n>0. De manera estricta, podríamos plantear a la teoría de las funciones recursivas primitivas, considerando a todas ellas con dominio en $I\!\!N$. Sin embargo, es convencional referirse a un dominio del tipo $I\!\!N^n$ para cada función recursiva primitiva y, así, nos ajustaremos a esa convención.


La clase ${\cal FRP}$ de las funciones recursivas primitivas es la clase mínima de funciones que cumple con las propiedades siguientes:

1.

Caso ``base''. Las siguientes funciones están en la clase ${\cal FRP}$:

$$\begin{array}{lcrcl} \mbox{\it Funci\'on \lq\lq Cero''} &.& 0:I\!... ...\!\!N&,& \mbox{\bf x}=(x_1,\ldots,x_n)\mapsto x_i. \end{array}$$

2.

Caso inductivo. La clase ${\cal FRP}$ es cerrada bajo los esquemas de composición y recursión, i.e.

$$\begin{array}{rcr} g,f_1,\ldots,f_k\in{\cal FRP} &\Rightarro... ...\Rightarrow& \mbox{\it Recu}(g;h)\in{\cal FRP} \\ \end{array}$$

Proposición 1.1   Toda función recuriva primitiva es computable.

En efecto, se puede mostrar esto por inducción en la definición de las funciones recursivas primitivas. Para esto, basta ver que cada una de las funciones básicas en las recursivas primitivas es computable, lo cual es directo; y hay que tener en cuenta que la clase de las funciones computables es cerrada bajo los dos esquemas de composición y de recursión que definen a las recursivas primitivas. Veamos algunos ejemplos de funciones en ${\cal FRP}$.

1.

Constantes. Para cualquier $m\in I\!\!N$ la función constante $x\mapsto m$ está en ${\cal FRP}$. En efecto, probemos la aseveración por inducción en m. Para m=0 se cumple pues la función Cero está efectivamente en ${\cal FRP}$. Sea m>0. Supongamos que la función $c_m:x\mapsto m$ está en ${\cal FRP}$. Es claro que $c_{m+1}=\mbox{\it suc}\circ c_m$. Por tanto, c_m+1 está en ${\cal FRP}$ como composición de dos funciones en ${\cal FRP}$.

2.

Suma. Ya que para cualesquiera $x,y\in I\!\!N$ se cumple

$$\begin{eqnarray*}x+0 &=& x \\ x+(y+1) &=& (x+y)+1 \end{eqnarray*}$$

se tiene que

$$\begin{array}{lcl} \mbox{\it Suma}(x,0) &=& \mbox{\it identi... ...suc}(y)) &=& \mbox{\it suc}(\mbox{\it Suma}(x,y)) \end{array}$$

Por tanto, $\mbox{\it Suma}(x,y)=\mbox{\it Recu}(\pi_1^1,h)(x,y)$, donde $\forall x,y,z: h(x,y,z)=\mbox{\it suc}\circ \pi_3^3(x,y,z)$, de lo cual se sigue directamente que $\mbox{\it Suma}\in{\cal FRP}$ pues se obtiene por el esquema de recursión de funciones en ${\cal FRP}$.

3.

Producto. Ya que para cualesquiera $x,y\in I\!\!N$ se cumple

$$\begin{eqnarray*}x\cdot 0 &=& 0 \\ x\cdot(y+1) &=& x\cdot y+x \end{eqnarray*}$$

se tiene que

$$\begin{array}{lcl} \mbox{\it Producto}(x,0) &=& 0 \\ \mbox... ...\mbox{\it Producto}(x,y),\mbox{\it identidad}(x)) \end{array}$$

Por tanto, $\mbox{\it Producto}(x,y)=\mbox{\it Recu}(0,h)(x,y)$, donde $\forall x,y,z: h(x,y,z)=\mbox{\it Suma}(\pi_1^3,\pi_3^3)(x,y,z)$, de lo cual se sigue directamente que $\mbox{\it Producto}\in{\cal FRP}$ pues se obtiene por el esquema de recursión de funciones en ${\cal FRP}$.

4.

Suma reiterada. Si f es una función recursiva primitiva definamos $g:y\mapsto{\displaystyle \sum_{x=0}^y f(x)}$. g es la sumatoria de f.

$$\begin{eqnarray*}g(0) &=& f(0) \\ g(y+1) &=& g(y)+f(y+1) \end{eqnarray*}$$

se tiene que

$$\begin{array}{lcl} g(0) &=& f(0) \\ g(\mbox{\it suc}(y)) &=& \mbox{\it Suma}(f(\mbox{\it suc}(y)),g(y)) \end{array}$$

Por tanto, $g(y)=\mbox{\it Recu}(f\circ\pi_1^1,h)(y)$, donde $\forall y,z: h(y,z)=\mbox{\it Suma}(f(\mbox{\it suc}\circ\pi_1^2),\pi_2^1)(y,z)$, de lo cual se sigue directamente que $g\in{\cal FRP}$ pues se obtiene por el esquema de recursión de funciones en ${\cal FRP}$. Lo mismo vale si, en vez de considerar a la operación Suma, se considera a una operación binaria que sea asociativa, como lo es, como un segundo ejemplo, la operación Producto.

5.

Signo. Sea $\mbox{\it sgn}:x\mapsto\left\{\begin{array}{ll} 0 &\mbox{\rm si $x=0$ , } \\ 1 &\mbox{\rm si $x>0$ . } \end{array}\right.$. Tenemos

$$\begin{eqnarray*}\mbox{\it sgn}(0) &=& 0 \\ \mbox{\it sgn}(y+1) &=& 1 \end{eqnarray*}$$

por lo que se tiene

$$\begin{array}{lcl} \mbox{\it sgn}(0) &=& 0 \\ \mbox{\it sgn}(\mbox{\it suc}(y)) &=& \mbox{\it suc}(0) \end{array}$$

Por tanto, $\mbox{\it sgn}(y)=\mbox{\it Recu}(0,(\mbox{\it suc}\circ 0))(y)$, de lo cual se sigue directamente que $\mbox{\it sgn}\in{\cal FRP}$ pues se obtiene por el esquema de recursión de funciones en ${\cal FRP}$.

6.

Signo complementado. Sea $\overline{\mbox{\it sgn}}:x\mapsto\left\{\begin{array}{ll} 1 &\mbox{\rm si $x=0$ , } \\ 0 &\mbox{\rm si $x>0$ . } \end{array}\right.$. Tenemos

$$\begin{eqnarray*}\overline{\mbox{\it sgn}}(0) &=& 1 \\ \overline{\mbox{\it sgn}}(y+1) &=& 0 \end{eqnarray*}$$

por lo que se tiene

$$\begin{array}{lcl} \overline{\mbox{\it sgn}}(0) &=& \mbox{\i... ...overline{\mbox{\it sgn}}(\mbox{\it suc}(y)) &=& 0 \end{array}$$

Por tanto, $\overline{\mbox{\it sgn}}(y)=\mbox{\it Recu}((\mbox{\it suc}\circ 0),0)(y)$, de lo cual se sigue directamente que $\overline{\mbox{\it sgn}}\in{\cal FRP}$ pues se obtiene por el esquema de recursión de funciones en ${\cal FRP}$.

7.

Antecesor. Sea $\mbox{\it ant}:x\mapsto\left\{\begin{array}{ll} 0 &\mbox{\rm si $x=0$ , } \\ x-1 &\mbox{\rm si $x>0$ . } \end{array}\right.$. Tenemos

$$\begin{eqnarray*}\mbox{\it ant}(0) &=& 0 \\ \mbox{\it ant}(y+1) &=& y \end{eqnarray*}$$

por lo que se tiene

$$\begin{array}{lcl} \mbox{\it ant}(0) &=& 0 \\ \mbox{\it ant}(\mbox{\it suc}(y)) &=& y \end{array}$$

Por tanto, $\mbox{\it ant}(y)=\mbox{\it Recu}(0,\pi_1^1)(y)$, de lo cual se sigue directamente que $\mbox{\it ant}\in{\cal FRP}$ pues se obtiene por el esquema de recursión de funciones en ${\cal FRP}$.

8.

Diferencia acotada. Consideremos la función $\mbox{\it DA}:(x,y)\mapsto x\dot{-}y=\left\{\begin{array}{ll} x-y &\mbox{\rm si $x\geq y$ , } \\ 0 &\mbox{\rm en otro caso. } \end{array}\right.$. Ya que para cualesquiera $x,y\in I\!\!N$ se cumple

$$\begin{eqnarray*}x\dot{-}0 &=& x \\ x\dot{-}(y+1) &=& \mbox{\it ant}(x\dot{-}y) \end{eqnarray*}$$

se tiene que

$$\begin{array}{lcl} \mbox{\it DA}(x,0) &=& \mbox{\it identida... ...t suc}(y)) &=& \mbox{\it ant}(\mbox{\it DA}(x,y)) \end{array}$$

Por tanto, $\mbox{\it DA}(x,y)=\mbox{\it Recu}(\pi_1^1,h)(x,y)$, donde $\forall x,y,z: h(x,y,z)=\mbox{\it ant}\circ \pi_3^3(x,y,z)$, de lo cual se sigue directamente que $\mbox{\it DA}\in{\cal FRP}$ pues se obtiene por el esquema de recursión de funciones en ${\cal FRP}$.

9.

Distancia. Sea $\mbox{\it dist}:(x,y)\mapsto \vert x-y\vert=\left\{\begin{array}{ll} x-y &\mbox{\rm si $x\geq y$ , } \\ y-x &\mbox{\rm si $x\leq y$ . } \end{array}\right.$. Ya que $\forall x,y:\ \mbox{\it dist}(x,y)=(x\dot{-}y)+(y\dot{-}x)$ se tiene que $\mbox{\it dist}\in{\cal FRP}$.

Sea $A\subset I\!\!N^n$ un subconjunto. La función característica de A es la función $\chi_A:\mbox{\bf x}\mapsto\left\{\begin{array}{ll} 1 &\mbox{\rm si $\mbox{\bf x}\in A$ , } \\ 0 &\mbox{\rm si $\mbox{\bf x}\not\in A$ . } \end{array}\right.$. Así pues, $\chi_A$ hace las veces de un oráculo que para cada $\mbox{\bf x}\in I\!\!N^n$ decide si acaso $\mbox{\bf x}\in A$. El conjunto $A\subset I\!\!N^n$ se dice ser recursivo primitivo, y abusando de la notación escribiremos $A\in{\cal FRP}$, si su función característica lo es, es decir, si $\chi_A\in{\cal FRP}$. Una relación de aridad n se dice ser recursiva primitiva, si ella, vista como un subconjunto de $I\!\!N^n$, lo es.

Veamos algunos ejemplos de conjuntos en ${\cal FRP}$.

1.

``Mayor que''. Para cualesquiera dos $x,y\in I\!\!N$ se tiene

$$x>y\ \ \Leftrightarrow\ \ \mbox{\it sgn}(x\dot{-}y)=1,$$

por tanto $\chi_{(>)}=\mbox{\it sgn}\circ\mbox{\it DA}$ de donde se sigue que la relación ``>'' es, en efecto, recursiva primitiva.

2.

Igualdad. Para cualesquiera dos $x,y\in I\!\!N$ se tiene

$$x=y\ \ \Leftrightarrow\ \ \vert x-y\vert=0,$$

por tanto $\chi_{(=)}=\overline{\mbox{\it sgn}}\circ\mbox{\it dist}$ de donde se sigue que la relación ``='' es, en efecto, recursiva primitiva.

Denotemos por ${\cal FRP}_n$ a la clase de funciones recursivas primitivas cuyo dominio es $I\!\!N^n$.

Proposición 1.2   La clase de conjuntos recursivos primitivos en $I\!\!N^n$, que continuando con el abuso de la notación denotaremos como ${\cal FRP}_n$, forma un álgebra de conjuntos, es decir,

$$\begin{eqnarray*}& & \emptyset\in{\cal FRP}_n \\ A\in{\cal FRP}_n &\Rightarrow... ...\cap B\in{\cal FRP}_n \mbox{\rm y } A\cup B\in{\cal FRP}_n. \\ \end{eqnarray*}$$

En efecto, basta considerar las siguientes identidades:

$$\begin{array}{lcl} \chi_{\emptyset} &=& \mbox{\it Cero}\circ... ...B} &=& \left(1\dot{-}\chi_{(A^c\cap B^c)}\right). \end{array}$$

Si $A\in I\!\!N^n$ es un conjunto y $z\in I\!\!N$, la proyección de A acotada por z, en sus (n-1) primeras coordenadas, es el conjunto

$$\exists_{\leq z} A=\{\mbox{\bf x}\in I\!\!N^{n-1}\vert\exists y\leq z:(\mbox{\bf x},y)\in A\}.$$

Proposición 1.3   Si $A\in{\cal FRP}_n$ entonces para cualquier $z\in I\!\!N$ se tiene que $\exists_{\leq z} A\in{\cal FRP}_{n-1}$.

En efecto, esto es evidente de la relación válida $\forall \mbox{\bf x}\in I\!\!N^{n-1}$:

$$\mbox{\bf x}\in\exists_{\leq z} A\ \ \Leftrightarrow\ \ \mbox{\it sgn}\left(\sum_{y=0}^z\chi_A(\mbox{\bf x},y)\right)=1.$$

Podemos ver ahora esquemas de composición bajo los cuales es cerrada la clase ${\cal FRP}$.

1.

Funciones definidas por dos condiciones. Si $f_1,f_0\in{\cal FRP}$ y $A\in{\cal FRP}$ entonces la función

$$f:\mbox{\bf x}\mapsto \left\{\begin{array}{ll} f_0(\mbox{\bf... ...f x}) &\mbox{\rm si $\mbox{\bf x}\in A$. } \end{array}\right.$$

es recursiva primitiva. En efecto, se tiene que $\forall\mbox{\bf x}$: $f(\mbox{\bf x})=f_1(\mbox{\bf x})\cdot\chi_A(\mbox{\bf x})+f_0(\mbox{\bf x})\cdot\left(1\dot{-}\chi_A(\mbox{\bf x})\right)$.

2.

Minimización acotada. La minimización acotada de cualquier función recursiva primitiva es, a su vez, recursiva primitiva. En otras palabras, la clase ${\cal FRP}$ es cerrada bajo el esquema de composisción $\mbox{\it MiAc}$,

$$f\in{\cal FRP}\ \ \Rightarrow\ \ \mbox{\it MiAc}(f)\in{\cal FRP}.$$

En efecto, para todo $\mbox{\bf x}$ tenemos que para cualquier y el valor de $\mbox{\it MiAc}(f)(\mbox{\bf x},y)$ coincidirá con el valor y, si no se ha encontrado un valor que anule a $y_1\mapsto f(\mbox{\bf x},y_1)$ con $0\leq y_1\leq y$, o bien coincidirá con el valor en el antecesor, y-1, en otro caso. Así pues, tendremos

$$\begin{array}{lcl} \mbox{\it MiAc}(f)(\mbox{\bf x},y) &=& 0 ... ...+1 &\mbox{\rm en otro caso. } \end{array}\right. \end{array}$$

Como todas las funciones y todas las relaciones involucradas son recursivas primitivas tenemos que $\mbox{\it MiAc}(f)\in{\cal FRP}.$

Continuando con nuestra lista de funciones y de relaciones recursivas primitivas, presentamos a las siguientes:

1.

Divisibilidad. Escribamos x|y para indicar que existe $z\leq x$ tal que x=zy, y, en tal caso, se dice que x es divisible entre y. Tenemos pues,

$$x\vert y\ \ \Leftrightarrow\ \ \exists z\leq x:x=zy.$$

Consecuentemente, ``|'' es una relación recursiva primitiva.

2.

División. Sea $\mbox{\tt div}:(x,y)\mapsto \left\{\begin{array}{ll} \lfloor\frac{x}{y}\rfloor &\mbox{\rm si $y\not=0$ , } \\ 0 &\mbox{\rm si $y=0$ . } \end{array}\right.$. Si consideramos la función $f:(x,y,z)\mapsto x\dot{-}yz$, la cual es recursiva primitiva, tenemos que $\mbox{\tt div}(x,y)=\mbox{\it MiAc}(f)(x,y)$ siempre que $y\not=0$. Se sigue que div es recursiva primitiva.

3.

Módulo. $\mbox{\tt mod}:(x,y)\mapsto x\dot{-}y\cdot\mbox{\tt div}(x,y)$ es recursiva primitiva.

4.

Primos. Un número es compuesto, $x\in\mbox{\it Primos}^c$, si $\exists y\leq x:\left(y\not=1\right)\land \left(y\not=x\right)\land \left(x\vert y\right)$. Por tanto la propiedad de ser compuesto es recursiva primitiva. La propiedad de ser primo es también recursiva primitiva, como complemento de ésa.

5.

Lista de primos. Según vimos en la demostración del teorema de Euclides acerca de la infinidad de los números primos, el (n+1)-ésimo primo p_n+1 excede a p_n pero no excede al número $q_n=\prod_{i=0}^np_i+1$. Así pues, la lista de primos se puede construir con el esquema siguiente:

$$\begin{array}{lcl} p_0 &=& 2 \\ p_{n+1} &=& \mathop{\rm Mi... ...+1\right)\land\left(y\in\mbox{\it Primos}\right)\} \end{array}$$

por tanto la lista de primos se construye de manera recursiva primitiva.

De los ejemplos mostrados, el lector podrá ver que muchas funciones de interés en aritmética son recursivas primitivas. Entre éstas, sin entrar en demostraciones, tan solo mencionamos a los siguientes: el sacar el exponente de un primo en la descomposición en primos de un entero, el sacar la lista de exponentes no-nulos en la descomposición en primos de un entero, el decidir si dos enteros son primos relativos, la función de Euler (que cuenta el número de primos relativos de un número dado menores que él), el símbolo de Legendre, el cual decide para dos primos relativos x,m si acaso x es un residuo cuadrático de m (es decir, $\exists x: x^2\equiv a\mbox{ mod }m$), etc.

Siguiente: Dos esquemas de reiteración Un nivel arriba: Funciones recursivas primitivas Anterior: Funciones recursivas primitivas