Función recursiva primitiva

Función computable con bucles acotados

En teoría de la computabilidad , una función recursiva primitiva es, en términos generales, una función que puede ser calculada por un programa informático cuyos bucles son todos bucles "for" (es decir, se fija un límite superior del número de iteraciones de cada bucle antes de entrar en el bucle). Las funciones recursivas primitivas forman un subconjunto estricto de aquellas funciones recursivas generales que también son funciones totales .

La importancia de las funciones recursivas primitivas radica en el hecho de que la mayoría de las funciones computables que se estudian en la teoría de números (y más generalmente en matemáticas) son recursivas primitivas. Por ejemplo, la suma y la división , la función factorial y exponencial y la función que devuelve el n -ésimo primo son todas recursivas primitivas. ^[1] De hecho, para demostrar que una función computable es recursiva primitiva, basta con demostrar que su complejidad temporal está acotada por encima por una función recursiva primitiva del tamaño de entrada. ^[2] Por lo tanto, no es particularmente fácil idear una función computable que no sea recursiva primitiva; algunos ejemplos se muestran en la sección § Limitaciones a continuación.

El conjunto de funciones recursivas primitivas se conoce como PR en la teoría de la complejidad computacional .

Definición

Una función recursiva primitiva toma un número fijo de argumentos, cada uno de ellos un número natural (entero no negativo: {0, 1, 2, ...}), y devuelve un número natural. Si toma n argumentos, se denomina n - aria .

Las funciones recursivas primitivas básicas están dadas por estos axiomas :

1. Funciones constantes ${\displaystyle C_{n}^{k}}$ : Para cada número natural y cada , la función constante k -aria, definida por , es recursiva primitiva. ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle C_{n}^{k}(x_{1},\ldots ,x_{k})\ {\stackrel {\mathrm {def} }{=}}\ n}$
2. Función sucesora : La función sucesora 1-aria S , que devuelve el sucesor de su argumento (ver postulados de Peano ), es decir, , es recursiva primitiva. ${\displaystyle S(x)\ {\stackrel {\mathrm {def} }{=}}\ x+1}$
3. Funciones de proyección : Para todos los números naturales tales que , la función k -aria definida por es recursiva primitiva. ${\displaystyle P_{i}^{k}}$ ${\displaystyle i,k}$ ${\displaystyle 1\leq i\leq k}$ ${\displaystyle P_{i}^{k}(x_{1},\ldots ,x_{k})\ {\stackrel {\mathrm {def} }{=}}\ x_{i}}$

Se pueden obtener funciones recursivas primitivas más complejas aplicando las operaciones dadas por estos axiomas:

4. Operador de composición (también llamado operador de sustitución ): Dada una función m -aria y m funciones k -arias : Para , se obtiene la composición de funciones ordinarias . ${\displaystyle \circ \,}$ ${\displaystyle h(x_{1},\ldots ,x_{m})\,}$ ${\displaystyle g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k})}$ $${\displaystyle h\circ (g_{1},\ldots ,g_{m})\ {\stackrel {\mathrm {def} }{=}}\ f,\quad {\text{where}}\quad f(x_{1},\ldots ,x_{k})=h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k})).}$$ ${\displaystyle m=1}$ ${\displaystyle h\circ g_{1}}$
5. Operador de recursión primitiva : Dada la función k -aria y la función ( k  + 2)-aria : ${\displaystyle \rho }$ ${\displaystyle g(x_{1},\ldots ,x_{k})\,}$ ${\displaystyle h(y,z,x_{1},\ldots ,x_{k})\,}$ $${\displaystyle {\begin{aligned}\rho (g,h)&\ {\stackrel {\mathrm {def} }{=}}\ f,\quad {\text{where the }}(k+1){\text{-ary function }}f{\text{ is defined by}}\\f(0,x_{1},\ldots ,x_{k})&=g(x_{1},\ldots ,x_{k})\\f(S(y),x_{1},\ldots ,x_{k})&=h(y,f(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k}).\end{aligned}}}$$

   Interpretación:

   La función actúa como un bucle for desde hasta el valor de su primer argumento. El resto de los argumentos para , denotados aquí con , son un conjunto de condiciones iniciales para el bucle for que puede utilizar durante los cálculos pero que son inmutables para él. Las funciones y en el lado derecho de las ecuaciones que definen representan el cuerpo del bucle, que realiza los cálculos. La función se utiliza solo una vez para realizar los cálculos iniciales. Los cálculos para los pasos posteriores del bucle se realizan mediante . El primer parámetro de se alimenta con el valor "actual" del índice del bucle for. El segundo parámetro de se alimenta con el resultado de los cálculos anteriores del bucle for, de los pasos anteriores. El resto de los parámetros para son las condiciones iniciales inmutables para el bucle for mencionado anteriormente. Pueden ser utilizados por para realizar cálculos, pero no serán alterados por . ${\displaystyle f}$ ${\displaystyle 0}$ ${\displaystyle f}$ ${\displaystyle x_{1},\ldots ,x_{k}}$ ${\displaystyle g}$ ${\displaystyle h}$ ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle h}$ ${\displaystyle h}$ ${\displaystyle h}$ ${\displaystyle h}$ ${\displaystyle h}$ ${\displaystyle h}$

