3.3.1      Funciones recursivas

Para definir las funciones recursivas se toma la definición de las funciones primitivas recursivas, para permitir funciones parciales, agregando el operador de búsqueda o minimización no acotadacomo sigue:

Si f(x,z1,z2,...,zn) es una función parcial sobre los naturales con n+1 argumentos x, z1,...,zn, la función μx f es la función parcial con argumentos z1,...,zn que retorna el más pequeño x tal que f(0,z1,z2,...,zn), f(1,z1,z2,...,zn), ..., f(x,z1,z2,...,zn) están todas definidas y f(x,z1,z2,...,zn) = 0, si un tal x existe; en caso contrario, μx f no está definida para los valores particulares de los argumentos z1,...,zn.

Función Factorial

 

La función factorial (símbolo: !) sólo quiere decir que se multiplican una serie de números que descienden. Ejemplos:

 

  • 4! = 4 × 3 × 2 × 1 = 24
  • 7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040
  • 1! = 1

 

Se puede verificar que la especificación del mínimo valor de x, junto con el resto de la definición idéntica a la de las funciones primitivas recursivas, implican el axioma de búsqueda acotada de las funciones primitivas recursivas.