Función recursiva general

En lógica matemática e informática, una función recursiva general, función recursiva parcial o función μ-recursiva es una función parcial de números naturales a números naturales que es "computable" en un sentido intuitivo, así como en uno formal. Si la función es total, también se denomina función recursiva total (a veces abreviada como función recursiva). En la teoría de la computabilidad se demuestra que las funciones μ-recursivas son precisamente las funciones que pueden ser calculadas por las máquinas de Turing (este es uno de los teoremas que sustenta la tesis de Church-Turing). Las funciones μ-recursivas están estrechamente relacionadas con las funciones recursivas primitivas, y su definición inductiva (a continuación) se basa en la de las funciones recursivas primitivas. Sin embargo, no todas las funciones recursivas totales son funciones recursivas primitivas; el ejemplo más famoso es la función de Ackermann.

Otras clases de funciones equivalentes son las funciones del cálculo lambda y las funciones que se pueden calcular mediante algoritmos de Markov.

El subconjunto de todas las funciones recursivas total con valores en {0,1} se conoce en la teoría de la complejidad computacional como clase de complejidad R.

Definición

Las funciones μ-recursivas (o funciones recursivas generales) son funciones parciales que toman tuplas finitas de números naturales y devuelven un solo número natural. Son la clase más pequeña de funciones parciales que incluye las funciones iniciales y se cierra bajo composición, recursividad primitiva y el operador μ.

La clase más pequeña de funciones, incluidas las funciones iniciales y cerradas bajo composición y recursividad primitiva (es decir, sin minimización), es la clase de funciones recursivas primitivas. Si bien todas las funciones recursivas primitivas son totales, esto no es cierto para las funciones recursivas parciales; por ejemplo, la minimización de la función sucesora no está definida. Las funciones recursivas primitivas son un subconjunto de las funciones recursivas totales, que son un subconjunto de las funciones recursivas parciales. Por ejemplo, se puede demostrar que la función de Ackermann es totalmente recursiva y no primitiva.

Primitivo o "básico" funciones:

1. Funciones constantes C^k
   _n: Para cada número natural n y todos k

   ${displaystyle ¿Qué? {fnK} {fnK}}} No.$

   Las definiciones alternativas usan en cambio un Función cero 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.

2. Función de éxito S:

   ${displaystyle S(x) {fnMicrosoft} } {=} x+1,}$

