Función recursiva primitiva

Una función (con valores vectoriales) ^{[ 5 ]}${\displaystyle f:\mathbb {N} ^{m}\to \mathbb {N} ^{n}}$es recursivo primitivo si se puede escribir como

${\displaystyle f(x_{1},\dots ,x_{m})=(f_{1}(x_{1},\dots ,x_{m}),\dots ,f_{n}(x_{1},\dots ,x_{m}))}$

donde cada componente${\displaystyle f_{i}:\mathbb {N} ^{m}\to \mathbb {N} }$es una función recursiva primitiva (con valores escalares). ^{[ 6 ]}

Una definición de la función biaria${\displaystyle \operatorname {Add} }$Para calcular la suma de sus argumentos, se puede obtener utilizando el operador de recursión primitivo.${\displaystyle \rho }$. Para ello, se utilizan las conocidas ecuaciones

${\displaystyle {\begin{aligned}0+y&=y,\\S(x)+y&=S(x+y)\end{aligned}}}$

están "reformulados en terminología de funciones recursivas primitivas": En la definición de${\displaystyle \rho (g,h)}$La primera ecuación sugiere elegir${\displaystyle g=P_{1}^{1}}$para obtener${\displaystyle \operatorname {Add} (0,y)=g(y)=y}$; la segunda ecuación sugiere elegir${\displaystyle h=S\circ P_{2}^{3}}$para obtener${\displaystyle \operatorname {Add} (S(x),y)=h(x,\operatorname {Add} (x,y),y)=(S\circ P_{2}^{3})(x,\operatorname {Add} (x,y),y)=S(\operatorname {Add} (x,y))}$Por lo tanto, la función de suma se puede definir como${\displaystyle \operatorname {Add} =\rho (P_{1}^{1},S\circ P_{2}^{3})}$. Como ejemplo de cálculo,

${\displaystyle {\begin{aligned}\operatorname {Add} (1,7)&=\rho (P_{1}^{1},S\circ P_{2}^{3})(S(0),7)&&{\text{ by Def. }}\operatorname {Add} ,S\\&=(S\circ P_{2}^{3})(0,\operatorname {Add} (0,7),7)&&{\text{ by case }}\rho (g,h)(S(...),...)\\&=S(\operatorname {Add} (0,7))&&{\text{ by Def. }}\circ ,P_{2}^{3}\\&=S(\rho (P_{1}^{1},S\circ P_{2}^{3})(0,7))&&{\text{ by Def. }}\operatorname {Add} \\&=S(P_{1}^{1}(7))&&{\text{ by case }}\rho (g,h)(0,...)\\&=S(7)&&{\text{ by Def. }}P_{1}^{1}\\&=8&&{\text{ by Def. }}S.\\\end{aligned}}}$

Dado${\displaystyle \operatorname {Add} }$, la función 1-aria${\displaystyle \operatorname {Add} \circ (P_{1}^{1},P_{1}^{1})}$duplica su argumento,${\displaystyle (\operatorname {Add} \circ (P_{1}^{1},P_{1}^{1}))(x)=\operatorname {Add} (x,x)=x+x.}$

De manera similar a la suma, la multiplicación se puede definir mediante${\displaystyle \operatorname {Mul} =\rho (C_{0}^{1},\operatorname {Add} \circ (P_{2}^{3},P_{3}^{3}))}$Esto reproduce las conocidas ecuaciones de multiplicación:

${\displaystyle {\begin{aligned}\operatorname {Mul} (0,y)&=\rho (C_{0}^{1},\operatorname {Add} \circ (P_{2}^{3},P_{3}^{3}))(0,y)&&{\text{ by Def. }}\operatorname {Mul} \\&=C_{0}^{1}(y)&&{\text{ by case }}\rho (g,h)(0,...)\\&=0&&{\text{ by Def. }}C_{0}^{1}.\end{aligned}}}$

y

