Función computable

De Wikipedia, la enciclopedia libre

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.

Tabla de contenidos

1 Introducción
2 Definición
3 Comentarios
4 Ejemplos
5 Propiedades

[editar] Introducción

Las funciones computables son una formalización de la noción intuitiva de algoritmo y según la tesis 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 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.

[editar] 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}$ .