Función recursiva general

Una de varias definiciones equivalentes de una función computable

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, así como formal . Si la función es total, también se le llama función recursiva total (a veces abreviada como función recursiva ). ^[1] En la teoría de la computabilidad , se muestra que las funciones μ-recursivas son precisamente las funciones que pueden ser calculadas por las máquinas de Turing ^{[2] [4]} (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 pueden calcularse mediante algoritmos de Markov .

El subconjunto de todas las funciones recursivas totales 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 único 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 de minimización μ .

La clase más pequeña de funciones que incluye 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.

Funciones primitivas o "básicas":

1. Funciones constantes C^kn
   _​: Para cada número natural n y cada k

   ${\displaystyle C_{n}^{k}(x_{1},\ldots ,x_{k})\ {\stackrel {\mathrm {def} }{=}}\ n}$

   Las definiciones alternativas utilizan en cambio una función cero 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.

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 los valores de los argumentos de modo que cada aplicación de función que debe realizarse durante el cálculo proporcione un resultado bien definido):

1. Operador de composición (también llamado operador de sustitución ): Dadas una función m-aria y m funciones k-arias : ${\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})).}$

   Esto significa que está definido sólo si y están todos definidos. ${\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 recursión primitiva ρ : Dada la función k -aria y la función k +2 -aria : ${\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 -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}}}$

   Esto significa que se define sólo si y se definen para todos ${\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 aria ( k +1) , la función aria k se define por: ${\displaystyle f(y,x_{1},\ldots ,x_{k})\,}$ ${\displaystyle \mu (f)}$

   ${\displaystyle {\begin{aligned}\mu (f)(x_{1},\ldots ,x_{k})=z{\stackrel {\mathrm {def} }{\iff }}\ f(i,x_{1},\ldots ,x_{k})&>0\quad {\text{for}}\quad i=0,\ldots ,z-1\quad {\text{and}}\\f(z,x_{1},\ldots ,x_{k})&=0\quad \end{aligned}}}$

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. ${\displaystyle \mu (f)}$ ${\displaystyle (x_{1},\ldots ,x_{k}).}$

Mientras que algunos libros de texto utilizan el operador μ como se define aquí, ^{[5] [6]} otros como ^{[7] [8]} exigen que el operador μ se aplique a funciones totales f únicamente. Aunque esto restringe el operador μ en comparación con la definición dada aquí, la clase de funciones recursivas μ sigue siendo la misma, como se desprende del Teorema de la forma normal de Kleene (ver más abajo). ^{[5] [6]} La única diferencia es que resulta 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. ^[7]

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 cumple si y sólo 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

Se pueden encontrar ejemplos que no involucran al operador de minimización en Función recursiva primitiva#Ejemplos .

Los siguientes ejemplos pretenden simplemente 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.

• La raíz cuadrada entera de x se puede definir como el mínimo z tal que . Utilizando el operador de minimización, una definición recursiva general es , donde Not , Gt y Mul son negación lógica , mayor que y multiplicación, ^[9] respectivamente. De hecho, es ${\displaystyle (z+1)^{2}>x}$ ${\displaystyle \operatorname {Isqrt} =\mu (\operatorname {Not} \circ \operatorname {Gt} \circ (\operatorname {Mul} \circ (S\circ P_{1}^{2},S\circ P_{1}^{2}),P_{2}^{2}))}$ ${\displaystyle (\operatorname {Not} \circ \operatorname {Gt} \circ (\operatorname {Mul} \circ (S\circ P_{1}^{2},S\circ P_{1}^{2}),P_{2}^{2}))\;(z,x)=(\lnot S(z)*S(z)>x)}$0 si, y sólo si, se cumple. Por tanto, el mínimo z es el que se cumple. El conector de negación Not es necesario ya que Gt codifica la verdad mediante ${\displaystyle S(z)*S(z)>x}$ ${\displaystyle \operatorname {Isqrt} (x)}$ ${\displaystyle S(z)*S(z)>x}$ 1 , mientras μ busca0 .

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

• ^{[ ejemplo necesario ]}

Función recursiva total

Una función recursiva general se llama función recursiva total si está definida para cada entrada o, de manera equivalente, si puede calcularse mediante 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 establece 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 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 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 (T)(e,x_{1},\ldots ,x_{k}))}$.

El número e se llama índice o número de Gödel para la función f . ^{[10] : 52–53} Una consecuencia de este resultado es que cualquier función μ-recursiva se puede definir 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 universal de Turing : ${\displaystyle U}$

Construir U es escribir la definición de una función recursiva general U(n, x) que interprete correctamente el número n y calcule 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 construir la máquina universal de Turing ^[11].

