6.3 Funciones Computables

Las funciones computables son usadas para discutir computabilidad sin referirse a ningún modelo de computación concreto, como máquina de Turing o máquina de registros. Los axiomas de Blum pueden ser usados para definir una teoría de complejidad computacional abstracta sobre el conjunto de funciones computables.

Según la tesis Church-Turing, la clase de funciones computables es equivalente a la clase de funciones definidas por funciones recursivas, cálculo lambda, o algoritmos de Markov.

Alternativamente se pueden definir como los algoritmos que pueden ser calculados por una máquina de Turing, un sistema de Post, o una máquina de registros.

En teoría de la complejidad computacional, el problema de determinar la complejidad de una función computable esta conocido como un problema de funciones.

Una función parcial

se llama computable si el gráfico de f es un conjunto recursivamente enumerable. El conjunto de funciones parcialmente computables con un parámetro es normalmente escrito o si el número de parámetros es claro del contexto.

Una función total

se llama computable si el gráfico de f es un conjunto recursivo. El conjunto de funciones totalmente computables con un parámetro normalmente se escribe o .
Una función computable f se llama predicado computable si es una función con valor booleano, o sea


Definición
La recursión primitiva se define sobre los números naturales o sobre tuplas de números naturales. La aridad de una función es el número de sus argumentos. El conjunto de las funciones primitivas recursivas se define en base a las siguientes reglas:
1. La constante 0 es primitiva recursiva.
2. La función sucesor S, de aridad 1, que produce el siguiente entero según los axiomas de Peano, es primitiva recursiva.
3. Las funciones de proyección Pin, de aridad n que producen como resultado su argumento de la posición i son primitivas recursivas.
4. Composición: Dado f, una función primitiva recursiva de aridad k y k funciones primitivas recursivas de aridad l g0,...,gk-1, la composición de f con g0,...,gk-1, es decir, la función h(x0,...,xl-1) = f(g0(x0,...,xl-1),...,gk-1(x0,...,xl-1)), es primitiva recursiva.
5. Recursión primitiva: Dado f una función primitiva recursiva de aridad k y g una función primitiva recursiva de aridad k+2, la función de aridad k+1 definida como la función h donde h(0,x0,...,xk-1) = f(x0,...,xk-1) y h(S(n),x0,...,xk-1) = g(h(n,x0,...,xk-1),n,x0,...,xk-1), es primitiva recursiva.
Se puede notar que las funciones de proyección permiten contrarrestar la rigidez impuesta por la paridad de las funciones en la definición anterior, dado que en la composición se puede pasar cualquier subconjunto de los argumentos.
Una función es primitiva recursiva si es la función constante cero, la función sucesor, una proyección o si se define a partir de funciones primitivas recursivas utilizando únicamente composición y recursión primitiva.