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

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

llámase parcialmente computable si'l gráficu ${\displaystyle f}$ ye un conjumerable. El conxuntu de funciones parcialmente computables con un parámetru ye de normal escritu ${\displaystyle \mathbf {P} ^{(1)}}$ o ath> si'l númberu de parámetros puede deducise del contestu.

Una función total

${\displaystyle f:\mathbb {N} \to \mathbb {N} }$

llámase computable si'l gráficu de ${\displaystyle f}$ ye un conxuntu recursivo. El conxuntu de funciones totalmente computables con un parámetru de normal escríbese ${\displaystyle \mathbf {R} ^{(1)}}$ o ${\displaystyle \mathbf {R} }$.

Una función computable ${\displaystyle f}$ llámase predicáu computable si ye una función con valor booleano, esto ye:

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

Comentarios

Dacuando, por razones de claridá, escríbese una función computable como : ${\displaystyle g:\subseteq \mathbb {N} ^{k}\to \mathbb {N} }$

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

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

usando una función de pares.

Exemplos

• Función constante f : N^k→ N, f(n₁,...n_k) := n

• Adición f : N²→ N, f(n₁,n₂) := n₁ + n₂

• 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 ${\displaystyle \{x\in \Sigma ^{*}:f(x)=1\}}$ ye recursivo.

Referencies

Enllaces esternos

• Wikimedia Commons tien conteníu multimedia tocante a Función computable.

• Datos: Q1148456