Función computable

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

Introducción

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 equivalentamente a una función arbitraria f de los naturales a los naturales, por medio de máquinas de Turing extendidas por un oracle por A o f. Tales funciones puede ser llamados A-computable o f-computable respectivamente. Antes la definición preciso de una función computable los matemáticos usaban el término informal efectivamente computable.

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 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.

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 esta conocido como un problema de funciones.

Definición

Una función parcial

$f:\subseteq \mathbb {N} \to \mathbb {N}$

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 $\mathbf {P} ^{(1)}$ o $\mathbf {P}$ si el número de parámetros es claro del contexto.

Una función total

$f:\mathbb {N} \to \mathbb {N}$

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 $\mathbf {R} ^{(1)}$ o $\mathbf {R}$.

Una función computable $f$ se llama predicado computable si es una función con valor booleano, o sea

$f:\subseteq \mathbb {N} \to \{0,1\}$

Comentarios

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

$g:\subseteq \mathbb {N} ^{k}\to \mathbb {N}$

Podemos fácilmente codificar g en una nueva función

$f:\subseteq \mathbb {N} \to \mathbb {N}$

usando una función de pares.

Ejemplos

• Función constante f : N^k→ N, f(n₁,...n_k) := n

• Adición f : N²→ N, f(n₁,n₂) := n₁ + n₂

• Máximo común divisor
• Identidad de Bézout, una ecuación diofántica linear

Propiedades

• El conjunto de las funciones computables es numerable.

• Dados dos funciones computables f yg entonces f+g, fg y fog son funciones computables.

• Las funciones computables son definibles aritméticamente.

• Una función con valor booleano f es un predicado computable si y solo si el lenguaje $\{x\in \Sigma ^{*}:f(x)=1\}$ es recursivo.