${\displaystyle {\begin{aligned}\operatorname {Mul} (S(x),y)&=\rho (C_{0}^{1},\operatorname {Add} \circ (P_{2}^{3},P_{3}^{3}))(S(x),y)&&{\text{ by Def. }}\operatorname {Mul} \\&=(\operatorname {Add} \circ (P_{2}^{3},P_{3}^{3}))(x,\operatorname {Mul} (x,y),y)&&{\text{ by case }}\rho (g,h)(S(...),...)\\&=\operatorname {Add} (\operatorname {Mul} (x,y),y)&&{\text{ by Def. }}\circ ,P_{2}^{3},P_{3}^{3}\\&=\operatorname {Mul} (x,y)+y&&{\text{ by property of }}\operatorname {Add} .\end{aligned}}}$

La función predecesora actúa como el "opuesto" de la función sucesora y se define recursivamente mediante las reglas.${\displaystyle \operatorname {Pred} (0)=0}$y${\displaystyle \operatorname {Pred} (S(n))=n}$. Una definición recursiva primitiva es${\displaystyle \operatorname {Pred} =\rho (C_{0}^{0},P_{1}^{2})}$. Como ejemplo de cálculo,

${\displaystyle {\begin{aligned}\operatorname {Pred} (8)&=\rho (C_{0}^{0},P_{1}^{2})(S(7))&&{\text{ by Def. }}\operatorname {Pred} ,S\\&=P_{1}^{2}(7,\operatorname {Pred} (7))&&{\text{ by case }}\rho (g,h)(S(...),...)\\&=7&&{\text{ by Def. }}P_{1}^{2}.\end{aligned}}}$

La función de resta limitada (también llamada " monus " y denotada "${\displaystyle \mathbin {\dot {-}} }$") se puede definir a partir de la función predecesora. Satisface las ecuaciones

${\displaystyle {\begin{aligned}y\mathbin {\dot {-}} 0&=y,\\y\mathbin {\dot {-}} S(x)&=\operatorname {Pred} (y\mathbin {\dot {-}} x).\end{aligned}}}$

Dado que la recursión se ejecuta sobre el segundo argumento, comenzamos con una definición recursiva primitiva de la resta inversa,${\displaystyle \operatorname {RSub} (y,x)=x\mathbin {\dot {-}} y}$Su recursión se ejecuta entonces sobre el primer argumento, por lo que su definición recursiva primitiva puede obtenerse, de forma similar a la suma, como${\displaystyle \operatorname {RSub} =\rho (P_{1}^{1},\operatorname {Pred} \circ P_{2}^{3})}$Para eliminar el orden invertido de los argumentos, defina${\displaystyle \operatorname {Sub} =\operatorname {RSub} \circ (P_{2}^{2},P_{1}^{2})}$. Como ejemplo de cálculo,

${\displaystyle {\begin{aligned}\operatorname {Sub} (8,1)&=(\operatorname {RSub} \circ (P_{2}^{2},P_{1}^{2}))(8,1)&&{\text{ by Def. }}\operatorname {Sub} \\&=\operatorname {RSub} (1,8)&&{\text{ by Def. }}\circ ,P_{2}^{2},P_{1}^{2}\\&=\rho (P_{1}^{1},\operatorname {Pred} \circ P_{2}^{3})(S(0),8)&&{\text{ by Def. }}\operatorname {RSub} ,S\\&=(\operatorname {Pred} \circ P_{2}^{3})(0,\operatorname {RSub} (0,8),8)&&{\text{ by case }}\rho (g,h)(S(...),...)\\&=\operatorname {Pred} (\operatorname {RSub} (0,8))&&{\text{ by Def. }}\circ ,P_{2}^{3}\\&=\operatorname {Pred} (\rho (P_{1}^{1},\operatorname {Pred} \circ P_{2}^{3})(0,8))&&{\text{ by Def. }}\operatorname {RSub} \\&=\operatorname {Pred} (P_{1}^{1}(8))&&{\text{ by case }}\rho (g,h)(0,...)\\&=\operatorname {Pred} (8)&&{\text{ by Def. }}P_{1}^{1}\\&=7&&{\text{ by property of }}\operatorname {Pred} .\end{aligned}}}$