Las funciones recursivas primitivas son las funciones básicas y las que se obtienen a partir de las funciones básicas aplicando estas operaciones un número finito de veces.

Ejemplos

• ${\displaystyle C_{0}^{1}}$es una función 1-aria que retorna para cada entrada: . ${\displaystyle 0}$ ${\displaystyle C_{0}^{1}(x)=0}$
• ${\displaystyle C_{1}^{1}}$es una función 1-aria que retorna para cada entrada: . ${\displaystyle 1}$ ${\displaystyle C_{1}^{1}(x)=1}$
• ${\displaystyle C_{3}^{0}}$es una función 0-aria, es decir, una constante: . ${\displaystyle C_{3}^{0}=3}$
• ${\displaystyle P_{1}^{1}}$es la función identidad sobre los números naturales: . ${\displaystyle P_{1}^{1}(x)=x}$
• ${\displaystyle P_{1}^{2}}$y es la proyección izquierda y derecha sobre pares de números naturales, respectivamente: y . ${\displaystyle P_{2}^{2}}$ ${\displaystyle P_{1}^{2}(x,y)=x}$ ${\displaystyle P_{2}^{2}(x,y)=y}$
• ${\displaystyle S\circ S}$es una función 1-aria que suma 2 a su entrada, . ${\displaystyle (S\circ S)(x)=x+2}$
• ${\displaystyle S\circ C_{0}^{1}}$es una función 1-aria que devuelve 1 para cada entrada: . Es decir, y son la misma función: . De manera similar, cada se puede expresar como una composición de un número apropiado de y . Además, es igual a , ya que . Por estas razones, algunos autores ^[3] definen solo para y . ${\displaystyle (S\circ C_{0}^{1})(x)=S(C_{0}^{1}(x))=S(0)=1}$ ${\displaystyle S\circ C_{0}^{1}}$ ${\displaystyle C_{1}^{1}}$ ${\displaystyle S\circ C_{0}^{1}=C_{1}^{1}}$ ${\displaystyle C_{n}^{k}}$ ${\displaystyle S}$ ${\displaystyle C_{0}^{k}}$ ${\displaystyle C_{0}^{k}}$ ${\displaystyle C_{0}^{1}\circ P_{1}^{k}}$ ${\displaystyle C_{0}^{k}(x_{1},\ldots ,x_{k})=0=C_{0}^{1}(x_{1})=C_{0}^{1}(P_{1}^{k}(x_{1},\ldots ,x_{k}))=(C_{0}^{1}\circ P_{1}^{k})(x_{1},\ldots ,x_{k})}$ ${\displaystyle C_{n}^{k}}$ ${\displaystyle n=0}$ ${\displaystyle k=1}$

Suma

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

${\displaystyle {\begin{array}{rcll}0+y&=&y&{\text{ and}}\\S(x)+y&=&S(x+y)&.\\\end{array}}}$

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

${\displaystyle {\begin{array}{lll}&Add(1,7)\\=&\rho (P_{1}^{1},S\circ P_{2}^{3})\;(S(0),7)&{\text{ by Def. }}Add,S\\=&(S\circ P_{2}^{3})(0,Add(0,7),7)&{\text{ by case }}\rho (g,h)\;(S(...),...)\\=&S(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. }}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{array}}}$

