Función computábel

As funcións computábeis son o obxecto básico de estudo da teoría da computabilidade e son, especificamente, as funcións que poden ser calculadas por unha máquina de Turing.

A computabilidade dunha función é unha noción informal. Un xeito de describila é dicir que unha función é computábel se os seus valores se poden obter por un método efectivo. Máis rigorosamente, unha función ${\displaystyle f:\mathbb {N} ^{k}\rightarrow \mathbb {N} }$ é computábel se e só se existe un procedemento que, dada calquera k-tupla ${\displaystyle \mathbf {x} }$ de números naturais, producirá o valor ${\displaystyle f(\mathbf {x} )}$.^[1]

Introdución

As funcións computábeis son unha formalización da noción intuitiva de algoritmo e segundo a tese de Church-Turing son exactamente as funcións que poden ser calculadas cunha máquina de cálculo. A noción da computabilidade dunha función pode ser relativizada a un conxunto arbitrario de números naturais A, ou equivalentemente a unha función arbitraria f dos naturais nos naturais, por medio de máquinas de Turing estendidas cun oráculo por A ou f. Tales funcións poden ser chamadas A-computábeis ou f-computábeis respectivamente. Antes da definición precisa dunha función computable os matemáticos empregaban o vocábulo informal efectivamente computábel.

As funcións computábeis son usadas para discutir sobre computabilidade sen referirse a ningún modelo de computación concreto, como o da máquina de Turing ou o da máquina de rexistros. Os axiomas de Blum poden ser usados para definir unha teoría de complexidade computacional abstracta sobre o conxunto de funcións computábeis.

Segundo a tese de Church-Turing, a clase de funcións computábeis é equivalente á clase de funcións definidas por funcións recursivas, cálculo lambda, ou algoritmos de Markov .

Alternativamente pódense definir como os algoritmos que poden ser calculados por unha máquina de Turing, unha máquina de Post, ou unha máquina de rexistros.

En teoría da complexidade computacional, o problema de determinar a complexidade dunha función computábel coñécese como un problema de funcións.

Definicións

Unha función parcial

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

chámase parcialmente computábel se o algoritmo de ${\displaystyle f}$ é un conxunto recursivamente numerábel. O conxunto de funcións parcialmente computábeis cun parámetro escríbese normalmente ${\displaystyle \mathbf {P} ^{(1)}}$ ou ${\displaystyle \mathbf {P} }$ se o número de parámetros pode deducirse do contexto.

Unha función total

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

chámase computábel se o algoritmo de ${\displaystyle f}$ é un conxunto recursivo. O conxunto de funcións totalmente computables cun parámetro normalmente escríbese ${\displaystyle \mathbf {R} ^{(1)}}$ ou ${\displaystyle \mathbf {R} }$.

Unha función computable ${\displaystyle f}$ chámase predicado computable se é unha función con valor booleano, é dicir:

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

Comentarios

Ás veces, por razóns de claridade, escríbese unha función computable como

${\displaystyle g:D_{k}\subseteq \mathbb {N} ^{k}\to \mathbb {N} }$

Pódese facilmente codificar g nunha nova función

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

usando unha 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áximo común divisor
• Identidade de Bézout, unha ecuación diofantiana linear.

Propiedades

• O conxunto das funcións computábeis é numerábel.
• Se ${\displaystyle f}$ e ${\displaystyle g}$ son funcións computábeis entón ${\displaystyle f+g}$, ${\displaystyle f\cdot g}$ e ${\displaystyle f\circ g}$ son funcións computábeis.
• As funcións computábeis son definíbeis aritméticamente.
• Unha función con valor booleano f é un predicado computábel se e só se a linguaxe ${\displaystyle \{x\in \Sigma ^{*}:f(x)=1\}}$ é recursiva.