Función recursiva primitiva

ImprimirCitar

Función computable con bucles atados

En la teoría de la computabilidad, una función recursiva primitiva es, en términos generales, una función que puede calcularse mediante un programa de computadora cuyos bucles son todos "for" bucles (es decir, se puede determinar 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 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 todos recursivos primitivos. De hecho, para mostrar que una función computable es recursiva primitiva, basta con mostrar que su complejidad temporal está acotada superiormente por una función recursiva primitiva del tamaño de entrada. Por lo tanto, no es tan fácil diseñar una función computable que no sea recursiva primitiva; se muestran algunos ejemplos 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 llama n-ario.

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

Funciones constantes $C k n$ : Para cada número natural $n$ y todos $k$ , el k- función constante, definida por ${displaystyle C_{n}^{k}(x_{1},ldotsx_{k}) {stackrel {mathrm {def} }{=}} n}$ , es recursivo primitivo.
Función de éxito: Función sucesora 1-ary S, que devuelve al sucesor de su argumento (ver Peano postulates), es decir, ${displaystyle S(x) {stackrel {mathrm {def} }{=}} x+1}$ , es recursivo primitivo.
Función de proyección $P_{i}^{k}$ : Para todos los números naturales ${displaystyle i,k}$ tales que $1leq ileq k$ , el k- Funciónaria definida ${displaystyle P_{i}^{k}(x_{1},ldotsx_{k}) {stackrel {mathrm {def} }{=}} x_{i}}$ es recursivo primitivo.

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

Composition operator $circ ,$ (también llamado el substitution operator): Dado un m- Función diaria $h(x_{1},ldotsx_{m}),$ y m k- Funciones $g_{1}(x_{1},ldotsx_{k}),ldotsg_{m}(x_{1},ldotsx_{k})$ : ${displaystyle hcirc (g_{1},ldotsg_{m}) {stackrel {mathrm {def} }{=}} f,quad {text{where}}quad f(x_{1},ldotsx_{k})=h(g_{1}(x_{1},ldotsx_{k}),ldotsg_{m}(x_{1},ldotsx_{k})).}$
Operador de recursión primitiva $***$ : Dada la k- Función diaria $g(x_{1},ldotsx_{k}),$ y elk+ 2) función diaria $h(y,z,x_{1},ldotsx_{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},ldotsx_{k})&=g(x_{1},ldotsx_{k})\f(S(y),x_{1},ldotsx_{k})&=h(y,f(y,x_{1},ldotsx_{k}),x_{1},ldotsx_{k}).end{aligned}}}$
Interpretación:
La funciónf actúa como un for-loop de 0 hasta el valor de su primer argumento. El resto de los argumentos paraf, denotado aquí con x₁,...,x_k, son un conjunto de condiciones iniciales para el bucle que puede ser utilizado por él durante cálculos pero que son inmutables por él. Funciones g y h en el lado derecho de las ecuaciones que definen f representan el cuerpo del bucle, que realiza cálculos. La funcióng se utiliza sólo una vez para realizar cálculos iniciales. Cálculos para los pasos posteriores del bucle se realizan porh. El primer parámetro deh es alimentado el valor "corriente" del índice de for-loop. El segundo parámetro deh es alimentado el resultado de los cálculos previos del circuito, de pasos anteriores. El resto de los parámetros parah son esas condiciones iniciales inmutables para el bucle mencionado anteriormente. Pueden ser utilizados porh para realizar cálculos pero ellos mismos no serán alterados porh.

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

Ejemplos

