Función computable

De Wikipedia
Saltar a navegación Saltar a la gueta

Les funciones computables son l'oxetu básicu d'estudiu de la teoría de la computabilidad y son, específicamente, les funciones que pueden ser calculaes por una máquina de Turing.

Introducción[editar | editar la fonte]

Les funciones computables son una formalización de la noción intuitiva d'algoritmu y según la Tesis de Church-Turing son esactamente les funciones que pueden ser calculaes con una máquina de cálculu. La noción de la computabilidad d'una función puede ser relativizada a un conxuntu arbitrariu de númberos naturales A, o equivalentemente a una función arbitraria f de los naturales a los naturales, per mediu de máquines de Turing estendíes con un oráculu por A o f. Tales funciones pueden ser llamaes A-computable o f-computable respeutivamente. Antes de la definición precisa d'una función computable los matemáticos usaben el términu informal efeutivamente computable.

Les funciones computables son usaes p'aldericar sobre computabilidad ensin referise a nengún modelu de computación concretu, como'l de la máquina de Turing o'l de la máquina de rexistros. Los axomes de Blum pueden ser usaos pa definir una teoría de complexidá computacional astracta sobre'l conxuntu de funciones computables.

Según la Tesis de Church-Turing, la clase de funciones computables ye equivalente a la clase de funciones definíes por funciones recursivas, cálculo lambda, o algoritmos de Markov [1].

Alternativamente pueden definise como los algoritmos que pueden ser calculaos por una máquina de Turing, una máquina de Post, o una máquina de rexistros.

En teoría de la complexidá computacional, el problema de determinar la complexidá d'una función computable ye conocíu como un problema de funciones.

Definición[editar | editar la fonte]

Una función parcial

llámase parcialmente computable si'l gráficu ye un conjumerable. El conxuntu de funciones parcialmente computables con un parámetru ye de normal escritu o ath> si'l númberu de parámetros puede deducise del contestu.

Una función total

llámase computable si'l gráficu de ye un conxuntu recursivo. El conxuntu de funciones totalmente computables con un parámetru de normal escríbese o .

Una función computable llámase predicáu computable si ye una función con valor booleano, esto ye:

Comentarios[editar | editar la fonte]

Dacuando, por razones de claridá, escríbese una función computable como :

Puédese fácilmente codificar g nuna nueva función

usando una función de pares.

Exemplos[editar | editar la fonte]

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

Propiedaes[editar | editar la fonte]

  • Si f y g son funciones computables entós f + g, f.g y fog son funciones computables.
  • Les funciones computables son definibles aritméticamente.
  • Una función con valor booleano f ye un predicáu computable si y namái si'l llinguaxe ye recursivo.



Función computable