Función computable

Las funciones computables son el objeto básico de estudio de la teoría de la computabilidad y son, específicamente, las funciones que pueden ser calculadas por una máquina de Turing.

Las funciones computables son una formalización de la noción intuitiva de algoritmo y según la Tesis de Church-Turing son exactamente las funciones que pueden ser calculadas con una máquina de cálculo. La noción de la computabilidad de una función puede ser relativizada a un conjunto arbitrario de números naturales A, o equivalentemente a una función arbitraria f de los naturales a los naturales, por medio de máquinas de Turing extendidas con un oráculo por A o f. Tales funciones pueden ser llamadas A-computable o f-computable respectivamente. Antes de la definición precisa de una función computable los matemáticos usaban el término informal efectivamente computable.

Las funciones computables son usadas para discutir sobre computabilidad sin referirse a ningún modelo de computación concreto, como el de la máquina de Turing o el de la 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 de 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 [1].

Alternativamente se pueden definir como los algoritmos que pueden ser calculados por una máquina de Turing, una máquina 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 es conocido como un problema de funciones.

Una función parcial

se llama parcialmente computable si el gráfico ${displaystyle f}$ es un conjumerable. El conjunto de funciones parcialmente computables con un parámetro es normalmente escrito ${displaystyle mathbf {P} ^{(1)}}$ o ath> si el número de parámetros puede deducirse del contexto.

Una función total

se llama computable si el gráfico de ${displaystyle f}$ es un conjunto recursivo. El conjunto de funciones totalmente computables con un parámetro normalmente se escribe ${displaystyle mathbf {R} ^{(1)}}$ o ${displaystyle mathbf {R} }$.

Una función computable ${displaystyle f}$ se llama predicado computable si es una función con valor booleano, es decir:

A veces, por razones de claridad, se escribe una función computable como

Se puede fácilmente codificar g en una nueva función

usando una función de pares.