Función computable

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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.

Introducción[editar]

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.

Definición[editar]

Una función parcial

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

se llama parcialmente 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 puede deducirse 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, es decir:

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

Comentarios[editar]

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

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

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

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

usando una función de pares.

Ejemplos[editar]

  • Adición f : N2N, f(n1,n2) := n1 + n2

Propiedades[editar]

  • Si f y g son funciones computables entonces f + g, f.g 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 sólo si el lenguaje \{x \in \Sigma^{*} : f(x)=1\} es recursivo.