GUÍA 07-09-26 Teoría de la Computación

NE111 · lunes 07/09/2026 · 16:00-17:15 · Sesión 9

Funciones recursivas primitivas y μ-recursión

FORMALIZAR LA COMPUTABILIDAD SIN MÁQUINAS

Gödel y Kleene definieron qué es una función computable partiendo solo de funciones básicas y reglas de construcción, sin hablar de máquinas. Es el camino alternativo al de Turing y llega al mismo lugar.

LAS FUNCIONES INICIALES

• Cero: Z(n) = 0.
• Sucesor: S(n) = n + 1.
• Proyección: Pᵢ(x₁,…,xₙ) = xᵢ.

LAS REGLAS DE CONSTRUCCIÓN

• Composición — combinar funciones ya construidas aplicando unas al resultado de otras.
• Recursión primitiva — definir f(0) directamente y f(n+1) en términos de f(n).

QUÉ SE OBTIENE CON ESO

Las funciones recursivas primitivas. Incluyen suma, producto, potencia, factorial, resta acotada, comparaciones y prácticamente todo lo que uno escribiría con ciclos for anidados de cota conocida.

LA PROPIEDAD CLAVE Y SU LÍMITE

Toda función recursiva primitiva termina siempre, para cualquier entrada. Eso suena deseable y es justamente lo que las hace insuficientes: si toda función de la clase termina, la clase no puede contener a las funciones que a veces no terminan, y esas también son computables.

LA FUNCIÓN DE ACKERMANN

Es computable, siempre termina, y no es recursiva primitiva. Crece más rápido que cualquier función construible con recursión primitiva. Su existencia demuestra que la clase se queda corta y motiva la siguiente regla.

MINIMIZACIÓN O Μ-RECURSIÓN

μy[f(x,y) = 0] es el menor y que hace cero a f. Se implementa buscando desde y = 0 hacia arriba. Si tal y existe, la búsqueda termina; si no existe, la búsqueda no termina nunca.

Ahí entra la posibilidad de no terminar, que es exactamente lo que faltaba. Agregando μ a las funciones recursivas primitivas se obtienen las funciones μ-recursivas o recursivas generales.

EL TEOREMA DE EQUIVALENCIA

Una función es μ-recursiva si y solo si es computable por una máquina de Turing. Dos definiciones que no se parecen en nada resultan describir exactamente la misma clase. Es el resultado que sostiene la tesis de Church-Turing.

LA LECCIÓN DE FONDO

Para capturar toda la computabilidad hay que aceptar la posibilidad de no terminar. No es un accidente ni un descuido del modelo: es una condición necesaria, y de ahí sale directamente el bloque de complejidad y el problema de Halting.

EJERCICIO

Construir la suma y el producto a partir de las funciones iniciales; explicar por qué la división entera requiere minimización.