Duplicación

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

Multiplicación

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

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

y

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

Predecesor

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

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

Resta truncada

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

${\displaystyle {\begin{array}{rcll}y{\stackrel {.}{-}}0&=&y&{\text{and}}\\y{\stackrel {.}{-}}S(x)&=&Pred(y{\stackrel {.}{-}}x)&.\\\end{array}}}$

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

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

Convertir predicados en funciones numéricas

En algunos entornos es natural considerar funciones recursivas primitivas que toman como entradas tuplas que mezclan números con valores de verdad (es decir, para verdadero y para falso), o que producen valores de verdad como salidas. ^[4] 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 con el número y el valor de verdad con el número . Una vez que se ha realizado esta identificación, la función característica de un conjunto , que siempre devuelve o , puede verse como un predicado que indica si un número está en el conjunto . Tal identificación de predicados con funciones numéricas se asumirá para el resto de este artículo. ${\displaystyle t}$ ${\displaystyle f}$ ${\displaystyle t}$ ${\displaystyle 1}$ ${\displaystyle f}$ ${\displaystyle 0}$ ${\displaystyle A}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle A}$

Predicado "Es cero"

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

Predicado "menor o igual"

Usando la propiedad , la función 2-aria se puede definir por . Entonces si , y , en caso contrario. Como ejemplo de cálculo, ${\displaystyle x\leq y\iff x{\stackrel {.}{-}}y=0}$ ${\displaystyle Leq}$ ${\displaystyle Leq=IsZero\circ Sub}$ ${\displaystyle Leq(x,y)=1}$ ${\displaystyle x\leq y}$ ${\displaystyle Leq(x,y)=0}$

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

Predicado "Mayor o igual"

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

Si-entonces-sino

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

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

y

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

Es decir, devuelve la parte then, , si la parte if, , es verdadera, y la parte else, , en caso contrario. ${\displaystyle {\textit {If}}(x,y,z)}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle z}$

Conectadores

A partir de la función, es fácil definir conjunciones lógicas. Por ejemplo, al definir , se obtiene , es decir, es verdadero si, y solo si , tanto y como son verdaderos ( conjunción lógica de y ). ${\displaystyle {\textit {If}}}$ ${\displaystyle And={\textit {If}}\circ (P_{1}^{2},P_{2}^{2},C_{0}^{2})}$ ${\displaystyle And(x,y)={\textit {If}}(x,y,0)}$ ${\displaystyle And(x,y)}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$

De manera similar, y conducen a definiciones apropiadas de disyunción y negación : y . ${\displaystyle Or={\textit {If}}\circ (P_{1}^{2},C_{1}^{2},P_{2}^{2})}$ ${\displaystyle Not={\textit {If}}\circ (P_{1}^{1},C_{0}^{1},C_{1}^{1})}$ ${\displaystyle Or(x,y)={\textit {If}}(x,1,y)}$ ${\displaystyle Not(x)={\textit {If}}(x,0,1)}$

Predicado de igualdad

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

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

Otras operaciones con números naturales

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

Operaciones con números enteros y racionales

Al utilizar numeraciones de Gödel , las funciones recursivas primitivas se pueden ampliar para operar sobre otros objetos, como números enteros y racionales . Si los números enteros se codifican mediante números de Gödel de manera estándar, las operaciones aritméticas, incluidas la suma, la resta y la multiplicación, son todas recursivas primitivas. De manera similar, si los racionales se representan mediante números de Gödel, las operaciones de campo son todas recursivas primitivas.

Algunas funciones recursivas primitivas comunes

Los siguientes ejemplos y definiciones son de Kleene (1952), págs. 223-231. Muchos aparecen con pruebas. La mayoría también aparecen con nombres similares, ya sea como pruebas o como ejemplos, en Boolos-Burgess-Jeffrey 2002, págs. 63-70; añaden el logaritmo lo(x, y) o lg(x, y) según la derivación exacta.

