Función recursiva general

Una de varias definiciones equivalentes de una función computable

En lógica matemática y ciencias de la computación , 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 ). ^[1] En teoría de la computabilidad , se muestra que las funciones μ-recursivas son precisamente las funciones que pueden ser calculadas por máquinas de Turing ^{[2] [4]} (este es uno de los teoremas que respalda 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 toda función recursiva total es una función recursiva primitiva; 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 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 la 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, recursión 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 recursión 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 recursiva total y no primitiva.

Funciones primitivas o "básicas":

1. Funciones constantes C^k-
   _n: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 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 tales que cada aplicación de la 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 ): Dada 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 se define 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 solo si y están definidos 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 ( k +1)-aria , la función k -aria 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 continuando 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 μ tal como se define aquí, ^{[5] [6]} otros ^{[7] [8]} exigen que el operador μ se aplique únicamente a funciones totales f . Aunque esto restringe el operador μ en comparación con la definición dada aquí, la clase de funciones μ-recursivas sigue siendo la misma, lo que se desprende del Teorema de la Forma Normal de Kleene (véase más abajo). ^{[5] [6]} 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. ^[7]

La relación 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 el operador de minimización en Función recursiva primitiva#Ejemplos .

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

• La raíz cuadrada entera de x se puede definir como el menor 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 lo tanto, es el menor z tal que se cumple. El conjuntor de negación Not es necesario ya que Gt codifica la verdad por ${\displaystyle S(z)*S(z)>x}$ ${\displaystyle \operatorname {Isqrt} (x)}$ ${\displaystyle S(z)*S(z)>x}$ 1 , mientras que μ 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 denomina función recursiva total si está definida para cada entrada o, equivalentemente, si puede calcularse mediante una máquina de Turing total . No hay forma de determinar computacionalmente si una función recursiva general dada es total (consulte el 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 ilimitado no es definible por las reglas de recursión primitiva, ya que estas 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 existen funciones recursivas primitivas y tales que para cualquier función μ-recursiva con k variables libres existe 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 denomina í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 de Turing universal : ${\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 la construcción de la máquina de Turing universal ^[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 mediante la "anidación" de los operadores uno dentro de 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 utiliza "C^no
  _q( 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

p. ej. constante ₁₃ (r, s, t, u, v, w, x) = 13

• Función sucesora : Kleene utiliza x' y S para "sucesor". Como "sucesor" se considera primitivo, la mayoría de los textos utilizan el apóstrofo de la siguiente manera:

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

• Función identidad : Kleene (1952) utiliza "U^yo
  _​" para indicar la función identidad sobre las variables x _i ; BBJ utiliza la función identidad id^yo
  _​sobre las variables x ₁ a x _n :

tú^yo
_​( x ) = identificación^yo
_​( x ) = x _i

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^m
  _-n(¡no debe confundirse 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 nos dan h( x )= g( f ₁ ( x ), ... , f _m ( x ) )

h( x ) = S^nuevo
_​(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 utiliza el símbolo " R ⁿ (paso base, paso de inducción)", donde n indica el número de variables; BBJ utiliza "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 recursión 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 ^{ Tu¹
₁(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 tres funciones iniciales.

1. S(a) = a'
2. tú¹
   ₁(a) = un
3. tú³
   ₂(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 = R2 [ ^U1
₁, S³
₁(S, U³
₂) ]

Ejemplos

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

Véase también

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

Referencias

1. "Funciones recursivas". The Stanford Encyclopedia of Philosophy . Laboratorio de investigación en metafísica, Universidad de Stanford. 2021.
2. Stanford Encyclopedia of Philosophy , Entrada Funciones recursivas, Sect.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". Duke Mathematical Journal . 2 (2): 340–352. doi :10.1215/s0012-7094-36-00227-2.
4. Turing, Alan Mathison (diciembre de 1937). "Computabilidad y λ-definibilidad". Journal of Symbolic Logic . 2 (4): 153–163. doi :10.2307/2268280. JSTOR  2268280. S2CID  2317046.Esquema de la 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, Una 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#Uniones , 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) . Transactions of the American Mathematical Society . 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 & North-Holland. ISBN 0-7204-2103-9.
• Soare, R. (1999) [1987]. Conjuntos y grados enumerables recursivamente: un estudio de funciones computables y conjuntos generados computacionalmente. Springer-Verlag. ISBN 9783540152996.
• Minsky, Marvin L. (1972) [1967]. Computación: máquinas finitas e infinitas . Prentice-Hall. pp. 210–5. ISBN 9780131654495.

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

• Boolos, George ; Burgess, John ; Jeffrey, Richard (2002). "6.2 Minimización". Computabilidad y lógica (4.ª ed.). Cambridge University Press. 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