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. Si la función es total, también se denomina función recursiva total (a veces se abrevia 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 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 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 .
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 en 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 demostrar que la función de Ackermann es totalmente recursiva y no primitiva.
Operadores (el dominio de una función definida por un operador es el conjunto de los 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):