En lo sucesivo, el signo " ' ", p. ej. a', es el signo primitivo que significa "el sucesor de", que normalmente se considera "+1", p. ej. 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 su forma "aritmética" expresada como} números de Gödel y su extracción de la misma .

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 de lo contrario 0
11. sg(a): signum(a): Si a=0 entonces 0 de lo contrario 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 manera uniforme". También se llama 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 computadoras, 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 en ~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 & NO(p _i ^x' |a)
19. lh(a): la "longitud" o número de exponentes no nulos en una
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 sucesivo, la abreviatura x = _def x ₁ , ... x _n ; se podrán 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 respectivas variables 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 ) y 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 u operador mu : se define como "el menor valor de y menor que z tal que R( x , y) sea verdadero; o z si no existe tal valor".

• #F: Definición por casos: La función así definida, donde Q ₁ , ..., Q _{m son} predicados mutuamente excluyentes (o "ψ( x ) tendrá el valor dado por la primera cláusula que 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, CURSO-φ(y; x ₂ , ... x _n ), x ₂ , ... x _n entonces φ es recursivo primitivo en χ. El valor CURSO-φ(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.

Relación con funciones recursivas

La clase más amplia de funciones recursivas parciales se define mediante la introducción de un operador de búsqueda ilimitado . El uso de este operador puede dar como resultado una función parcial , es decir, una relación con como máximo un valor para cada argumento, pero no necesariamente tiene ningún valor para ningún argumento (véase dominio ). Una definición equivalente establece que una función recursiva parcial es aquella que puede ser calculada por una máquina de Turing . Una función recursiva total es una función recursiva parcial que se define para cada entrada.

Toda función recursiva primitiva es recursiva total, pero no todas las funciones recursivas totales son recursivas primitivas. La función de Ackermann A ( m , n ) es un ejemplo bien conocido de una función recursiva total (de hecho, total demostrable), que no es recursiva primitiva. Existe una caracterización de las funciones recursivas primitivas como un subconjunto de las funciones recursivas totales utilizando la función de Ackermann. Esta caracterización establece que una función es recursiva primitiva si y solo si hay un número natural m tal que la función puede ser calculada por una máquina de Turing que siempre se detiene dentro de A( m , n ) o menos pasos, donde n es la suma de los argumentos de la función recursiva primitiva. ^[5]

Una propiedad importante de las funciones recursivas primitivas es que son un subconjunto recursivamente enumerable del conjunto de todas las funciones recursivas totales (que no es recursivamente enumerable en sí mismo). Esto significa que hay una única función computable f ( m , n ) que enumera las funciones recursivas primitivas, a saber:

• Para cada función recursiva primitiva g , existe una m tal que g ( n ) = f ( m , n ) para todo n , y
• Para cada m , la función h ( n ) = f ( m , n ) es recursiva primitiva.

f se puede construir explícitamente repitiendo iterativamente todas las formas posibles de crear funciones recursivas primitivas. Por lo tanto, es demostrablemente total. Se puede usar un argumento de diagonalización para mostrar que f no es primitiva recursiva en sí misma: si lo fuera, también lo sería h ( n ) = f ( n , n )+1. Pero si esto es igual a alguna función recursiva primitiva, existe una m tal que h ( n ) = f ( m , n ) para todo n , y entonces h ( m ) = f ( m , m ), lo que lleva a una contradicción.

Sin embargo, el conjunto de funciones recursivas primitivas no es el subconjunto recursivamente enumerable más grande del conjunto de todas las funciones recursivas totales. Por ejemplo, el conjunto de funciones demostrablemente totales (en la aritmética de Peano) también es recursivamente enumerable, ya que se pueden enumerar todas las demostraciones de la teoría. Si bien todas las funciones recursivas primitivas son demostrablemente totales, lo inverso no es cierto.

Limitaciones

Las funciones recursivas primitivas tienden a corresponderse muy de cerca con nuestra intuición de lo que debe ser una función computable. Ciertamente, las funciones iniciales son intuitivamente computables (en su misma simplicidad), y las dos operaciones mediante las cuales uno puede crear nuevas funciones recursivas primitivas también son muy sencillas. Sin embargo, el conjunto de funciones recursivas primitivas no incluye cada función computable total posible; esto se puede ver con una variante del argumento diagonal de Cantor . Este argumento proporciona una función computable total que no es recursiva primitiva. Un esbozo de la prueba es el siguiente:

