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 .
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":
Funciones constantes Ck- n:Para cada número natural n y cada k
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.
Función sucesora S:
Función de proyección (también llamada función identidad ): Para todos los números naturales tales que :
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):
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 sólo si y están todos definidos.
Operador de recursión primitiva ρ : Dada la función k -aria y la función k +2 -aria :
Esto significa que se define solo si y están definidos para todos
Operador de minimización μ : Dada una función ( k +1)-aria , la función k -aria se define por:
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.
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
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.
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, es0 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 por1 , 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.
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
This section needs expansion. You can help by adding to it. (February 2010)
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
.
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).
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 1 , ..., x n se abrevia como x :
Función constante : Kleene utiliza "Cno q( x ) = q " y Boolos-Burgess-Jeffrey (2002) (BBJ) utilizan la abreviatura " const n ( x ) = n ":
por ejemplo C7 13(r, s, t, u, v, w, x) = 13
p. ej. constante 13 (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 "Uyo " para indicar la función identidad sobre las variables x i ; BBJ utiliza la función identidad idyo sobre las variables x 1 a x n :
túyo ( x ) = identificaciónyo ( x ) = x i
por ejemplo U7 3= identificación7 3(r, s, t, u, v, w, x) = t
Operador de composición (sustitución) : Kleene utiliza una S en negritam -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 1 ( x ), ... , f m ( x ) )
h( x ) = Snuevo (g, f 1 , ... , f m )
De manera similar, pero sin los subíndices y superíndices, BBJ escribe:
h( x' )= Cn[g, f 1 ,..., f m ]( x )
Recursión primitiva : Kleene utiliza el símbolo " R n (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 = U1 1(a)
paso de inducción: f( b' , a ) = ( f ( b, a ) )' = g( b, f( b, a), a ) = g( b, c, a ) = c' = S(U3 2(b, c, a))
R2 { Tu1 1(a), S [ (U3 2(b, c, a) ] }
Pr{ U1 1(a), S[(U3 2(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.
S(a) = a'
tú1 1(a) = un
tú3 2(b, c, a) = c
g(b, c, a) = S(U3 2(b, c, a)) = c'
paso base: h( 0, a ) = U1 1(a)
paso de inducción: h( b', a ) = g( b, h( b, a ), a )
^ "Funciones recursivas". The Stanford Encyclopedia of Philosophy . Laboratorio de investigación en metafísica, Universidad de Stanford. 2021.
^ 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 " .
^ ab Enderton, HB, Una introducción matemática a la lógica, Academic Press, 1972
^ ab Boolos, GS, Burgess, JP, Jeffrey, RC, Computabilidad y lógica, Cambridge University Press, 2007
^ ab Jones, ND, Computabilidad y complejidad: desde una perspectiva de programación, The MIT Press, Cambridge, Massachusetts, Londres, Inglaterra, 1997
^ 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
^ 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 .
Soare, R. (1999) [1987]. Conjuntos y grados enumerables recursivamente: un estudio de funciones computables y conjuntos generados computacionalmente. Springer-Verlag. ISBN9783540152996.
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.