En algunos entornos, es natural considerar funciones recursivas primitivas que toman como entradas tuplas que mezclan números con valores de verdad (es decir,${\displaystyle t}$porque es cierto y${\displaystyle f}$para falso), o que produzcan valores de verdad como salidas. ^{[ 8 ]} Esto se puede lograr identificando los valores de verdad con números de cualquier manera fija. Por ejemplo, es común identificar el valor de verdad${\displaystyle t}$con el número${\displaystyle 1}$y el valor de verdad${\displaystyle f}$con el número${\displaystyle 0}$. Una vez realizada esta identificación, la función característica de un conjunto${\displaystyle A}$, que siempre regresa${\displaystyle 1}$o${\displaystyle 0}$puede considerarse como un predicado que indica si un número está en el conjunto${\displaystyle A}$En el resto de este artículo, se asumirá dicha identificación de predicados con funciones numéricas.

Como ejemplo de un predicado recursivo primitivo, la función 1-aria${\displaystyle \operatorname {IsZero} }$se definirá de tal manera que${\displaystyle \operatorname {IsZero} (x)=1}$si${\displaystyle x=0}$, y${\displaystyle \operatorname {IsZero} (x)=0}$de lo contrario. Esto se puede lograr definiendo${\displaystyle \operatorname {IsZero} =\rho (C_{1}^{0},C_{0}^{2})}$. Entonces${\displaystyle \operatorname {IsZero} (0)=\rho (C_{1}^{0},C_{0}^{2})(0)=C_{1}^{0}()=1}$y por ejemplo${\displaystyle \operatorname {IsZero} (8)=\rho (C_{1}^{0},C_{0}^{2})(S(7))=C_{0}^{2}(7,\operatorname {IsZero} (7))=0}$.

Utilizando la propiedad${\displaystyle x\leq y\iff x\mathbin {\dot {-}} y=0}$, la función biaria${\displaystyle \operatorname {Leq} }$puede definirse por${\displaystyle \operatorname {Leq} =\operatorname {IsZero} \circ \operatorname {Sub} }$. Entonces${\displaystyle \operatorname {Leq} (x,y)=1}$si${\displaystyle x\leq y}$, y${\displaystyle \operatorname {Leq} (x,y)=0}$de lo contrario. Como ejemplo de cálculo,

${\displaystyle {\begin{aligned}\operatorname {Leq} (8,3)&=\operatorname {IsZero} (\operatorname {Sub} (8,3))&&{\text{ by Def. }}\operatorname {Leq} \\&=\operatorname {IsZero} (5)&&{\text{ by property of }}\operatorname {Sub} \\&=0&&{\text{ by property of }}\operatorname {IsZero} \\\end{aligned}}}$

Una vez una definición de${\displaystyle \operatorname {Leq} }$Se obtiene el predicado recíproco, que puede definirse como${\displaystyle \operatorname {Geq} =\operatorname {Leq} \circ (P_{2}^{2},P_{1}^{2})}$. Entonces,${\displaystyle \operatorname {Geq} (x,y)=\operatorname {Leq} (y,x)}$es verdadero (más precisamente: tiene valor 1) si y solo si${\displaystyle x\geq y}$.

El operador if-then-else de 3 niveles conocido en los lenguajes de programación se puede definir mediante${\displaystyle \operatorname {If} =\rho (P_{2}^{2},P_{3}^{4})}$. Entonces, para arbitrario${\displaystyle x}$,

${\displaystyle {\begin{aligned}\operatorname {If} (S(x),y,z)&=\rho (P_{2}^{2},P_{3}^{4})(S(x),y,z)&&{\text{ by Def. }}\operatorname {If} \\&=P_{3}^{4}(x,\operatorname {If} (x,y,z),y,z)&&{\text{ by case }}\rho (S(...),...)\\&=y&&{\text{ by Def. }}P_{3}^{4}\end{aligned}}}$

y

${\displaystyle {\begin{aligned}\operatorname {If} (0,y,z)&=\rho (P_{2}^{2},P_{3}^{4})(0,y,z)&&{\text{ by Def. }}\operatorname {If} \\&=P_{2}^{2}(y,z)&&{\text{ by case }}\rho (0,...)\\&=z&&{\text{ by Def. }}P_{2}^{2}.\end{aligned}}}$