Las funciones recursivas primitivas de un argumento (es decir, funciones unarias) se pueden enumerar de forma computacional . Esta enumeración utiliza las definiciones de las funciones recursivas primitivas (que son esencialmente solo expresiones con las operaciones de composición y recursión primitiva como operadores y las funciones recursivas primitivas básicas como átomos), y se puede suponer que contiene cada definición una vez, aunque una misma función aparecerá muchas veces en la lista (ya que muchas definiciones definen la misma función; de hecho, simplemente componer por la función identidad genera infinitas definiciones de cualquier función recursiva primitiva). Esto significa que la -ésima definición de una función recursiva primitiva en esta enumeración se puede determinar efectivamente a partir de . De hecho, si uno usa alguna numeración de Gödel para codificar definiciones como números, entonces esta -ésima definición en la lista se calcula mediante una función recursiva primitiva de . Sea la función recursiva primitiva unaria dada por esta definición. ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle f_{n}}$

Ahora definamos la "función evaluadora" con dos argumentos, por . Claramente es total y computable, ya que se puede determinar efectivamente la definición de , y al ser una función recursiva primitiva es en sí misma total y computable, por lo que siempre está definida y es efectivamente computable. Sin embargo, un argumento diagonal mostrará que la función de dos argumentos no es recursiva primitiva. ${\displaystyle ev}$ ${\displaystyle ev(i,j)=f_{i}(j)}$ ${\displaystyle ev}$ ${\displaystyle f_{i}}$ ${\displaystyle f_{i}}$ ${\displaystyle f_{i}(j)}$ ${\displaystyle ev}$

Supongamos que fuera recursiva primitiva, entonces la función unaria definida por también sería recursiva primitiva, ya que está definida por la composición a partir de la función sucesora y . Pero entonces ocurre en la enumeración, por lo que hay algún número tal que . Pero ahora da una contradicción. ${\displaystyle ev}$ ${\displaystyle g}$ ${\displaystyle g(i)=S(ev(i,i))}$ ${\displaystyle ev}$ ${\displaystyle g}$ ${\displaystyle n}$ ${\displaystyle g=f_{n}}$ ${\displaystyle g(n)=S(ev(n,n))=S(f_{n}(n))=S(g(n))}$

Este argumento se puede aplicar a cualquier clase de funciones computables (totales) que se puedan enumerar de esta manera, como se explica en el artículo Máquina que siempre se detiene . Sin embargo, tenga en cuenta que las funciones computables parciales (aquellas que no necesitan definirse para todos los argumentos) se pueden enumerar explícitamente, por ejemplo, enumerando las codificaciones de la máquina de Turing.

Se conocen otros ejemplos de funciones recursivas totales pero no recursivas primitivas:

• La función que lleva m a Ackermann ( m , m ) es una función recursiva total unaria que no es recursiva primitiva.
• El teorema de París-Harrington implica una función recursiva total que no es recursiva primitiva.
• La función del Sudán
• La función de Goodstein

Variantes

Funciones constantes

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

Recursión primitiva débil

La función predecesora de 1 lugar es recursiva primitiva, consulte la sección #Predecesor. Fischer, Fischer y Beigel ^[6] eliminaron el predecesor implícito de la regla de recursión, reemplazándolo por la regla más débil

${\displaystyle {\begin{array}{lcl}f(0,x_{1},\ldots ,x_{k})&=&g(x_{1},\ldots ,x_{k})&{\text{and}}\\f(S(y),x_{1},\ldots ,x_{k})&=&h(S(y),f(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})\end{array}}}$

Demostraron que la función predecesora todavía podía definirse y, por lo tanto, que la recursión primitiva "débil" también define las funciones recursivas primitivas.

Funciones iterativas

Debilitando esto aún más al usar funciones de aridad k +1, eliminando y de los argumentos de por completo, obtenemos la regla de iteración : ${\displaystyle h}$ ${\displaystyle y}$ ${\displaystyle S(y)}$ ${\displaystyle h}$

${\displaystyle {\begin{array}{lcll}f(0,x_{1},\ldots ,x_{k})&=&g(x_{1},\ldots ,x_{k})&{\textrm {and}}\\f(S(y),x_{1},\ldots ,x_{k})&=&h(f(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})\end{array}}}$

