Función recursiva primitiva

En la 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 de computadora cuyos bucles son todos bucles "para" (es decir, se puede determinar un límite superior del número de iteraciones de cada bucle antes de entrando al 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 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 ené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á limitada 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 los cuales es un número natural (entero no negativo: {0, 1, 2, ...}) y devuelve un número natural. Si toma n argumentos se llama n - ario .

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

Funciones constantes $C kn $ : Para cada número natural $n$ y cada $k$ , la función constante k -aria, definida por , es recursiva primitiva. $C_{n}^{k}(x_{1},\ldots,x_{k})\ {\stackrel {\mathrm {def} }{=}}\ n$
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. $S(x)\ {\stackrel {\mathrm {def} }{=}}\ x+1$
Función de proyección : para todos los números naturales tales que , la función k -aria definida por es recursiva primitiva. $P_{i}^{k}$ $i,k$ $1\leq i\leq k$ $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:

Operador de composición (también llamado operador de sustitución ): Dadas una función m -aria y funciones m k -arias : $\circ\,$ $h(x_{1},\ldots,x_{m})\,$ $g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k})$ $h\circ (g_{1},\ldots ,g_{m})\ {\stackrel {\mathrm {def} }{=}}\ f,\quad {\text{donde}}\quad f (x_{1},\ldots ,x_{k})=h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ lpuntos,x_{k})).$
Operador de recursión primitiva $ρ$ : Dada la función k -aria y la función ( k + 2)-aria : $g(x_{1},\ldots,x_{k})\,$ $h(y,z,x_{1},\ldots ,x_{k})\,$ ${\begin{aligned}\rho (g,h)&\ {\stackrel {\mathrm {def} }{=}}\ f,\quad {\text{donde el }}(k+1) {\text{-función aria }}f{\text{ se define por}}\\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 f actúa como un bucle desde 0 hasta el valor de su primer argumento. El resto de los argumentos para f , denotados aquí con x ₁ , ..., x _k , son un conjunto de condiciones iniciales para el bucle for que puede utilizar durante los cálculos pero que son inmutables. Las funciones g y h en el lado derecho de las ecuaciones que definen f representan el cuerpo del bucle, que realiza los cálculos. La función g se usa solo una vez para realizar cálculos iniciales. Los cálculos para los pasos posteriores del bucle los realiza h . El primer parámetro de h recibe el valor "actual" del índice del bucle for. El segundo parámetro de h recibe el resultado de los cálculos previos del bucle for, de pasos anteriores. El resto de los parámetros para h son aquellas condiciones iniciales inmutables para el bucle for mencionado anteriormente. Pueden ser utilizados por h para realizar cálculos, pero h no los alterará .

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

Ejemplos

$C_{0}^{1}$ es una función 1-aria que devuelve para cada entrada: . $0$ $C_{0}^{1}(x)=0$
$C_{1}^{1}$ es una función 1-aria que devuelve para cada entrada: . $1$ $C_{1}^{1}(x)=1$
$C_{3}^{0}$ es una función 0-aria, es decir, una constante: . $C_{3}^{0}=3$
$P_{1}^{1}$ es la función identidad de los números naturales: . $P_{1}^{1}(x)=x$
$P_{1}^{2}$ y es la proyección izquierda y derecha de pares de números naturales, respectivamente: y . $P_{2}^{2}$ $P_{1}^{2}(x,y)=x$ $P_{2}^{2}(x,y)=y$
$S\circ S$ es una función 1-aria que suma 2 a su entrada, . $(S\circ S)(x)=x+2$
$S\circ C_{0}^{1}$ es una función 1-aria que devuelve 1 por cada entrada: . Es decir, y son la misma función: . De manera similar, cada se puede expresar como una composición de muchos y apropiadamente . $(S\circ C_{0}^{1})(x)=S(C_{0}^{1}(x))=S(0)=1$ $S\circ C_{0}^{1}$ $C_{1}^{1}$ $S\circ C_{0}^{1}=C_{1}^{1}$ $C_{n}^{1}$ $S$ $C_{0}^{1}$

Suma

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

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

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

{\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, . $Add$ $Add\circ (P_{1}^{1},P_{1}^{1})$ $(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 mediante . Esto reproduce las conocidas ecuaciones de multiplicación: $Mul=\rho (C_{0}^{1},Add\circ (P_{2}^{3},P_{3}^{3}))$

{\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}}

{\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 está definida recursivamente por las reglas y . Una definición recursiva primitiva es . Como ejemplo de cálculo, $Pred(0)=0$ $Pred(S(n))=n$ $Pred=\rho (C_{0}^{0},P_{1}^{2})$

{\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 resta limitada (también llamada " monus " y denominada " ") se puede definir a partir de la función predecesora. Satisface las ecuaciones ${\stackrel {.}{-}}$

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

Dado que la recursividad pasa por el segundo argumento, comenzamos con una definición recursiva primitiva de la resta invertida, . Luego, su recursividad pasa por el primer argumento, por lo que su definición recursiva primitiva se puede obtener, similar a la suma, como . Para deshacerse del orden invertido de los argumentos, defina . Como ejemplo de cálculo, $RSub(y,x)=x{\stackrel {.}{-}}y$ $RSub=\rho (P_{1}^{1},Pred\circ P_{2}^{3})$ $Sub=RSub\circ (P_{2}^{2},P_{1}^{2})$

{\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, t para verdadero yf para falso), o que producen valores de verdad como salidas. ^[3] 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 t con el número 1 y el valor de verdad f con el número 0. Una vez realizada esta identificación, la función característica de un conjunto A , que siempre devuelve 1 o 0, puede ser visto como un predicado que indica si un número está en el conjunto A. Esta identificación de predicados con funciones numéricas se asumirá durante el resto de este artículo.

Predicado "Es cero"

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

Predicado "Menos o igual"

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

{\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 sólo si, . $Leq$ $Geq=Leq\circ (P_{2}^{2},P_{1}^{2})$ $Geq(x,y)=Leq(y,x)$ $x\geq y$

Si-entonces-si no

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

{\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}}

{\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 entonces, si la parte si, es verdadera, y la parte más, en caso contrario. ${\textit {If}}(x,y,z)$ $y$ $x$ $z$

Junctores

Según la función, es fácil definir juntas lógicas. Por ejemplo, al definir , se obtiene , es decir, es verdadero si, y sólo si , ambos y son verdaderos ( conjunción lógica de y ). ${\textit {If}}$ $And={\textit {If}}\circ (P_{1}^{2},P_{2}^{2},C_{0}^{2})$ $And(x,y)={\textit {If}}(x,y,0)$ $And(x,y)$ $x$ $y$ $x$ $y$

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

Predicado de igualdad

Usando las funciones anteriores y , la definición implementa el predicado de igualdad. De hecho, es cierto si y sólo si es igual a . $Leq$ $Geq$ $And$ $Eq=And\circ (Leq,Geq)$ $Eq(x,y)=And(Leq(x,y),Geq(x,y))$ $x$ $y$

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

Otras operaciones con números naturales

Las pruebas de exponenciación y primalidad son recursivas primitivas. Dadas las funciones recursivas primitivas e , f , g y h , una función que devuelve el valor de g cuando e ≤ f y el valor de h en caso contrario es recursiva primitiva.

Operaciones con números enteros y racionales.

Al utilizar numeraciones de Gödel , las funciones recursivas primitivas se pueden extender para operar en otros objetos como números enteros y racionales . Si los números enteros se codifican mediante números de Gödel de forma 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 están representados por números de Gödel, entonces todas las operaciones de campo son recursivas primitivas.

Algunas funciones recursivas primitivas comunes

Los siguientes ejemplos y definiciones provienen 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) dependiendo de la derivación exacta.

En lo sucesivo, 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 y su extracción de su forma "aritmética" expresada como números de Gödel .

Adición: a+b
Multiplicación: a×b
Exponenciación: a ^b
Factorial a! : 0! = 1, a'! = a!×a'
pred(a): (Predecesor o decremento): Si a > 0 entonces a−1 sino 0
Resta adecuada a ∸ b: Si a ≥ b entonces a−b sino 0
Mínimo(a ₁ , ... a _n )
Máximo(a ₁ , ... a _n )
Diferencia absoluta: | a-b | = _def (a ∸ b) + (b ∸ a)
~sg(a): NOT[signum(a)]: Si a=0 entonces 1 si no 0
sg(a): signum(a): Si a=0 entonces 0 si no 1
un | b: (a divide b): Si b=k×a para algún k entonces 0 o 1
Resto (a, b): el resto si b no divide a "equitativamente". También llamado MOD(a,b)
a = b: sg | un - segundo | (La convención de Kleene era representar verdadero por 0 y falso por 1; actualmente, especialmente en computadoras, la convención más común es la inversa, es decir, representar verdadero por 1 y falso por 0, lo que equivale a cambiar sg por ~sg aquí y en el siguiente elemento)
a < b: sg( a' ∸ b )
Pr(a): a es un número primo Pr(a) = _def a>1 & NOT(Existe c) _1<c<a [ c|a ]
p _i : el i+1º número primo
(a) _i : exponente de p _i en a: el único x tal que p _i^x |a & NOT(p _i^x' |a)
lh(a): la "longitud" o número de exponentes que no desaparecen en un
lo(a, b): (logaritmo de a en base b): Si a, b > 1 entonces el mayor x tal que b ^x | otro 0

En lo sucesivo, 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 funciones χ ₁ ,..., χ _m por las respectivas variables de un predicado Q es primitivo recursivo en χ ₁ ,..., χ _m , Q.
#D: Los siguientes predicados son recursivos primitivos en Q y R:

NOT_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 una 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 : definido como "el valor mínimo 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 así definida, donde Q ₁ , ..., Q _{m son}predicados mutuamente excluyentes (o "ψ( x ) tendrá el valor dado por la primera cláusula que aplique), es primitiva recursiva en φ ₁ , ..., Q ₁ , ... Q _metro :

φ( 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 an} ) de la función de curso de valores codifica la secuencia de valores φ(0, x _{2 an} ), ..., φ(y-1, x _{2 an} ) de la función original.

Relación con funciones recursivas

La clase más amplia de funciones recursivas parciales se define introduciendo un operador de búsqueda ilimitado . El uso de este operador puede resultar en 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 (ver dominio ). Una definición equivalente establece que una función recursiva parcial es aquella que puede calcularse mediante una máquina de Turing . Una función recursiva total es una función recursiva parcial que se define para cada entrada.

Cada 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 sólo si existe un número natural m tal que la función pueda 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. ^[4]

Una propiedad importante de las funciones recursivas primitivas es que son un subconjunto recursivamente enumerable del conjunto de todas las funciones recursivas totales (que en sí mismo no es recursivamente enumerable). 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 puede construirse explícitamente repitiendo iterativamente todas las formas posibles de crear funciones recursivas primitivas. Por tanto, es demostrablemente total. Se puede utilizar un argumento de diagonalización para demostrar que f no es primitiva recursiva en sí misma: si lo hubiera sido, también lo sería h ( n ) = f ( n , n )+1. Pero si esto es igual a alguna función recursiva primitiva, hay una m tal que h ( n ) = f ( m , n ) para todo n , y luego 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 aritmética de Peano) también es recursivamente enumerable, ya que se pueden enumerar todas las pruebas de la teoría. Si bien todas las funciones recursivas primitivas son demostrablemente totales, lo contrario no es cierto.

Limitaciones

Las funciones recursivas primitivas tienden a corresponderse muy estrechamente 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 se pueden crear nuevas funciones recursivas primitivas también son muy sencillas. Sin embargo, el conjunto de funciones recursivas primitivas no incluye todas las funciones computables totales posibles; 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 bosquejo de la prueba es el siguiente:

Las funciones recursivas primitivas de un argumento (es decir, funciones unarias) se pueden enumerar de forma computable . Esta enumeración utiliza las definiciones de las funciones recursivas primitivas (que son esencialmente expresiones con la composición y las operaciones recursivas primitivas 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 ocurrirá muchas veces en la lista (ya que muchas definiciones definen la misma función; de hecho, simplemente componer mediante la función de identidad genera infinitas definiciones de cualquier función recursiva primitiva). Esto significa que la

enésima

definición de una función recursiva primitiva en esta enumeración se puede determinar efectivamente a partir de

n

. De hecho, si uno usa alguna numeración de Gödel para codificar definiciones como números, entonces esta

enésima

definición en la lista se calcula mediante una función recursiva primitiva de

n

. Sea

f n

la función recursiva primitiva unaria dada por esta definición.

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

Supongamos que

ev

fuera recursiva primitiva, entonces la función unaria

g

definida por

g (i) = S(ev (i, i))

también sería recursiva primitiva, ya que está definida por la composición de la función sucesora y

ev

. Pero entonces

g

ocurre en la enumeración, por lo que hay algún número

n

tal que

g = f n

. Pero ahora

g (n) = S(ev (n, n)) = S(f n (n)) = S(g (n))

da una contradicció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 codificaciones de la máquina de Turing.

Se conocen otros ejemplos de funciones recursivas totales pero no 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 Paris-Harrington implica una función recursiva total que no es recursiva primitiva.
La función de Sudán
La función de Goodstein

Variantes

Funciones constantes

En lugar de , las definiciones alternativas usan solo una función cero 0-aria como una 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. $C_{n}^{k}$ $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 & Beigel ^[5] eliminaron el predecesor implícito de la regla de recursividad, reemplazándolo por la regla más débil.

{\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 aún se podía definir y, por tanto, que la recursividad primitiva "débil" también define las funciones recursivas primitivas.

Funciones iterativas

Debilitando esto aún más usando funciones de aridad k +1, eliminando y de los argumentos de completamente, obtenemos la regla de iteración : $h$ $y$ $S(y)$ $h$

${\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 conjetura que son un subconjunto adecuado de las funciones recursivas primitivas. ^[5]

Formas recursivas primitivas adicionales

Algunas formas adicionales de recursividad 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 recursividad del curso de valores define funciones recursivas primitivas. Algunas formas de recursividad 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 del poder de estas funciones. La principal limitación del lenguaje LOOP, en comparación con un lenguaje completo de Turing , es que en el lenguaje LOOP se especifica el número de veces que se ejecutará cada bucle antes de que comience a ejecutarse.

Definición del 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 SUMA y RESTA), condicionales y comparación (SI-ENTONCES, IGUAL, MENOS QUE) y bucles acotados, como el básico for loop , donde hay un límite superior conocido o calculable para todos los bucles (FOR i FROM 1 TO n, sin i ni n modificables por el cuerpo del bucle). En un lenguaje recursivo primitivo no se admiten estructuras de control de mayor generalidad, como bucles while o IF-THEN más GOTO .

El lenguaje LOOP , introducido en un artículo de 1967 por Albert R. Meyer y Dennis M. Ritchie , ^[6] es uno de esos lenguajes. Su potencia de cálculo coincide con las funciones recursivas primitivas. Una variante del lenguaje LOOP es BlooP de Douglas Hofstadter en Gödel, Escher, Bach . Agregar bucles ilimitados (WHILE, GOTO) hace que el lenguaje sea recursivo en general y completo en Turing , como lo son todos los lenguajes de programación de computadoras 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 otro lado, el problema de la detención es indecidible para funciones recursivas generales.

Resultados de finitismo y consistencia

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

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 prueba pueden demostrarse 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 demuestra la implicación Con( T )→ G _T .

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

En la teoría de la prueba y la teoría de conjuntos , existe interés en las pruebas de consistencia finitistas , es decir, pruebas de consistencia que en sí mismas 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 coherencia sea finitista es la capacidad de formalizarla en PRA. Por ejemplo, muchos resultados de consistencia en la teoría de conjuntos que se obtienen forzando pueden reformularse como pruebas sintácticas que pueden formalizarse en PRA.

Historia

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

La aritmética recursiva primitiva fue propuesta por primera vez por Thoralf Skolem ^[10] 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, hecho que impulsó la necesidad de cambiar el nombre de lo que hasta entonces se llamaban simplemente funciones recursivas. ^[8]^[9]

Ver también

Notas

^ Brainerd y Landweber, 1974
^ Hartmanis, 1989
^ Kleene [1952 págs. 226-227]
^ 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 sólo si su complejidad temporal está limitada por una función recursiva primitiva. Para el primero, véase Linz, Peter (2011), Introducción a los lenguajes formales y los autómatas, Jones & Bartlett Publishers, p. 332, ISBN 9781449615529. Para este último, véase Moore, Cristopher ; Mertens, Stephan (2011), La naturaleza de la computación, Oxford University Press, pág. 287, ISBN 9780191620805
^ ab Fischer, Fischer y Beigel 1989.
^ 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 .
^ Peter Smith (2013). Introducción a los teoremas de Gödel (2ª ed.). Prensa de la Universidad de Cambridge. págs. 98–99. ISBN 978-1-107-02284-3.
^ ab George Tourlakis (2003). Conferencias de lógica y teoría de conjuntos: volumen 1, lógica matemática . Prensa de la Universidad de Cambridge. pag. 129.ISBN 978-1-139-43942-8.
^ ab Rod Downey, ed. (2014). El legado de Turing: desarrollos de las ideas de Turing en lógica . Prensa de la Universidad de Cambridge. pag. 474.ISBN 978-1-107-04348-0.
↑ 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 consulta sobre lógica matemática, 1879-1931 . Universidad de Harvard. Prensa: 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.), Teoría de la complejidad computacional, Providence: American Mathematical Society, págs.
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 recursividad 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