El conjunto de las "funciones recursivas parciales" está definido como el más pequeño conjunto de funciones parciales con cualquier número de argumentos de los naturales en los naturales que contiene el cero, el sucesor y las funciones de proyección, tales que la composición, la recursión primitiva y la búsqueda no acotada son operaciones cerradas en este conjunto.