La clase de funciones iterativas se define de la misma manera que la clase de funciones recursivas primitivas, excepto con esta regla más débil. Se supone que estas son un subconjunto propio de las funciones recursivas primitivas. ^[6]

Formas recursivas primitivas adicionales

Algunas formas adicionales de recursión también definen funciones que son, de hecho, 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 exactamente las funciones recursivas primitivas. Esto da una caracterización diferente de la potencia de estas funciones. La principal limitación del lenguaje LOOP, en comparación con un lenguaje Turing-completo , es que en el lenguaje LOOP el número de veces que se ejecutará cada bucle se especifica antes de que el bucle comience a ejecutarse.

Definición de lenguaje informático

Un ejemplo de un lenguaje de programación recursivo primitivo es uno que contiene operadores aritméticos básicos (por ejemplo, + y −, o ADD y SUBTRACT), condicionales y comparaciones (IF-THEN, EQUALS, LESS-THAN) y bucles acotados, como el bucle for básico , donde hay un límite superior conocido o calculable para todos los bucles (FOR i FROM 1 TO n, sin que i ni n sean modificables por el cuerpo del bucle). No se admiten estructuras de control de mayor generalidad, como bucles while o IF-THEN más GOTO , en un lenguaje recursivo primitivo.

El lenguaje LOOP , introducido en un artículo de 1967 por Albert R. Meyer y Dennis M. Ritchie , ^[7] es un lenguaje de este tipo. Su poder de cálculo coincide con 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) hace que el lenguaje sea recursivo general y Turing-completo , como lo son todos los lenguajes de programación informática del mundo real.

La definición de funciones recursivas primitivas implica que su cálculo se detiene en cada entrada (después de un número finito de pasos). Por otra parte, el problema de la detención es indecidible para las funciones recursivas generales.

Resultados del finitismo y la consistencia

Las funciones recursivas primitivas están estrechamente relacionadas con el finitismo matemático y se utilizan en varios contextos de la lógica matemática en los que se desea un sistema particularmente constructivo. La aritmética recursiva primitiva (APR), un sistema de axiomas formales para los números naturales y las funciones recursivas primitivas sobre ellos, se utiliza a menudo para este propósito.

La PRA es mucho más débil que la aritmética de Peano , que no es un sistema finitista. Sin embargo, muchos resultados de la teoría de números y de la teoría de la demostración se pueden demostrar en PRA. Por ejemplo, el teorema de incompletitud de Gödel se puede formalizar en PRA, dando el siguiente teorema:

Si T es una teoría de la aritmética que satisface ciertas hipótesis, con la oración de Gödel G _T , entonces PRA prueba la implicación Con( T )→ G _T .

De manera similar, muchos de los resultados sintácticos en la teoría de pruebas pueden demostrarse en PRA, lo que implica que existen funciones recursivas primitivas que llevan a cabo las transformaciones sintácticas correspondientes de las pruebas.

En la teoría de la prueba y la teoría de conjuntos , existe un interés en las pruebas de consistencia finitistas , es decir, pruebas de consistencia que son finitísticamente aceptables. Tal prueba establece que la consistencia de una teoría T implica la consistencia de una teoría S al producir una función recursiva primitiva que puede transformar cualquier prueba de una inconsistencia de S en una prueba de una inconsistencia de T. Una condición suficiente para que una prueba de consistencia sea finitista es la capacidad de formalizarla en PRA. Por ejemplo, muchos resultados de consistencia en la teoría de conjuntos que se obtienen al forzar pueden reformularse como pruebas sintácticas que pueden formalizarse en PRA.

Historia

Las definiciones recursivas se habían utilizado de forma más o menos formal en matemáticas antes, pero la construcción de la recursión primitiva se remonta al teorema 126 de Richard Dedekind en su obra Was sind und was sollen die Zahlen? (1888). Este trabajo fue el primero en dar una prueba de que una determinada construcción recursiva define una función única. ^{[8] [9] [10]}

La aritmética recursiva primitiva fue propuesta por primera vez por Thoralf Skolem ^[11] en 1923.

