Funciones Recursivas: Primitivas y Generales en Teoría de la Recursión
Definición de Funciones Recursivas
Las funciones recursivas son una clase fundamental de funciones computables definidas formalmente dentro de la teoría de la recursión. Se dividen en dos tipos principales:
- Funciones recursivas primitivas: Son aquellas que pueden definirse a partir de funciones básicas mediante composición y recursión primitiva.
- Funciones recursivas generales: Extienden el concepto de funciones recursivas primitivas al incluir el esquema de minimización (búsqueda acotada por una condición de parada).
Funciones Recursivas Primitivas
Las funciones recursivas primitivas son construidas a partir de las siguientes funciones básicas:
- Función cero: \(Z(n) = 0\)
- Función sucesor: \(S(n) = n + 1\)
- Funciones proyección: \(P^m_i(x_1, \dots, x_m) = x_i\)
A partir de estas, se pueden generar nuevas funciones usando:
- Composición: Si \(g, h_1, \dots, h_k\) son recursivas primitivas, entonces f(x1,…,xm)=g(h1,…,hk)f(x_1, \dots, x_m) = g(h_1, \dots, h_k) también lo es.
- Recursión primitiva: Si \(g(x_1, \dots, x_m)\) y \(h(x_1, \dots, x_m, y)\) son recursivas primitivas, entonces la función definida por: \(f(x_1, \dots, x_m, 0) = g(x_1, \dots, x_m)\) \(f(x_1, \dots, x_m, y+1) = h(x_1, \dots, x_m, y, f(x_1, \dots, x_m, y))\) también es recursiva primitiva.
Ejemplo: La función suma definida por: $$\Large Suma(x,0) = x, \quad Suma(x,y+1) = S(Suma(x,y)) $$
es recursiva primitiva.
Funciones Recursivas Generales
Las funciones recursivas generales se obtienen al agregar la minimización \mu \ a las funciones recursivas primitivas. Formalmente, si \(g(x_1, \dots, x_m, y)\) es una función recursiva total, se define: $$\Large f(x_1, \dots, x_m) = \mu y [g(x_1, \dots, x_m, y) = 0] $$
si existe algún /(y/) tal que /(g(x_1, \dots, x_m, y) = 0/), tomando el menor /(y/) que satisface esta condición.
Ejemplo: La función de Ackermann es recursiva general pero no primitiva.
Propiedades y Aplicaciones
- Las funciones recursivas primitivas son totalmente computables, mientras que las generales pueden ser parcialmente computables.
- La clase de funciones computables coincide con las funciones recursivas generales.
- La minimización introduce la posibilidad de no terminación, lo que permite modelar problemas indecidibles.