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 $f:\mathbb {N} ^{k}\rightarrow \mathbb {N}$ é computábel se e só se existe un procedemento que, dada calquera k-tupla $\mathbf {x}$ de números naturais, producirá o valor $f(\mathbf {x} )$.

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

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

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

Unha función total

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

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

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

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

Comentarios

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

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

Pódese facilmente codificar g nunha nova función

$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 $f$ e $g$ son funcións computábeis entón $f+g$, $f\cdot g$ e $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 $\{x\in \Sigma ^{*}:f(x)=1\}$ é recursiva.

Véxase tamén

Bibliografía

• Cutland, Nigel. Computability. Cambridge University Press, 1980.
• Enderton, H.B. Elements of recursion theory. Handbook of Mathematical Logic (North-Holland 1977) pp. 527–566.
• Rogers, H. Theory of recursive functions and effective computation (McGraw–Hill 1967).
• Turing, A. (1936), On Computable Numbers, With an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, Serie 2, Volume 42 (1936). Reimpreso en M. Davis (ed.), The Undecidable, Raven Press, Hewlett, NY, 1965.

Outros artigos

• Algoritmo