Siguiente: Funciones recursivas Un nivel arriba: COMPUTABILIDAD Y COMPLEJIDAD Anterior: Universalidad en programas-while

Teoría de la recursividad

Presentamos en este capítulo a las funciones recursivas, las cuales han de coincidir con las funciones computables. Así, veremos una presentación alternativa de la noción de computabilidad. Las funciones recursivas poseen una función universal y, en la clase que conforman, es irresoluble el ``problema de la parada'', es decir, el decidir cuándo el cálculo de una función recursiva ha de converger o no ante una instancia dada.