Siguiente: Conceptos básicos Un nivel arriba: COMPUTABILIDAD Y COMPLEJIDAD Anterior: Primera lista de programas

Funciones recursivas primitivas

En este capítulo haremos una presentación formal de las funciones recursivas primitivas. Veremos que todas ellas son computables. Introduciremos la jerarquía de Grzegorczyk como un ejemplo de una jerarquía de complejidad. En el primer nivel de esta jerarquía están las así llamadas funciones elementales. Mostraremos que éstas pueden ser definidas, siempre de manera equivalente, partiendo de diversos esquemas de composición. Finalmente, la función de Ackermann nos proveerá de un ejemplo de una función que, siendo computable, no es recursiva primitiva.