Función computable

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 
Les funciones computables son una formalización de la noción intuitiva d'algoritmu y según la Tesis de Church-Turing son esautamente 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 .

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 

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 

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 

 Función constante f : Nk→ N, f(n1,...nk) := n

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

 Máximu común divisor
 Identidá de Bézout, una ecuación diofántica llinial.

 Propiedaes 

 El conxuntu de les funciones computables ye numerable. 

 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.

 Referencies 

 Enllaces esternos 

Categoría:Computabilidá
Computable
Computable
Categoría:Wikipedia:Páxines con enllaces interllingüísticos