Función recursiva general - General recursive function

En lógica matemática e informática , una función recursiva general , una función recursiva parcial o una función recursiva μ es una función parcial de números naturales a números naturales que es "computable" en un sentido intuitivo. 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 muestra que las funciones recursivas μ son precisamente las funciones que pueden ser calculadas por 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 equivalentes de funciones son las funciones del cálculo lambda y las funciones que pueden ser calculadas por algoritmos de Markov .

El subconjunto de todos los totales funciones recursivas con valores en {0,1} se conoce en teoría de la complejidad computacional como la clase de la 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 está cerrada bajo composición, recursividad primitiva y el operador μ .

La clase más pequeña de funciones, incluidas las funciones iniciales y cerrada en 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 probar que la función de Ackermann es totalmente recursiva y no primitiva.

Funciones primitivas o "básicas":

1. Funciones constantes C^k
   _n: Para cada número natural y todas las definiciones alternativas, utilice en su lugar una función cero como función primitiva que siempre devuelve cero, y construyó las funciones constantes a partir de la función cero, la función sucesora y el operador de composición.${\ Displaystyle n \,}$${\ Displaystyle k \,}$
       ${\ Displaystyle C_ {n} ^ {k} (x_ {1}, \ ldots, x_ {k}) {\ stackrel {\ mathrm {def}} {=}} n}$
   
2. Función sucesora S:
       ${\ Displaystyle S (x) {\ stackrel {\ mathrm {def}} {=}} x + 1 \,}$
3. Función de proyección (también llamada función de identidad ): para todos los números naturales tales que :${\ 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} \ ,.}$

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

1. Operador de composición (también llamado operador de sustitución ): Dada una función m-aria y m funciones k-arias : Esto significa que se define solo si y están todas definidas.${\ 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 {donde}} \ quad f (x_ {1}, \ ldots, x_ {k}) = h (g_ {1} (x_ {1}, \ ldots, x_ {k}), \ ldots, g_ {m} (x_ {1}, \ ldots, x_ {k})).}$
   ${\ Displaystyle f (x_ {1}, \ ldots, x_ {k})}$${\ Displaystyle g_ {1} (x_ {1}, \ ldots, x_ {k}), \ ldots, g_ {m} (x_ {1}, \ ldots, x_ {k}),}$${\ Displaystyle h (g_ {1} (x_ {1}, \ ldots, x_ {k}), \ ldots, g_ {m} (x_ {1}, \ ldots, x_ {k}))}$