La terminología actual fue acuñada por Rózsa Péter (1934) después de que Ackermann demostrara en 1928 que la función que hoy lleva su nombre no era recursiva primitiva, evento que provocó la necesidad de renombrar lo que hasta entonces se llamaban simplemente funciones recursivas. ^{[9] [10]}

Véase también

• Jerarquía de Grzegorczyk
• Recursión (informática)
• Función recursiva primitiva
• Doble recursión
• Función de conjunto recursiva primitiva
• Función ordinal recursiva primitiva
• Llamada de cola

Notas

1. Brainerd y Landweber, 1974
2. Hartmanis, 1989
3. Por ejemplo: Henk Barendregt (1990). "Programación funcional y cálculo Lambda". En Jan van Leeuwen (ed.). Modelos formales y semántica . Manual de informática teórica. vol. B. Elsevier. págs. 321–364. ISBN 0-444-88074-7.Aquí: 2.2.6 funciones iniciales , Def.2.2.7 recursión primitiva , p.331-332.
4. Kleene [1952 págs. 226-227]
5. Esto se desprende del hecho de que las funciones de esta forma son las funciones recursivas primitivas de crecimiento más rápido, y que una función es recursiva primitiva si y solo si su complejidad temporal está limitada por una función recursiva primitiva. Para lo primero, véase Linz, Peter (2011), An Introduction to Formal Languages ​​and Automata, Jones & Bartlett Publishers, p. 332, ISBN 9781449615529Para este último, véase Moore, Cristopher ; Mertens, Stephan (2011), The Nature of Computation, Oxford University Press, pág. 287, ISBN 9780191620805
6. Fischer, Fischer y Beigel 1989.
7. Meyer, Albert R. ; Ritchie, Dennis M. (1967). La complejidad de los programas de bucle . ACM '67: Actas de la 22.ª conferencia nacional de 1967. doi : 10.1145/800196.806014 .
8. Peter Smith (2013). Introducción a los teoremas de Gödel (2.ª ed.). Cambridge University Press. pp. 98-99. ISBN 978-1-107-02284-3.
9. George Tourlakis (2003). Lecciones de lógica y teoría de conjuntos: volumen 1, lógica matemática . Cambridge University Press. pág. 129. ISBN 978-1-139-43942-8.
10. Rod Downey, ed. (2014). El legado de Turing: desarrollos a partir de las ideas de Turing en lógica . Cambridge University Press. pág. 474. ISBN 978-1-107-04348-0.
11. Thoralf Skolem (1923) "Los fundamentos de la aritmética elemental" en Jean van Heijenoort , traductor y ed. (1967) De Frege a Gödel: un libro de fuentes sobre lógica matemática, 1879-1931 . Harvard Univ. Press: 302-33.

Referencias

• Brainerd, WS, Landweber, LH (1974), Teoría de la computación , Wiley, ISBN 0-471-09585-0 
• Fischer, Michael J.; Fischer, Robert P.; Beigel, Richard (noviembre de 1989). "Recursión primitiva sin predecesor implícito". Noticias ACM SIGACT . 20 (4): 87–91. doi : 10.1145/74074.74089. S2CID  33850327.
• Juris Hartmanis (1989), “Descripción general de la teoría de la complejidad computacional” en J. Hartmanis (ed.), Computational Complexity Theory, Providence: American Mathematical Society, págs. 1–17.
• Robert I. Soare , Conjuntos y grados recursivamente enumerables , Springer-Verlag, 1987. ISBN 0-387-15299-7 
• Stephen Kleene (1952) Introducción a las metamatemáticas , North-Holland Publishing Company, Nueva York, 11.ª reimpresión, 1971: (notas de la 2.ª edición añadidas en la 6.ª reimpresión). En el capítulo XI. Funciones recursivas generales §57
• George Boolos , John Burgess , Richard Jeffrey (2002), Computabilidad y lógica: cuarta edición , Cambridge University Press, Cambridge, Reino Unido. Cf. págs. 70–71.
• Robert I. Soare 1995 Computabilidad y recursión http://www.people.cs.uchicago.edu/~soare/History/compute.pdf
• Daniel Severin 2008, Funciones recursivas primitivas unarias , J. Symbolic Logic Volumen 73, Número 4, págs. 1122–1138 arXiv projecteuclid doi :10.2178/jsl/1230396909 JSTOR  275903221