En matemáticas (e informática teórica) la noción de función recursiva (o funciones recursivas [math] \ mu [/ math], como también se las llama) se refiere a una clase particular de funciones parciales que mapean tuplas de números naturales a un número natural. La clase contiene aquellas funciones parciales que se pueden considerar computables, y se puede demostrar que estas son exactamente las funciones que puede calcular una máquina de Turing, suponiendo una codificación razonable de números en cintas de Turing. La clase es una extensión de la clase de funciones recursivas primitivas , y estrictamente más grande que esta clase.
La definición de la clase procede primero definiendo ciertas funciones básicas que están en la clase y luego definiendo operadores que nos permiten construir inductivamente funciones más complejas a partir de las existentes.
Funciones recursivas básicas:
- ¿Qué es lo mejor que puedes hacer si te quedas atrapado en un problema en SPOJ?
- Cómo encontrar la mediana de m matrices ordenadas
- ¿Hay algún libro que tenga todos los códigos para todas las estructuras de datos? ¿Al menos para todas las estructuras de datos de árbol?
- El comportamiento emergente se encuentra en el núcleo de las ciencias físicas y de la vida: posiblemente por conveniencia computacional. ¿La teoría de la complejidad ofrece ideas aquí?
- ¿Cuál es la lógica detrás de los algoritmos de ajuste de aprendizaje automático?
- Funciones cero : para cada número [matemática] n [/ matemática] hay una función [matemática] 0 ^ n: \ Bbb {N} ^ n \ to \ Bbb {N} [/ matemática] tal que [matemática] 0 ^ n (x_1, \ ldots, x_n) = 0 [/ math] para todos los números [math] x_1, \ ldots, x_n [/ math].
- Sucesor : hay una función [matemática] S: \ Bbb {N} \ to \ Bbb {N} [/ matemática] tal que [matemática] S (x) = x + 1 [/ matemática].
- Proyección : por cada dos números naturales [matemática] n [/ matemática] y [matemática] i [/ matemática] st [matemática] 1 \ leq i \ leq n [/ matemática], hay una función [matemática] \ pi ^ n_i: \ Bbb {N} ^ n \ to \ Bbb {N} [/ math] tal que [math] \ pi ^ n_i (x_1, \ ldots, x_n) = x_i [/ math] para todos los números [math] x_1 , \ ldots, x_n [/ math].
Operadores para construir la función recursiva:
- Composición : dada una función [matemática] f: \ Bbb {N} ^ n \ to \ Bbb {N} [/ matemática] y funciones [matemática] g_1: \ Bbb {N} ^ m \ to \ Bbb {N}, \ ldots, g_n: \ Bbb {N} ^ m \ to \ Bbb {N} [/ math] hay una función [math] f \ circ (g_1, \ ldots, g_n): \ Bbb {N} ^ m \ a \ Bbb {N} [/ math] tal que si [math] h = f \ circ (g_1, \ ldots, g_n) [/ math] entonces [math] h (\ bar {x}) = f (g_1 ( \ bar {x}), \ ldots, g_n (\ bar {x})) [/ math] donde [math] \ bar {x} [/ math] denota [math] x_1, \ ldots, x_m [/ math] .
- Recurrencia primitiva : funciones dadas [matemáticas] f: \ Bbb {N} ^ n \ to \ Bbb {N} [/ matemáticas] y [matemáticas] g: \ Bbb {N} ^ {n + 2} \ a \ Bbb { N} [/ math] hay una función [math] \ rho (f, g): \ Bbb {N} ^ {n + 1} \ to \ Bbb {N} [/ math] tal que si [math] h = \ rho (f, g) [/ math] entonces, suponiendo que [math] \ bar {x} [/ math] denota [math] x_1, \ ldots, x_n [/ math], sostiene que
- [matemática] h (0, \ bar {x}) = f (\ bar {x}) [/ matemática], y
- [matemática] h (y + 1, \ bar {x}) = g (y, h (y, \ bar {x}), \ bar {x}) [/ matemática].
- Minimización : dada una función [matemática] f: \ Bbb {N} ^ {n + 1} \ a \ Bbb {N} [/ matemática] hay una función [matemática] \ mu (f): \ Bbb {N} ^ {n} \ to \ Bbb {N} [/ math] tal que si [math] h = \ mu (f) [/ math] entonces, suponiendo que [math] \ bar {y} [/ math] denota [math ] y_1, \ ldots, y_n, [/ math] el resultado de [math] h (\ bar {y}) [/ math] es el número natural más pequeño [math] z [/ math] tal que [math] f ( z, \ bar {y}) = 0 [/ matemáticas]. Si no existe dicho número natural, entonces [matemática] h (\ bar {y}) [/ matemática] no está definida.
La clase de funciones recursivas se define entonces como la clase más pequeña que contiene la función recursiva básica y se cierra bajo los operadores dados para construir funciones recursivas. En otras palabras, contiene las funciones que se pueden construir a partir de las funciones recursivas básicas y utilizando los operatros dados un número finito de veces.
Algunas observaciones rápidas:
- Si omitimos el operador de minimización, obtenemos la definición de funciones recursivas primitivas. Observe que este operador es el único que nos permite construir funciones parciales que a partir de funciones totales. De hecho, la clase de funciones recursivas primitivas contiene solo funciones totales.
- La clase de funciones recursivas primitivas es estrictamente más pequeña que la clase de funciones recursivas. Esto no solo es cierto porque solo contiene funciones totales, sino que también hay funciones recursivas totales que no son recursivas primitivas. Un ejemplo bien conocido de esto es la función de Ackermann.