2. Operador de recursividad primitiva : Dada la función k -ary y la función k +2 -ary : Esto significa que se define solo si y se definen para todos${\ Displaystyle \ rho \,}$${\ Displaystyle g (x_ {1}, \ ldots, x_ {k}) \,}$${\ Displaystyle h (y, z, x_ {1}, \ ldots, x_ {k}) \,}$
       ${\ displaystyle {\ begin {alineado} \ rho (g, h) & {\ stackrel {\ mathrm {def}} {=}} f \ quad {\ text {donde la función k + 1 -ary}} f { \ text {está definido 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 {alineado}}}$
   ${\ Displaystyle f (y, x_ {1}, \ ldots, x_ {k})}$${\ Displaystyle g (x_ {1}, \ ldots, x_ {k})}$${\ Displaystyle h (z, f (z, x_ {1}, \ ldots, x_ {k}), x_ {1}, \ ldots, x_ {k})}$${\ Displaystyle z <y.}$
3. Operador de minimización : Dada una función ( k +1) -ary , la función k -ary se define mediante: Intuitivamente, la minimización busca —comenzando la búsqueda desde 0 y avanzando hacia arriba— el argumento más pequeño que hace que la función devuelva cero; si no existe tal argumento, o si uno encuentra un argumento para el cual f no está definido, entonces la búsqueda nunca termina y no está definida para el argumento ( Nota : Mientras que algunos libros de texto usan el operador μ como se define aquí, otros como Exigir que el operador μ se aplique solo a funciones totales . 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 sigue del teorema de 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).${\ Displaystyle \ mu \,}$${\ Displaystyle f (y, x_ {1}, \ ldots, x_ {k}) \,}$${\ Displaystyle \ mu (f)}$
       ${\ Displaystyle {\ begin {alineado} \ mu (f) (x_ {1}, \ ldots, x_ {k}) = z {\ stackrel {\ mathrm {def}} {\ iff}} \ f (i, x_ {1}, \ ldots, x_ {k}) &> 0 \ quad {\ text {para}} \ quad i = 0, \ ldots, z-1 \ quad {\ text {y}} \\ f ( z, x_ {1}, \ ldots, x_ {k}) & = 0 \ quad \ end {alineado}}}$
   ${\ Displaystyle \ mu (f)}$${\ Displaystyle (x_ {1}, \ ldots, x_ {k}).}$
   ${\ Displaystyle f}$

El operador de igualdad fuerte se puede utilizar para comparar funciones recursivas μ parciales. Esto se define para todas las funciones parciales f y g de modo que ${\ Displaystyle \ simeq}$

${\ Displaystyle f (x_ {1}, \ ldots, x_ {k}) \ simeq g (x_ {1}, \ ldots, x_ {l})}$

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

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 puede ser calculada por una máquina de Turing total . No hay forma de saber computablemente si una función recursiva general dada 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 las máquinas de Turing que no terminan para ciertas entradas y un resultado indefinido para esa entrada en la función recursiva parcial correspondiente. El operador de búsqueda ilimitada no se puede definir mediante las reglas de la 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 y tal que para cualquier función recursiva μ con k variables libres hay una e tal que ${\ Displaystyle U (y) \!}$${\ Displaystyle T (y, e, x_ {1}, \ ldots, x_ {k}) \!}$${\ Displaystyle f (x_ {1}, \ ldots, x_ {k}) \!}$

${\ Displaystyle f (x_ {1}, \ ldots, x_ {k}) \ simeq U (\ mu y \, T (y, e, x_ {1}, \ ldots, x_ {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 μ puede definirse utilizando una única instancia del operador μ aplicado a una función recursiva primitiva (total).

Minsky observa que lo definido anteriormente es, en esencia, el equivalente recursivo μ de la máquina de Turing universal : ${\ Displaystyle U}$

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

Simbolismo

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

• Función constante : Kleene usa "Cⁿ
  _q( x ) = q "y Boolos-Burgess-Jeffrey (2002) (BBJ) usan la abreviatura" const _n ( x ) = n ":

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

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

• Función de sucesor : Kleene usa x 'y S para "Sucesor". Como "sucesor" se considera primitivo, la mayoría de los textos usan el apóstrofe de la siguiente manera:

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

• Función de identidad : Kleene (1952) usa "Uⁿ
  _yo"para indicar la función de identidad sobre las variables x _i ; BBJ usa la función de identidad idⁿ
  _yosobre las variables x ₁ ax _n :

Uⁿ
_yo( x ) = idⁿ
_yo( x ) = x _yo

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

• Operador de composición (sustitución) : Kleene usa una S en negrita^m
  _n(¡No confundir con su S de "sucesor" ! ). El superíndice "m" se refiere a la m ^ésima función "f _m ", mientras que el subíndice "n" se refiere a la n ^ésima variable "x _n ":

Si se nos da h ( x ) = g (f ₁ ( x ), ..., f _m ( x ))

h ( x ) = Sⁿ
_m(sol, f ₁ , ..., f _m )

De manera similar, pero sin los subíndices y superíndices, BBJ escribe:

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

• Recursividad primitiva : Kleene usa el símbolo " R ⁿ (paso base, paso de inducción)" donde n indica el número de variables, BBJ usa "Pr (paso base, paso de inducción) ( x )". Dado:

• paso base: h (0, x ) = f ( x ), y
• paso de inducción: h (y + 1, x ) = g (y, h (y, x ), x )

Ejemplo: definición de recursividad primitiva de a + 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 ayb). Empieza con 3 funciones iniciales

1. S (a) = a '
2. U¹
   ₁(a) = a
3. U³
   ₂(b, c, a) = c
4. g (segundo, 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 de

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

Ver también

• Teoría de la recursividad
• Recursividad
• Recursión (informática)

Referencias

enlaces externos

• Entrada de la Enciclopedia de Filosofía de Stanford
• Un compilador para transformar una función recursiva en una máquina de Turing equivalente