Función computable

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.

Contenido

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

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

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

  • Adición f : N2→ N, f(n1,n2) := n1 + n2

Propiedades

  • El conjunto de las funciones computables es numerable.
  • 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.

Wikimedia foundation. 2010.

Игры ⚽ Поможем сделать НИР

Mira otros diccionarios:

  • Función de Ackermann — En teoría de la computación, la función de Ackermann es una función recursiva que toma dos números naturales como argumentos y devuelve un único número natural. Como norma general se define como sigue …   Wikipedia Español

  • Número computable — En matemáticas, especialmente en ciencia computacional teórica y lógica matemática, los números computables o recursivos son los números reales que pueden ser computados con la precisión que se desee por un algoritmo finito. Se puede llegar al… …   Wikipedia Español

  • Cálculo lambda — Artículo parcialmente traducido: Contiene texto en inglés. Ayuda a terminarlo. El cálculo lambda es un sistema formal diseñado para investigar la definición de función, la noción de aplicación de funciones y la recursión. Fue introducido por… …   Wikipedia Español

  • Teorema de la jerarquía temporal — En la teoría de complejidad computacional, los teoremas de jerarquía temporal son declaraciones importantes sobre cómputo de tiempo acotado en máquinas de Turing. Informalmente, estos teoremas dicen que con más tiempo, una máquina de Turing puede …   Wikipedia Español

  • Lógica combinatoria — La lógica combinatoria es la lógica última y como tal puede ser un modelo simplificado del cómputo, usado en la teoría de computabilidad (el estudio de qué puede ser computado) y la teoría de la prueba (el estudio de qué se puede probar… …   Wikipedia Español

  • Teorema del aumento de velocidad de Blum — En Teoría de la complejidad computacional el teorema del aumento de velocidad de Blum, dado primero por Manuel Blum en 1967, es un teorema importante sobre la complejidad de funciones computables. Cada función computable tiene un número infinito… …   Wikipedia Español

  • Numeración de Gödel — En teoría de los números un número de Gödel es una función que asigna a cada símbolo y fórmula de un lenguaje formal un número único, denominado Número de Gödel (GN). El concepto fue utilizado por primera vez por Kurt Gödel para la demostración… …   Wikipedia Español

  • Reducción de conjuntos — Saltar a navegación, búsqueda En teoría de la computabilidad, sean A y B dos conjuntos cualesquiera; decimos que A es reducible a B y escribimos A ≤ B, si existe una función computable total, o lo que es el equivalente, una función recursiva… …   Wikipedia Español

  • Transformación polinómica — En complejidad computacional, una transformación polinomial, reducción polinomial o reducción de Karp, es una manera de relacionar dos problemas de decisión, de manera que la existencia de un algoritmo que resuelve el primer problema, garantiza… …   Wikipedia Español

  • Reducción de conjuntos — En teoría de la computabilidad, sean A y B dos conjuntos cualesquiera; decimos que A es reducible a B y escribimos A ≤ B, si existe una función computable total, o lo que es el equivalente, una funció …   Enciclopedia Universal

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”