Eso es,${\displaystyle \operatorname {If} (x,y,z)}$devuelve la parte entonces (${\displaystyle y}$) si la parte if (${\displaystyle x}$) es verdadero, y la otra parte (${\displaystyle z}$) de lo contrario.

Basado en el${\displaystyle \operatorname {If} }$función, es fácil definir conectores lógicos. Por ejemplo, definiendo${\displaystyle \operatorname {And} =\operatorname {If} \circ (P_{1}^{2},P_{2}^{2},C_{0}^{2})}$, uno obtiene${\displaystyle \operatorname {And} (x,y)=\operatorname {If} (x,y,0)}$, eso es,${\displaystyle \operatorname {And} (x,y)}$es cierto si y solo si ambos${\displaystyle x}$y${\displaystyle y}$son verdaderos ( conjunción lógica de${\displaystyle x}$y${\displaystyle y}$).

Similarmente,${\displaystyle \operatorname {Or} =\operatorname {If} \circ (P_{1}^{2},C_{1}^{2},P_{2}^{2})}$y${\displaystyle \operatorname {Not} =\operatorname {If} \circ (P_{1}^{1},C_{0}^{1},C_{1}^{1})}$conducir a definiciones apropiadas de disyunción y negación :${\displaystyle \operatorname {Or} (x,y)=\operatorname {If} (x,1,y)}$y${\displaystyle \operatorname {Not} (x)=\operatorname {If} (x,0,1)}$.

Utilizando las funciones anteriores${\displaystyle \operatorname {Leq} }$,${\displaystyle \operatorname {Geq} }$y${\displaystyle \operatorname {And} }$, la definición${\displaystyle \operatorname {Eq} =\operatorname {And} \circ (\operatorname {Leq} ,\operatorname {Geq} )}$implementa el predicado de igualdad. De hecho,${\displaystyle \operatorname {Eq} (x,y)=\operatorname {And} (\operatorname {Leq} (x,y),\operatorname {Geq} (x,y))}$es cierto si y solo si${\displaystyle x}$igual${\displaystyle y}$.

De manera similar, la definición${\displaystyle \operatorname {Lt} =\operatorname {Not} \circ \operatorname {Geq} }$implementa el predicado "menor que" y${\displaystyle \operatorname {Gt} =\operatorname {Not} \circ \operatorname {Leq} }$implementa "mayor que".

La exponenciación y la prueba de primalidad son recursivas primitivas. Dadas las funciones recursivas primitivas${\displaystyle e}$,${\displaystyle f}$,${\displaystyle g}$, y${\displaystyle h}$, una función que devuelve el valor de${\displaystyle g}$cuando${\displaystyle e\leq f}$y el valor de${\displaystyle h}$De lo contrario, es recursivo primitivo.

Mediante la numeración de Gödel , las funciones recursivas primitivas pueden extenderse para operar con otros objetos, como números enteros y racionales . Si los números enteros se codifican con números de Gödel de forma estándar, las operaciones aritméticas, incluyendo la suma, la resta y la multiplicación, son recursivas primitivas. Del mismo modo, si los números racionales se representan con números de Gödel, las operaciones de campo también son recursivas primitivas.

Los siguientes ejemplos y definiciones provienen de Kleene 1974 , pp. 222–231 . Muchos aparecen con demostraciones. La mayoría también aparecen con nombres similares, ya sea como demostraciones o como ejemplos, en Boolos, Burgess y Jeffrey 2002 , pp. 63–70, donde añaden el logaritmo lo(x, y) o lg(x, y) según la derivación exacta.  

En lo que sigue, la marca " ' ", por ejemplo a', es la marca primitiva que significa "el sucesor de", generalmente considerada como " +1", por ejemplo a +1 = _def a'. Las funciones 16–20 y #G son de particular interés con respecto a la conversión de predicados recursivos primitivos a, y la extracción de los mismos de, su forma "aritmética" expresada como números de Gödel .