${displaystyle C_{0}^{1}}$ es una función 1-ary que devuelve ${displaystyle 0}$ para cada entrada: ${displaystyle C_{0}^{1}(x)=0}$ .
$C_{1}^{1}$ es una función 1-ary que devuelve $1$ para cada entrada: ${displaystyle C_{1}^{1}(x)=1}$ .
${displaystyle C_{3}^{0}}$ es una función 0-ary, es decir, una constante: ${displaystyle C_{3}^{0}=3}$ .
${displaystyle P_{1}^{1}}$ es la función de identidad en los números naturales: ${displaystyle P_{1}^{1}(x)=x}$ .
${displaystyle P_{1}^{2}}$ y ${displaystyle P_{2}^{2}}$ es la proyección izquierda y derecha en pares de números naturales, respectivamente: ${displaystyle P_{1}^{2}(x,y)=x}$ y ${displaystyle P_{2}^{2}(x,y)=y}$ .
${displaystyle Scirc S}$ es una función 1-ary que añade 2 a su entrada, ${displaystyle (Scirc S)(x)=x+2}$ .
${displaystyle Scirc C_{0}^{1}}$ es una función 1-ary que devuelve 1 para cada entrada: ${displaystyle (Scirc C_{0}^{1})(x)=S(C_{0}^{1}(x))=S(0)=1}$ . Eso es, ${displaystyle Scirc C_{0}^{1}}$ y $C_{1}^{1}$ son la misma función: ${displaystyle Scirc C_{0}^{1}=C_{1}^{1}}$ . De una manera similar, cada ${displaystyle C_{n}^{1}}$ puede expresarse como una composición apropiada de muchos $S$ y ${displaystyle C_{0}^{1}}$ .

Adición

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

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

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

