Funciones recursivas totales y funciones recursivas parciales en autómatas

Funciones recursivas totales: 
una función recursiva se llama función recursiva total si está definida para todos sus argumentos . Sea f (a1, a2, … an) una función definida en la función g (b1, b2, … bn). Entonces f es una función total si cada elemento de f se asigna a algún elemento único de la función g . 

• Una función total se llama recursiva o recursiva primitiva si y sólo si es una función inicial sobre n, o se obtiene aplicando composición o recursividad con un número finito de veces a la función inicial sobre n.
• La multiplicación de dos números enteros positivos es una función recursiva total o una función recursiva primitiva.
• No todas las funciones recursivas totales son funciones recursivas primitivas.
• La función de Ackerman es una función total.
• Todas las funciones recursivas primitivas son funciones totales.
• Funciones como n!, logn son funciones recursivas totales.

Funciones recursivas parciales: 
una función f (a1, a2, ….an) calculada por un TM se conoce como función recursiva parcial. Si f está definida para algunos pero no para todos los valores de a1, a2, ….an. Sea f (a1 , a2, …an) es una función y está definida en la función g(b1, b2, ….bn) entonces f es una función parcial si algún elemento de f se asigna a casi un elemento de la función g . 

Una función parcial es recursiva si es una función inicial sobre N, o se obtiene aplicando recursividad o composición o minimización sobre la función inicial N. 
 

• La resta de dos números enteros positivos es una función recursiva parcial.
• La composición de funciones parciales (totales) produce una función parcial (total).
• La minimización de una función recursiva total es una función recursiva parcial.
• ¿Función recursiva primitiva? función total? Funciones recursivas parciales