Simbolismo

En la literatura se utilizan varios simbolismos diferentes. Una ventaja de utilizar 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, la cadena de parámetros x ₁ , ..., x _n se abrevia como x :

• Función constante : Kleene usa " C^nq
  _​( x ) = q " y Boolos-Burgess-Jeffrey (2002) (BBJ) utilizan 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 sucesora : Kleene usa x' y S para "Sucesor". Como "sucesor" se considera primitivo, la mayoría de los textos utilizan 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) utiliza " 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 ₁ a x _n :

Ud.ⁿ
_yo( x ) = identificaciónⁿ
_yo( x ) = x _yo

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

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

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

h( x ) = S^m
_​(g, f ₁ , ... , f _m )

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

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

• Recursión 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))

R2 { ^U1
₁(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. Ud.¹
   ₁(un) = un
3. Ud.³
   ₂( b, c, a ) = c
4. gramo(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

Ver también

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

Referencias

1. "Funciones recursivas". La Enciclopedia de Filosofía de Stanford . Laboratorio de Investigación en Metafísica, Universidad de Stanford. 2021.
2. Enciclopedia de Filosofía de Stanford , Funciones recursivas de entrada, Sección 1.7: "[La clase de funciones recursivas μ] resulta coincidir con la clase de funciones computables de Turing introducidas por Alan Turing, así como con la clase de λ -funciones definibles introducidas por Alonzo Church " .
3. Kleene, Stephen C. (1936). "λ-definibilidad y recursividad". Revista de Matemáticas de Duke . 2 (2): 340–352. doi :10.1215/s0012-7094-36-00227-2.
4. Turing, Alan Mathison (diciembre de 1937). "Computabilidad y λ-Definibilidad". Revista de Lógica Simbólica . 2 (4): 153–163. doi :10.2307/2268280. JSTOR  2268280. S2CID  2317046.Esquema de prueba en la página 153: ^[3] ${\displaystyle \lambda {\mbox{-definable}}}$ ${\displaystyle {\stackrel {triv}{\implies }}}$ ${\displaystyle \lambda {\mbox{-}}K{\mbox{-definable}}}$ ${\displaystyle {\stackrel {160}{\implies }}}$ ${\displaystyle {\mbox{Turing computable}}}$ ${\displaystyle {\stackrel {161}{\implies }}}$ ${\displaystyle \mu {\mbox{-recursive}}}$ ${\displaystyle {\stackrel {Kleene}{\implies }}}$ ${\displaystyle \lambda {\mbox{-definable}}}$
5. Enderton, HB, Introducción matemática a la lógica, Academic Press, 1972
6. Boolos, GS, Burgess, JP, Jeffrey, RC, Computabilidad y lógica, Cambridge University Press, 2007
7. Jones, ND, Computabilidad y complejidad: desde una perspectiva de programación, The MIT Press, Cambridge, Massachusetts, Londres, Inglaterra, 1997
8. Kfoury, AJ, RN Moll y MA Arbib, Un enfoque de programación para la computabilidad, 2.ª ed., Springer-Verlag, Berlín, Heidelberg, Nueva York, 1982
9. definido en Función recursiva primitiva#Junctors , Función recursiva primitiva#Predicado de igualdad y Función recursiva primitiva#Multiplicación
10. Stephen Cole Kleene (enero de 1943). "Predicados y cuantificadores recursivos" (PDF) . Transacciones de la Sociedad Matemática Estadounidense . 53 (1): 41–73. doi : 10.1090/S0002-9947-1943-0007371-8 .
11. Minsky 1972, págs.189.

• Kleene, Stephen (1991) [1952]. Introducción a las Metamatemáticas . Walters-Noordhoff y Holanda Septentrional. ISBN 0-7204-2103-9.
• Soare, R. (1999) [1987]. Conjuntos y grados recursivamente enumerables: un estudio de funciones computables y conjuntos generados computablemente. Springer-Verlag. ISBN 9783540152996.
• Minsky, Marvin L. (1972) [1967]. Computación: Máquinas finitas e infinitas . Prentice Hall. págs. 210–5. ISBN 9780131654495.

En las páginas 210-215, Minsky muestra cómo crear el operador μ utilizando el modelo de máquina de registro , demostrando así su equivalencia con las funciones recursivas generales.

• Boolos, George ; Burgess, Juan ; Jeffrey, Richard (2002). "6.2 Minimización". Computabilidad y Lógica (4ª ed.). Prensa de la Universidad de Cambridge. págs. 70–71. ISBN 9780521007580.

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.