{displaystyle {begin{array}{lll}&Add(1,7)\=&rho (P_{1}^{1},Scirc P_{2}^{3});(S(0),7)&{text{ by Def. }}Add,S\=&(Scirc P_{2}^{3})(0,Add(0,7),7)&{text{ by case }}rho (g,h);(S(...),...)\=&S(Add(0,7))&{text{ by Def. }}circP_{2}^{3}\=&S(;rho (P_{1}^{1},Scirc 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 ${displaystyle Add}$ , la función 1-ary ${displaystyle Addcirc (P_{1}^{1},P_{1}^{1})}$ duplica su argumento, ${displaystyle (Addcirc (P_{1}^{1},P_{1}^{1}))(x)=Add(x,x)=x+x}$ .

Multiplicación

De manera similar como adición, la multiplicación puede ser definida por ${displaystyle Mul=rho (C_{0}^{1},Addcirc (P_{2}^{3},P_{3}^{3}))}$ . Esto reproduce las ecuaciones de multiplicación conocidas:

{displaystyle {begin{array}{lll}&Mul(0,y)\=&rho (C_{0}^{1},Addcirc (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}}}

{displaystyle {begin{array}{lll}&Mul(S(x),y)\=&rho (C_{0}^{1},Addcirc (P_{2}^{3},P_{3}^{3}));(S(x),y)&{text{ by Def. }}Mul\=&(Addcirc (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. }}circP_{2}^{3},P_{3}^{3}\=&Mul(x,y)+y&{text{ by property of }}Add.\end{array}}}

Predecesora

(feminine)

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

{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 restante limitada (también llamada "monus", y denotado " ${displaystyle {stackrel {.}{-}}}$ ") es definible de la función predecesora. Satisface las ecuaciones

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

Puesto que la recursión pasa por el segundo argumento, comenzamos con una definición recursiva primitiva de la resta inversa, ${displaystyle RSub(y,x)=x{stackrel {.}{-}}y}$ . Su recursión entonces se extiende sobre el primer argumento, por lo que se puede obtener su definición recursiva primitiva, similar a la adición, como ${displaystyle RSub=rho (P_{1}^{1},Predcirc P_{2}^{3})}$ . Para deshacerse de la orden de argumento inversa, luego definir ${displaystyle Sub=RSubcirc (P_{2}^{2},P_{1}^{2})}$ . Como ejemplo de cálculo,

{displaystyle {begin{array}{lll}&Sub(8,1)\=&(RSubcirc (P_{2}^{2},P_{1}^{2}));(8,1)&{text{ by Def. }}Sub\=&RSub(1,8)&{text{ by Def. }}circP_{2}^{2},P_{1}^{2}\=&rho (P_{1}^{1},Predcirc P_{2}^{3});(S(0),8)&{text{ by Def. }}RSub,S\=&(Predcirc P_{2}^{3});(0,RSub(0,8),8)&{text{ by case }}rho (g,h);(S(...),...)\=&Pred(RSub(0,8))&{text{ by Def. }}circP_{2}^{3}\=&Pred(;rho (P_{1}^{1},Predcirc 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 algunas configuraciones, es natural considerar funciones recursivas primitivas que toman como entrada tuplas que mezclan números con valores de verdad (es decir, t para verdadero y f para falso), o que producen valores de verdad como salidas. Esto se puede lograr identificando los valores de verdad con números de cualquier forma 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 verse como un predicado que indica si un número está en el conjunto A. Tal identificación de predicados con funciones numéricas se asumirá en el resto de este artículo.

Predicado "Es cero"

Como ejemplo para un predicado recursivo primitivo, la función 1-ary ${displaystyle IsZero}$ será definido como ${displaystyle IsZero(x)=1}$ si $x=0$ , y ${displaystyle IsZero(x)=0}$ De lo contrario. Esto puede lograrse definiendo ${displaystyle IsZero=rho (C_{1}^{0},C_{0}^{2})}$ . Entonces, ${displaystyle IsZero(0)=rho (C_{1}^{0},C_{0}^{2})(0)=C_{1}^{0}(0)=1}$ y por ejemplo. ${displaystyle IsZero(8)=rho (C_{1}^{0},C_{0}^{2})(S(7))=C_{0}^{2}(7,IsZero(7))=0}$ .

Predicado "Menor o igual"

Utilizando la propiedad ${displaystyle xleq yiff x{stackrel {.}{-}}y=0}$ , la función 2-ary ${displaystyle Leq}$ puede definirse ${displaystyle Leq=IsZerocirc Sub}$ . Entonces... ${displaystyle Leq(x,y)=1}$ si $xleq y$ , y ${displaystyle Leq(x,y)=0}$ De lo contrario. Como ejemplo de cálculo,

{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 definida ${displaystyle Leq}$ se obtiene, el predicado transversal se puede definir como ${displaystyle Geq=Leqcirc (P_{2}^{2},P_{1}^{2})}$ . Entonces, ${displaystyle Geq(x,y)=Leq(y,x)}$ es cierto (más precisamente: tiene valor 1) si, y sólo si, ${displaystyle xgeq y}$ .

Si-entonces-otro

El operador 3-ary if-then-else conocido desde lenguajes de programación puede ser definido por ${displaystyle {textit {If}}=rho (P_{2}^{2},P_{3}^{4})}$ . Entonces, por arbitrariedad $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}}}

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

Eso es, ${displaystyle {textit {If}}(x,y,z)}$ devuelve la parte posterior, $y$ Si la parte si, $x$ , es verdad, y la otra parte, $z$ De lo contrario.

Juntas

Basado en ${displaystyle {textit {If}}}$ función, es fácil definir los junctores lógicos. Por ejemplo, definir ${displaystyle And={textit {If}}circ (P_{1}^{2},P_{2}^{2},C_{0}^{2})}$ , uno obtiene ${displaystyle And(x,y)={textit {If}}(x,y,0)}$ , es decir, ${displaystyle And(x,y)}$ es verdad si, y sólo si, ambos $x$ y $y$ son verdaderas (conjunción lógica de $x$ y $y$ ).

Análogamente, ${displaystyle Or={textit {If}}circ (P_{1}^{2},C_{1}^{2},P_{2}^{2})}$ y ${displaystyle Not={textit {If}}circ (P_{1}^{1},C_{0}^{1},C_{1}^{1})}$ dar lugar a definiciones apropiadas de desjunción y negación: ${displaystyle Or(x,y)={textit {If}}(x,1,y)}$ y ${displaystyle Not(x)={textit {If}}(x,0,1)}$ .

Predicado de igualdad

Utilizando las funciones anteriores ${displaystyle Leq}$ , ${displaystyle Geq}$ y ${displaystyle And}$ , la definición ${displaystyle Eq=Andcirc (Leq,Geq)}$ implementa la situación de igualdad. De hecho, ${displaystyle Eq(x,y)=And(Leq(x,y),Geq(x,y))}$ es verdad si, y sólo si, $x$ iguales $y$ .

Análogamente, la definición ${displaystyle Lt=Notcirc Geq}$ implementa el predicado "menos-que", y ${displaystyle Gt=Notcirc Leq}$ implementa "greater-than".

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 de lo contrario es recursivo primitivo.

Operaciones con números enteros y racionales

Al usar la numeración de Gödel, las funciones recursivas primitivas se pueden extender para operar en otros objetos, como números enteros y números 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 recursivas primitivas. De manera similar, si los racionales están representados por números de Gödel, entonces las operaciones de campo son todas recursivas primitivas.

Algunas funciones recursivas primitivas comunes

Los siguientes ejemplos y definiciones son de Kleene (1952) pp. 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 pp. 63–70; añaden el logarithm lo(x, y) o lg(x, y) dependiendo de la derivación exacta.

A continuación observamos que las funciones recursivas primitivas pueden ser de cuatro tipos:

funciones para abreviar: "funciones teórico-número" de { 0, 1, 2,...} a { 0, 1, 2,...},
predicados: de { 0, 1, 2,...} a los valores de verdad { t =true, f =false },
conexiones proposicionesde los valores de la verdad a los valores de la verdad
funciones: de los valores de la verdad { t, f } a { 0, 1, 2,... }. Muchas veces un predicado requiere una función representativa para convertir la salida del predicado { t, f } a { 0, 1 } (nota el orden "t" a "0" y "f" a "1" partidos con ~sg() definido abajo). Por definición una función φ(x) es una "función representativa" del predicado P(x) si φ toma sólo los valores 0 y 1 y produce 0 cuando P es verdad".

A continuación, la marca " ' ", p. a', es la marca primitiva que significa "el sucesor de", generalmente considerado como " +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 sus funciones "aritméticas" forma expresada como números de Gödel.

Adición: a+b
Multiplicación: a×b
Exposición: a^b
Factorial a!: 0! = 1, a' = a'! '
pred(a): (Predecesador o decremento): Si un título 0 entonces a-1 0
Sustracción adecuada a ∸ b: Si un ≥ b entonces a-b 0
Mínimo(a)₁,... a_n)
Máximo(a)₁,... a_n)
Diferencia absoluta:_def (a ∸ b) + (b ∸ a)
~sg(a): NOT[signum(a)]: Si a=0 entonces 1 más 0
sg(a): signum(a): Si a=0 entonces 0 más 1
a Silencio b: (una división b): Si b=k×a para algunos k entonces 0 más 1
Restante(a, b): la sobra si b no divide un "evenalmente". También se llama MOD(a, b)
a = b: sg Silencio a - b Silencio (La convención de Cleene era representar verdadero por 0 y falso por 1; actualmente, especialmente en las computadoras, la convención más común es la inversa, a saber, representar verdadero por 1 y falso por 0, lo que equivale a cambiar sg en ~sg aquí y en el siguiente artículo)
a b: sg(a' ∸ b)
Pr(a): a es un número primario Pr(a) =_def a título personal1 < NO(Existe c)_{1 sec} [ c sometidaa]
p_i: el número i+1-est
a)_i: exponente de p_i en a: el único x tal que p_i^xtención no(p_i^{x '}Silencio
lh(a): la "longitud" o número de exponentes no-vanishing en un
Lo(a, b): (logaritmo de a a base b): Si a, b > 1 entonces el mayor x tal que b^x Silencio a otra 0

En lo siguiente, la abreviatura x =_def x₁, x_n; los subscriptos pueden ser aplicados si el significado requiere.

#A: Una función φ definable explícitamente de funciones Ψ y constantes q₁, q_n es recursivo primitivo en Ψ.
#B: La suma finita_y ↓x, y) y el producto_y↓x, y) son primitivas recursivas en .
#C: A predicar P obtenido por funciones de sustitución χ₁, χ_m para las variables respectivas de un predicado Q es recursivo primitivo en la χ₁, χ_m, Q.
#D: The following predicados son primitivos recursivos en Q y R:

NOT_Q(x).
Q OR R: Q(xV Rx),
Q AND R: Q(xRx),
Q IMPLIES R: Q(x) → R(x)
Q es equivalente a R: Q(x)x)

#E: The following predicados son primitivas recursivas en predicar R:

(Ey)_y R(x, y) donde (Ey)_y denota "hay al menos un y que es menos que z tal que"
(y)_y R(x, y) donde (y)_y denota "para todos y menos que z es verdad que"
μy_y R(x, y). El operador μy_y R(x, y) es un atado forma de la llamada minimización- o mu-operador: Definido como "el menor valor de y menos que z tal que R(x, y) es cierto; o z si no hay tal valor."

Definición por casos: La función se define así, donde Q₁,..._m son mutuamente excluyentes predicados (o "nuevo(x) tendrá el valor dado por la primera cláusula que aplica), es primitiva recursiva en φ₁,...₁,... Q_m:

φ(x)

φ₁()xSi Q₁()x) es verdad,
...............
φ_m()xSi Q_m()x) es verdad
φ_m+1()xDe lo contrario

#G: Si φ satisface la ecuación:

φ(y,x) = χ(y, COURSE-φ(y; x₂, x_n), x₂, x_n entonces φ es recursivo primitivo en la χ. 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.

Utilizar en aritmética de Peano de primer orden

En la aritmética de Peano de primer orden, hay un número infinito de variables (símbolos 0-arios), pero no hay símbolos no lógicos k-arios con k>0 que no sean S, +, * y ≤. Por lo tanto, para definir funciones recursivas primitivas, se debe usar el siguiente truco de Gödel.

Al usar una numeración de Gödel para secuencias, por ejemplo, la función β de Gödel, cualquier secuencia finita de números se puede codificar con un solo número. Por lo tanto, tal número puede representar la función recursiva primitiva hasta un n dado.

Sea h una función recursiva primitiva aria definida por:

{displaystyle h(0)=C}

{displaystyle h(n+1)=g(n,h(n))}

donde C es una constante y g es una función ya definida.

Usando la función β de Gödel, para cualquier secuencia de números naturales (k₀, k₁,..., k_n), existen números naturales b y c tales que, para todo i ≤ n, β(b, c, i) = k_i. Por lo tanto, podemos usar la siguiente fórmula para definir h; más precisamente, m=h(n) es una forma abreviada de lo siguiente:

<math alttext="{displaystyle exists b:exists c:beta (b,c,0)=Cland forall i:(i\exists \exists b:\exists \exists c:β β ()b,c,0)=C\land \land О О i:()i.n)\to \to ()β β ()b,c,i+1)=g()i,β β ()b,c,i)))\land \land ()m=β β ()b,c,n)){displaystyle exists b:exists c:beta (b,c,0)=Cland forall i:(i donen)rightarrow (beta (b,c,i+1)=g(i,beta (b,c,i))))land (m=beta (b,c,n)} <img alt="{displaystyle exists b:exists c:beta (b,c,0)=Cland forall i:(i

y la equiparación a g, ya definida, es de hecho una abreviatura de alguna otra fórmula ya definida (como lo es β, cuya fórmula se da aquí).

La generalización a cualquier función recursiva primitiva k-aria es trivial.

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

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 recursivo primitivo. Se caracterizan 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.

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, hay un m tales que g()n) f()m,n) para todos n, y
Por todos m, la función h()n) f()m,n) es primitiva recursiva.

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 un primitivo recursivo en sí mismo: 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, existe una m tal que h(n) = f(m,n) para todo n, y luego h(m) = f(m,m), lo que lleva a la 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 uno puede 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 corresponder 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 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 esquema de la demostración es el siguiente:

Las funciones recursivas primitivas de un argumento (es decir, funciones inadvertidas) pueden enumerarse computadamente. Esta enumeración utiliza las definiciones de las funciones recursivas primitivas (que son esencialmente sólo expresiones con la composición y las operaciones de recursión primitiva como operadores y las funciones recursivas primitivas básicas como átomos), y se puede suponer que contienen 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 por la función de identidad genera infinitamente muchas definiciones de cualquier función recursiva primitiva). Esto significa que

n

-la definición de una función recursiva primitiva en esta enumeración puede determinarse efectivamente a partir de

n

. De hecho, si uno utiliza algunos Gödel numeración para codificar definiciones como números, entonces esto

n

-la definición en la lista es calculada por una función recursiva primitiva

n

. Vamos

f n

denotar la función recursiva primitiva no original dada por esta definición.

Ahora definir la "función del evaluador" $ev$ con dos argumentos, por $ev () i, j) f i () j)$ . Claramente $ev$ es total y computable, ya que uno puede determinar eficazmente la definición $f i$ , y ser una función recursiva primitiva $f i$ es en sí mismo total y computable, así $f i () j)$ es siempre definido y efectivamente computable. Sin embargo, un argumento diagonal mostrará que la función $ev$ de dos argumentos no es recursivo primitivo.

Suppose

ev

eran primitivas recursivas, entonces la función no seria

g

definidas por

g () i . ev () i, i)