3. Función de proyección ${displaystyle P_{i} {k}$ (también llamado el Función de identidad): Para todos los números naturales ${displaystyle i,k}$ tales que ${displaystyle 1leq ileq k}$:

   ${displaystyle P_{i} {k}(x_{1},ldotsx_{k}) {fnMicrosoft} } {=} #$

Operadores (el dominio de una función definida por un operador es el conjunto de los valores de los argumentos de tal manera que cada aplicación de función que se debe hacer durante el cálculo proporciona un resultado bien definido):

1. Composition operator ${displaystyle circ ,}$ (también llamado el substitution operator): Dada una función m-ary ${displaystyle h(x_{1},ldotsx_{m},}$ y m k-ary funciones ${displaystyle g_{1}(x_{1},ldotsx_{k}),ldotsg_{m}(x_{1},ldotsx_{k})}$:

   ${displaystyle hcirc (g_{1},ldotsg_{m}) {fnMicrosoft} }{=} f,quad {text{where}quad f(x_{1},ldotsx_{k})=h(g_{1}(x_{1},ldotsx_{k}),ldotsg_{m}(x_{1},ldotsx_{k})). }$

   Esto significa que ${displaystyle f(x_{1},ldotsx_{k}}$ se define solamente si ${displaystyle g_{1}(x_{1},ldotsx_{k}),ldotsg_{m}(x_{1},ldotsx_{k}),}$ y ${displaystyle h(g_{1}(x_{1},ldotsx_{k}),ldotsg_{m}(x_{1},ldotsx_{k})}$ están todos definidos.

2. Operador de recursión primitiva ***: Dada la k- Función diaria ${displaystyle g(x_{1},ldotsx_{k},}$ y k+2 - función diaria ${displaystyle h(y,z,x_{1},ldotsx_{k},}$:

   ${displaystyle {begin{aligned}rho (g,h) convict {stackrel {mathrm {def}{=}} ################################################################################################################################################################################################################################################################$

   Esto significa que ${displaystyle f(y,x_{1},ldotsx_{k}}$ se define solamente si ${displaystyle g(x_{1},ldotsx_{k}}$ y ${displaystyle h(z,f(z,x_{1},ldotsx_{k}),x_{1},ldotsx_{k}}}$ se definen para todos ${displaystyle zcantarillado.}$

3. Operador de minimización μ: Dado akfunción +1)-ary ${displaystyle f(y,x_{1},ldotsx_{k},}$, el k- Función diaria ${displaystyle mu (f)}$ se define por:

   ${displaystyle {begin{aligned}mu (f)(x_{1},ldotsx_{k})=z{stackrel {fnMicrosoft}f}f(i,x_{1},ldotsx_{k} {f {text{for}quad i=0,ldotsz-1quad {text{y}f(z,x_{1},ldotsx=0} {k} {f} {f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}f}}f}f}$

Intuitivamente, la minimización busca —comenzando la búsqueda de 0 y procediendo hacia arriba— el menor argumento que hace que la función vuelva cero; si no hay tal argumento, o si se encuentra con un argumento para el cual f no se define, entonces la búsqueda nunca termina, y ${displaystyle mu (f)}$ no se define para el argumento ${displaystyle (x_{1},ldotsx_{k}).}$

Mientras que algunos libros de texto usan el operador μ como se define aquí, otros exigen que el operador μ se aplique a las funciones total f solamente. Aunque esto restringe el operador μ en comparación con la definición dada aquí, la clase de funciones recursivas μ sigue siendo la misma, que se deriva del teorema de la forma normal de Kleene (ver más abajo). La única diferencia es que se vuelve indecidible si una definición de función específica define una función μ-recursiva, ya que es indecidible si una función computable (es decir, μ-recursiva) es total.

El firme igualdad operador ${displaystyle simeq }$ se puede utilizar para comparar funciones recursivas parciales μ. Esto se define para todas las funciones parciales f y g así

${displaystyle f(x_{1},ldotsx_{k})simeq g(x_{1},ldotsx_{l})}$

se cumple si y solo si para cualquier elección de argumentos ambas funciones están definidas y sus valores son iguales o ambas funciones no están definidas.

Ejemplos

Los ejemplos que no implican el operador de minimización se pueden encontrar en Función recursiva primitiva #Examples.

Los siguientes ejemplos pretenden demostrar el uso del operador de minimización; también podrían definirse sin él, aunque de una manera más complicada, ya que todos son recursivos primitivos.

Los siguientes ejemplos definen funciones recursivas generales que no son recursivas primitivas; por lo tanto, no pueden evitar usar el operador de minimización.

Función recursiva total

Una función recursiva general se llama función recursiva total si se define para cada entrada o, de manera equivalente, si se puede calcular mediante una máquina de Turing total. No hay forma de saber de manera computable si una función recursiva general determinada es total; consulte Problema de detención.

Equivalencia con otros modelos de computabilidad

En la equivalencia de modelos de computabilidad, se traza un paralelo entre máquinas de Turing que no terminan para ciertas entradas y un resultado indefinido para esa entrada en la correspondiente función recursiva parcial. El operador de búsqueda ilimitado no se puede definir mediante las reglas de recursividad primitiva, ya que no proporcionan un mecanismo para "bucles infinitos" (valores indefinidos).

Teorema de la forma normal

Un teorema de forma normal debido a Kleene dice que para cada k hay funciones recursivas primitivas ${displaystyle U(y)!}$ y ${displaystyle T(y,e,x_{1},ldotsx_{k}!}$ tal que para cualquier función recursiva μ ${displaystyle f(x_{1},ldotsx_{k}!}$ con k variables libres hay una e tales que

${displaystyle f(x_{1},ldotsx_{k})simeq U(mu y,T(y,e,x_{1},ldotsx_{k})}$.

El número e se denomina índice o número de Gödel para la función f. Una consecuencia de este resultado es que cualquier función μ-recursiva se puede definir usando una sola instancia del operador μ aplicado a una función recursiva primitiva (total).

Minsky observa el ${displaystyle U}$ definido arriba es en esencia el equivalente μ-recursivo de la máquina de Turing universal:

Para construir U es anotar la definición de una función general-recursiva U(n, x) que interpreta correctamente el número n y calcula la función apropiada de x. para construir U directamente implicaría esencialmente la misma cantidad de esfuerzo, y esencialmente las mismas ideas, como hemos invertido en construir la máquina de Turing universal

Simbolismo

En la literatura se utilizan varios simbolismos diferentes. Una ventaja de usar el simbolismo es la derivación de una función por "anidamiento" de los operadores uno dentro del otro es más fácil de escribir en una forma compacta. A continuación, la cadena de parámetros x₁,..., x_n se abrevia como x:

• Función constante: Kleene utiliza Cⁿ
  _q()x) = q " y Boolos-Burgess-Jeffrey (2002) (B-B-J) utilizan la abreviación " const_n()x) = n ":

por ejemplo C⁷
₁₃ (r, s, t, u, v, w, x) = 13

e.g. const₁₃ (r, s, t, u, v, w, x) = 13

• Función de éxito: Kleene utiliza x' y S para "Succesor". Como se considera que el éxito es primitivo, la mayoría de los textos utilizan el apostrofe como sigue:

S(a) = a +1 =_def a', donde 1 =_def 0', 2 =_def 0 '', etc.

• Función de identidad: Kleene (1952) utiliza "Uⁿ
  _i "para indicar la función de identidad sobre las variables x_i; B-B-J use the identity function idⁿ
  _i sobre las variables x₁ a x_n:

Uⁿ
_i()x) = idⁿ
_i()x) = x_i

por ejemplo U⁷
₃ = id⁷
₃ (r, s, t, u, v, w, x) = t

• Composition (Substitution) operator: Kleene utiliza una cara audaz S^m
  _n (que no se confunda con su S por "sucesor" !). El superscript "m" se refiere al m^T de la función "f_m", mientras que el subscripto "n" se refiere a la n^T variable "x_n"

Si nos dan h(x)= g(f)₁()x),... f_m()x)

hx) Sⁿ
_m(g, f₁,... f_m)

De manera similar, pero sin los sub- y superscriptos, B-B-J escribe:

hx ')= Cn[g, f₁..._m]x)

• Recursión primitiva: Kleene utiliza el símbolo " Rⁿ(base step, induction step) "donde n indica el número de variables, B-B-J use " Pr(base step, induction step)(x)". Dado:

• paso base: h(0, x)= fx), y
• paso de inducción: h(y+1, xSí. x),x)

Ejemplo: definición de recursión primitiva de un + b:

• paso base: f(0, a) = a = U¹
  ₁a)
• paso de inducción: f(b' a) = (f (b, a)))' = g(b, f(b, a), a) = g(b, c, a) = c' = S(U)³
  ₂b, c, a))

R² U¹
₁a), S [ (U³
₂(b, c, a)

Pr{ U¹
₁a), S[ (U)³
₂(b, c, a)

Ejemplo: Kleene da un ejemplo de cómo realizar la derivación recursiva de f(b, a) = b + a (observe la inversión de las variables a y b). Comienza con 3 funciones iniciales

1. S(a) = a'
2. U¹
   ₁a) = a)
3. U³
   ₂b, c, a) = c
4. g(b, c, a) = S(U³
   ₂b, c, a) = c
5. paso base: h(0, a) = U¹
   ₁a)

paso de inducción: h(b', a) = g(b, h(b, a), a)

Llega a:

a+b = R²[U¹
₁, S³
₁(S, U³
₂)

Ejemplos

• Número de Fibonacci
• Función McCarthy 91