Siguiente: Una escala de funciones Un nivel arriba: Funciones recursivas primitivas Anterior: Clase de funciones elementales

Jerarquía de Grzegorczyk

Veremos en esta sección que la clase de las funciones recursivas primitivas contiene una sucesión de funciones tal que cada función en ella tiene un crecimiento sustantivamente más complejo que la función que la precede en la sucesión. Tal escala de funciones nos permitirá definir a la jerarquía de Grzegorczyk en ${\cal FRP}$, con la cual podremos clasificar a las funciones recursivas primitivas en diversos ``niveles de complejidad''.