sería también recursivo primitivo, ya que se define 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

tales que

g = f n

. Pero ahora

g () n . 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 pueden 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 toma m a Ackermann(m,m) es una función recursiva total no original que no es recursiva primitiva.
El teorema de París-Harrington implica una función recursiva total que no es recursiva primitiva.
Función del Sudán
La función Goodstein

Variantes

Funciones constantes

En lugar de $C_{n}^{k}$ , definiciones alternativas utilizan sólo un 0-ary Función cero ${displaystyle C_{0}^{0}}$ como una función primitiva que siempre devuelve cero, y construye las funciones constantes de la función cero, la función sucesora y el operador de composición.

Recursión primitiva débil

La función predecesora de 1 lugar es recursiva primitiva, consulte la sección #Predecesor. Fischer, Fischer &amperio; Beigel eliminó 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},ldotsx_{k})&=&g(x_{1},ldotsx_{k})&{text{and}}\f(S(y),x_{1},ldotsx_{k})&=&h(S(y),f(y,x_{1},ldotsx_{k}),x_{1},ldotsx_{k})end{array}}}

Probaron que la función predecesora aún se podía definir y, por lo tanto, que "débil" La recursividad primitiva también define las funciones recursivas primitivas.

Funciones iterativas

Debilitándolo aún más utilizando funciones $h$ de la aridad k+1, eliminación $y$ y $S(y)$ de los argumentos de $h$ completamente, tenemos el iteración regla:

${displaystyle {begin{array}{lcll}f(0,x_{1},ldotsx_{k})&=&g(x_{1},ldotsx_{k})&{textrm {and}}\f(S(y),x_{1},ldotsx_{k})&=&h(f(y,x_{1},ldotsx_{k}),x_{1},ldotsx_{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 estas son un subconjunto propio de las funciones recursivas primitivas.

Formas recursivas primitivas adicionales

Algunas formas adicionales de recursividad también definen funciones que son de hecho recursivo primitivo. Las definiciones en estos formularios pueden ser más fáciles de encontrar o más natural para leer o escribir. La recursión de 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 ciclo antes de que el ciclo 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 (p. ej., + y -, o SUMA y RESTA), condicionales y comparación (SI-ENTONCES, IGUAL, MENOR-QUE) y bucles acotados, como 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 i ni n 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, es uno de esos lenguajes. Su poder de cómputo 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 Turing completo, 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, incluso si son totales. Es decir, hay programas que se detienen en cada entrada, pero para los cuales esto no puede ser verificado por un algoritmo.

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. La aritmética recursiva primitiva (PRA), un sistema de axiomas formales para los números naturales y las funciones recursivas primitivas en ellos, se usa a menudo para este propósito.

PRA es mucho más débil que la aritmética de Peano, que no es un sistema finitista. Sin embargo, muchos resultados en la teoría de números y en la teoría de la demostración pueden probarse 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 aritmética satisfacer ciertas hipótesis, con la sentencia de Gödel G_T, entonces PRA demuestra la implicación Con(T)→G_T.

Del mismo modo, muchos de los resultados sintácticos de la teoría de las demostraciones pueden probarse en PRA, lo que implica que existen funciones recursivas primitivas que realizan las correspondientes transformaciones sintácticas de las demostraciones.

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, las 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 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 forzando pueden reformularse como pruebas sintácticas que pueden formalizarse en PRA.

Historia

Las definiciones recursivas se habían usado antes de manera más o menos formal en matemáticas, pero la construcción de la recursividad primitiva se remonta al teorema 126 de Richard Dedekind de su libro Was sind und was sollen die Zahlen? (1888). Este trabajo fue el primero en dar una prueba de que cierta construcción recursiva define una función única.

La aritmética recursiva primitiva fue propuesta por primera vez por Thoralf Skolem 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 motivó la necesidad de renombrar lo que hasta entonces se llamaba simplemente funciones recursivas.

Contenido relacionado

Más resultados...