1. Suma: a+b
2. Multiplicación: a × b
3. Exponenciación: a ^b
4. Factorial a!  : 0! = 1, a'! = a!×a'
5. pred(a): (Predecesor o decremento): Si a > 0 entonces a−1, de lo contrario 0
6. Resta propia a ∸ b: Si a ≥ b, entonces a−b; de lo contrario, 0.
7. Mínimo(a ₁ , ... a _n )
8. Máximo(a ₁ , ... a _n )
9. Diferencia absoluta: | a−b | = _def (a ∸ b) + (b ∸ a)
10. ~sg(a): NOT[signum(a)]: Si a=0 entonces 1 sino 0
11. sg(a): signum(a): Si a=0 entonces 0 sino 1
12. a | b: (a divide a b): Si b = k × a para algún k, entonces 0; de lo contrario, 1.
13. Resto(a, b): el sobrante si b no divide a de forma exacta. También llamado MOD(a, b).
14. a = b: sg | a − b | (La convención de Kleene era representar verdadero con 0 y falso con 1; actualmente, especialmente en informática, la convención más común es la inversa, es decir, representar verdadero con 1 y falso con 0, lo que equivale a cambiar sg por ~sg aquí y en el siguiente elemento).
15. a < b: sg( a' ∸ b )
16. Pr(a): a es un número primo Pr(a) = _def a>1 & NOT(Existe c) _1<c<a [ c|a ]
17. p _i : el i+1º número primo
18. (a) _i : exponente de p _i en a: el único x tal que p _i ^x |a & NOT(p _i ^x' |a)
19. lh(a): la "longitud" o número de exponentes no nulos en un
20. lo(a, b): (logaritmo de a en base b): Si a, b > 1, entonces el mayor x tal que b ^x | a, de lo contrario 0

En lo que sigue, la abreviatura x = _def x ₁ , ... x _n ; se pueden aplicar subíndices si el significado lo requiere.

• #A: Una función φ definible explícitamente a partir de funciones Ψ y constantes q ₁ , ... q _n es recursiva primitiva en Ψ.
• #B: La suma finita Σ _y<z ψ( x , y) y el producto Π _y<z ψ( x , y) son recursivos primitivos en ψ.
• #C: Un predicado P obtenido al sustituir las funciones χ ₁ ,..., χ _m por las variables respectivas de un predicado Q es recursivo primitivo en χ ₁ ,..., χ _m , Q.
• #D: Los siguientes predicados son recursivos primitivos en Q y R:

• NO_Q( x ) .
• Q O R: Q( x ) VR( x ),
• Q Y R: Q( x ) & R( x ),
• Q IMPLICA R: Q( x ) → R( x )
• Q es equivalente a R: Q( x ) ≡ R( x )

• #E: Los siguientes predicados son recursivos primitivos en el predicado R:

• (Ey) _y<z R( x , y) donde (Ey) _y<z denota "existe al menos un y que es menor que z tal que"
• (y) _y<z R( x , y) donde (y) _y<z denota "para todo y menor que z es cierto que"
• μy _y<z R( x , y). El operador μy _y<z R( x , y) es una forma acotada del llamado operador de minimización o mu : se define como "el menor valor de y menor que z tal que R( x , y) es verdadero; o z si no existe tal valor".

• #F: Definición por casos: La función definida así, donde Q ₁ , ..., Q _{m son} predicados mutuamente excluyentes (o "ψ( x ) tendrá el valor dado por la primera cláusula que se aplique), es recursiva primitiva en φ ₁ , ..., Q ₁ , ... Q _m :

φ( x ) =

• φ ₁ ( x ) si Q ₁ ( x ) es verdadero,
• . . . . . . . . . . . . . . . . . . .
• φ _m ( x ) si Q _m ( x ) es verdadero
• φ _m+1 ( x ) en caso contrario

• #G: Si φ satisface la ecuación:

φ(y, x ) = χ(y, COURSE-φ(y; x ₂ , ... x _n ), x ₂ , ... x _n entonces φ es recursiva primitiva en χ. El valor COURSE-φ(y; x _{2 a n} ) de la función de curso de valores codifica la secuencia de valores φ(0, x _{2 a n} ), ..., φ(y-1, x _{2 a n} ) de la función original.

En lugar de${\displaystyle C_{n}^{k}}$Las definiciones alternativas utilizan solo una función cero 0-aria${\displaystyle C_{0}^{0}}$como una función primitiva que siempre devuelve cero, y construir las funciones constantes a partir de la función cero, la función sucesora y el operador de composición.

Robinson ^{[ 10 ]} consideró varias restricciones de la regla de recursión. Una de ellas es la llamada regla de iteración, donde la función h no tiene acceso a los parámetros x _i (en este caso, podemos suponer sin pérdida de generalidad que la función g es simplemente la identidad, ya que el caso general se puede obtener por sustitución):

${\displaystyle {\begin{aligned}f(0,x)&=x,\\f(S(y),x)&=h(y,f(y,x)).\end{aligned}}}$

Demostró que la clase de todas las funciones recursivas primitivas aún puede obtenerse de esta manera.

Otra restricción considerada por Robinson ^{[ 10 ]} es la recursión pura , donde h no tiene acceso a la variable de inducción y :

${\displaystyle {\begin{aligned}f(0,x_{1},\ldots ,x_{k})&=g(x_{1},\ldots ,x_{k}),\\f(S(y),x_{1},\ldots ,x_{k})&=h(f(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k}).\end{aligned}}}$

Gladstone ^{[ 11 ]} demostró que esta regla es suficiente para generar todas las funciones recursivas primitivas. Gladstone ^{[ 12 ]} mejoró esto de modo que incluso la combinación de estas dos restricciones, es decir, la regla de iteración pura que se muestra a continuación, es suficiente:

${\displaystyle {\begin{aligned}f(0,x)&=x,\\f(S(y),x)&=h(f(y,x)).\end{aligned}}}$

Son posibles mejoras adicionales: Severin ^{[ 13 ]} demuestra que incluso la regla de iteración pura sin parámetros , a saber,

${\displaystyle {\begin{aligned}f(0)&=0,\\f(S(y))&=h(f(y)),\end{aligned}}}$

Basta con generar todas las funciones recursivas primitivas unarias si extendemos el conjunto de funciones iniciales con la resta truncada x ∸ y . Obtenemos todas las funciones recursivas primitivas si además incluimos + como función inicial.

Algunas formas adicionales de recursión también definen funciones que, de hecho, son recursivas primitivas. Las definiciones en estas formas pueden ser más fáciles de encontrar o más naturales para leer o escribir. La recursión de curso de valores define funciones recursivas primitivas. Algunas formas de recursión mutua también definen funciones recursivas primitivas.

Las funciones que se pueden programar en el lenguaje de programación LOOP son precisamente las funciones recursivas primitivas. Esto le confiere una caracterización diferente a la potencia de estas funciones. La principal limitación del lenguaje LOOP, en comparación con un lenguaje Turing-completo , es que en LOOP se especifica el número de iteraciones de cada bucle antes de que este comience a ejecutarse.

Un ejemplo de lenguaje de programación recursivo primitivo es aquel que contiene operadores aritméticos básicos (por ejemplo, + y −, o suma y resta), condicionales y comparaciones (SI-ENTONCES, IGUAL, MENOR QUE) y bucles acotados, como el bucle for básico , donde existe un límite superior conocido o calculable para todos los bucles (PARA i DESDE 1 HASTA n, sin que ni i ni n sean modificables por el cuerpo del bucle). En un lenguaje recursivo primitivo no se admiten estructuras de control de mayor generalidad, como bucles while o SI-ENTONCES más GOTO .

El lenguaje LOOP , presentado en un artículo de 1967 por Albert R. Meyer y Dennis M. Ritchie , ^{[ 14 ]} es un ejemplo de este tipo de lenguaje. Su capacidad de cálculo coincide con la de las funciones recursivas primitivas. Una variante del lenguaje LOOP es BlooP de Douglas Hofstadter en Gödel, Escher, Bach . La adición de bucles ilimitados (WHILE, GOTO) convierte al lenguaje en recursivo general y Turing-completo , al igual que todos los lenguajes de programación del mundo real.

La definición de funciones recursivas primitivas implica que su cálculo se detiene en cada entrada (tras un número finito de pasos). Por otro lado, el problema de la parada es indecidible para funciones recursivas generales.