Mostrar código-fonte de Função computável

{{Sem notas|Este artigo|tec|data=maio de 2011}}
'''Funções computáveis''' são os objetos básicos de estudo na [[teoria da recursão|teoria da computabilidade]]. Funções computáveis são uma [[analogia]] formalizada da noção intuitiva de [[algoritmo]]s. Elas são usadas para discutir a computabilidade sem se referir a algum [[modelo de computação]] concreto, como a [[máquina de Turing]] e a [[Máquina de registradores|máquina registradora]]. Entretanto, o conjunto das funções computáveis é equivalente ao conjunto de funções computáveis numa máquina de Turing. No entanto, qualquer definição precisa fazer referência a algum modelo específico de computação, mas todas as referências válidas geram a mesma classe de funções. Modelos particulares de computabilidade que dão origem ao conjunto de funções computáveis são as [[função Turing-computável|funções Turing-computáveis]] e as [[função μ-recursiva|funções μ-recursivas]].

Antes de uma definição precisa do termo, [[matemático]]s usavam informalmente o termo "efetivamente computável". Desde então, esse termo vem sendo identificado como função computável. Note que a computabilidade efetiva de tais funções não implica que elas são ''eficientemente'' computáveis, isto é, a execução em certa quantidade tolerável de tempo. De fato, pode-se mostrar que para algumas funções computáveis, qualquer algoritmo que a implemente será ineficiente na medida em que seu [[tempo de execução]] crescerá [[função exponencial|exponencialmente]] (ou mesmo [[Tetração|superexponencialmente]]) de acordo com o tamanho da entrada. Os campos da [[computação factível]] e [[complexidade computacional]] estudam funções que podem ser computadas eficientemente.

De acordo com a [[tese de Church-Turing]], funções computáveis são exatamente as funções que podem ser calculadas usando um dispositivo mecânico de calculo dado uma quantidade ilimitada de espaço de armazenamento e de tempo de execução. De maneira equivalente, a mesma tese define que qualquer função que possui um algoritmo é computável. Observe que um algoritmo, neste sentido, é interpretado como sendo uma sequência de passos que uma pessoa, com tempo ilimitado e caneta e papéis infinitos, pode seguir.

Os [[axiomas de Blum]] podem ser usados para definir uma [[teoria de complexidade computacional]] abstrato, sobre o conjunto de funções computáveis. Na teoria da complexidade computacional, o problema de se determinar a complexidade de uma função computável é conhecido como [[problema de função]].

== Definição ==
A classe de funções computáveis pode ser definida em vários [[modelo de computação|modelos de computação]] diferentes, incluindo:
* '''[[Máquina de Turing|Máquinas de Turing]];'''
* '''[[Função μ-recursiva|Funções μ-recursivas]];'''
* '''[[Cálculo lambda]];'''
* '''[[Máquina de Post|Máquinas de ''Post'']]''' ('''[[Máquina de Post-Turing|máquinas de ''Post-Turing'']]''' e '''sistemas de ''tags''''');
* '''[[Máquina de registradores|Máquinas registradoras]].'''
Embora esses modelos utilizem diferentes representações para as funções, suas entradas e suas saídas, existem traduções entre quaisquer par de modelos. Durante o restante deste artigo, serão utilizadas funções de [[números naturais]] para números naturais (como é o caso de funções μ-recursivas, por exemplo).

Cada função computável {{math|''f''}} leva um número fixo e finito de números naturais como argumentos. Como, em geral, as funções são [[função parcial|parciais]], elas podem não ser definidas para toda escolha de entrada possível. Se uma função computável for definida para uma certa entrada, então ela retornará um número natural simples como saída (esta saída pode ser interpretada como uma lista de números usando uma função de emparelhamento). Estas funções também são chamadas '''funções recursivas parciais'''. Na teoria da computabilidade, o '''[[domínio (matemática)|domínio]]''' de uma função é dado como o conjunto de todas as entradas para o qual a função é definida.

Uma função que é definida para todos os argumentos possíveis é chamada '''total'''. Se uma função computável for total, ela será chamada '''função computável total''' ou '''função recursiva total'''.

A notação {{math|''f''(<var>x</var><sub>1</sub>, ..., <var>x<sub>k</sub></var>)&darr; }} indica que a função parcial {{math|''f''}} é definida sobre os argumentos {{math|<var>x</var><sub>1</sub>, ..., <var>x<sub>k</sub></var>}}, e a notação {{math|''f''(<var>x</var><sub>1</sub>, ..., <var>x<sub>k</sub></var>) {{=}} <var>y</var> }} indica que {{math|''f''}} é definida sobre os argumentos {{math|<var>x</var><sub>1</sub>, ..., <var>x<sub>k</sub></var>}} e o valor retornado é {{math|<var>y</var>}}. O caso em que a função {{math|''f''}} é indefinida para os argumentos {{math|<var>x</var><sub>1</sub>, ..., <var>x<sub>k</sub></var>}} é denotada por {{math|''f''(<var>x</var><sub>1</sub>, ..., <var>x<sub>k</sub></var>)&uarr; }} .

== Características ==
{{Artigo principal|Algoritmo}}

A característica básica de uma função computável é a disponibilidade de um [[algoritmo]], um procedimento finito que descreve como computá-la. A interpretação do significado de procedimento e como ele é usado cabe ao modelo de computação, mas cada interpretação compartilha algumas propriedades. O fato de tais modelos proverem classes equivalentes de funções computáveis vem do fato de que cada modelo é capaz de ler e reproduzir um procedimento de qualquer outro modelo, assim como um [[compilador]] é capaz de ler instruções em uma [[linguagem de computador]] e transformá-las noutra linguagem.

Herbert Enderton ([[1977]]) define as seguintes características de um procedimento para uma função computável. Características similares forem definidas por [[Alan Turing|Turing]] ([[1936]]), Rogers ([[1967]]), entre outros.
* Há instruções exatas para o procedimento, numa quantidade finita. Portanto, cada função computável deve ter um programa finito que descreve completamente como ele deve ser computada.
* Se o procedimento é alimentado por uma ''k''-tupla <math>x</math> no domínio de <math>f</math>, então após uma quantidade finita de passos discretos o procedimento deve terminar e produzir <math>f(x)</math>. Intuitivamente, o procedimento é executado passo a passo, com uma regra específica para definir o que deve ser feito em cada passo. Após uma quantidade finita de passos, o valor da função é retornado.
* Se o procedimento é alimentado por uma ''k''-tupla <math>x</math> que não está no domínio de <math>f</math>, então o procedimento pode executar infinitamente, nunca retornando um valor. Ou ele pode parar em certo passo, mas não pode produzir um valor para <math>f</math> em <math>x</math>. Portanto, se um valor para <math>f(x)</math> é encontrado, ele deve ser correto. Não é usado para que se distingua um valor de retorno incorreto porque o procedimento sempre estará correto se produzir algum resultado qualquer.

Enderton também lista diversas clarificações para tais requisitos de procedimentos para funções computáveis:
* Em teoria, o procedimento deve trabalhar para uma grande quantidade de argumentos. Não se assume a quantidade máxima de argumentos que podem alimentar o procedimento.
* O procedimento deve retornar após uma quantidade finita de passos para produzir um resultado, mas pode levar uma quantidade indeterminada de passos para parar a execução. Não se assume uma limitação de tempo.
* Apesar do procedimento poder usar somente uma quantidade finita de espaço de armazenamento durante a computação, não há limitação nesse sentido. Assume-se que espaço adicional para armazenamento pode ser fornecido ao procedimento sempre que requerido.

O campo da [[complexidade computacional]] estuda funções com limitações previstas sobre o tempo ou espaço permitidos em uma computação bem sucedida.

== Conjuntos computáveis ==
Um conjunto <math>A</math> de números naturais é chamada '''computável''' (ou ainda, '''recursivo''' ou '''decidível''') se há uma função computável <math>f</math> de forma que para cada número <math>n</math>, <math>f(n) \downarrow = 1</math> se <math>n</math> está em <math>A</math> e <math>f(n) \downarrow = 0</math> se <math>n</math> não está em <math>A</math>.

Um conjunto de números naturais é chamado '''computacionalmente enumerável''' (ou ainda, '''recursivamente enumerável''' ou, ainda, '''semidecidível''') se há uma função computável <math>f</math> de forma que, para cada número <math>n</math>, <math>f(n)</math> é definida [[se e somente se]] <math>n</math> está no conjunto. Portanto, um conjunto é computacionalmente enumerável se e somente se ele está no domínio de alguma função computável. O termo ''enumerável'' é usado neste contexto por conta da seguinte equivalência de um subconjunto não vazio <math>B</math> dos números naturais:
* <math>B</math> está no domínio de uma função computável.
* <math>B</math> está no intervalo de uma função computável. Se <math>B</math> é infinito então a função pode ser assumida como [[Função injectiva|injetora]].

Se um conjunto <math>B</math> está no intervalo de uma função <math>f</math> então a função pode ser vista como uma [[enumeração]] de <math>B</math>, pois a lista <math>f(0), f(1), \cdots</math> incluirá cada elemento de <math>B</math>.

Como cada relação finitária sobre os números naturais pode ser identificada como um conjunto correspondente das sequências finitas de números naturais, as noções de '''relação computável''' e '''relação computacionalmente enumerável''' podem ser definidas a partir dos seus análogos para conjuntos.

== Linguagens formais ==
{{Artigo principal|Linguagem formal}}

Em [[teoria da computabilidade]] é comum se considerar [[linguagem formal|linguagens formais]]. Um '''[[alfabeto (ciência da computação)|alfabeto]]''' é um conjunto arbitrário. Uma '''palavra''' sobre um alfabeto é uma sequência finita de símbolos de um alfabeto, que podem ser usados mais de uma vez na mesma sequência. Por exemplo, cadeias binárias são palavras do alfabeto <math>\{0,1\}</math>. Uma '''linguagem''' passa a ser um subconjunto da coleção de todas as palavras do alfabeto. Por exemplo, a coleção de todas as cadeias binárias que contém exatamente três elementos é uma linguagem do alfabeto binário.

Um propriedade relevante de uma linguagem formal é o nível de dificuldade requerido para decidir se uma palavra pertence à linguagem. Alguns sistemas de codificação devem ser desenvolvidos para permitir que uma função computável ser alimentada por uma palavra qualquer; isso é geralmente considerado uma rotina. Uma linguagem é chamada computável (ou ainda, recursiva ou decidível) se há uma função computável <math>f</math> de forma que para cada palavra <math>w</math> do alfabeto, <math>f(w) \downarrow = 1</math> se a palavra pertence à linguagem e <math>f(w)\downarrow = 0</math> se a palavra não pertence à linguagem. Portanto, a linguagem é computável somente se há um procedimento que pode computar de palavras pertencem à linguagem.

Uma linguagem é '''computacionalmente enumerável''' (ou ainda, '''recursivamente enumerável''', ou '''semidecidível''') se há uma função computável <math>f</math> de forma que <math>f(w)</math> é definida se e somente se a palavra <math>w</math> está na linguagem. Portanto, apesar de não ser decidível é computável. O termo enumerável possui a mesma etimologia dos conjuntos enumeráveis dos números naturais.

== Exemplos ==
As seguintes funções são computáveis:

* Cada função com um [[Domínio (matemática)|domínio]] finito; por exemplo, qualquer sequência finita dos números naturais.
* Cada [[função constante]] ''f'' : '''N'''<sup>''k''</sup> → '''N''',  ''f''(''n''<sub>1</sub>,...''n''<sub>''k''</sub>) := ''n''.
* [[Adição]] ''f'' : '''N'''<sup>2</sup> → '''N''', ''f''(''n''<sub>1</sub>,''n''<sub>''2''</sub>) := ''n''<sub>1</sub> + ''n''<sub>2</sub>
* A função que dá a lista de fatores primos de um número.
* O [[máximo divisor comum]] de dois números.
* A [[identidade de Bézout]], uma [[equação diofantina]] linear

Se ''f'' e ''g'' são computáveis, então também são computáveis: [[Adição|''f'' + ''g'']], [[Multiplicação|''f'' * ''g'']], [[Composição de funções|<math>f \circ g</math>]] se ''f'' for [[Operação unária|unária]], ''max''(''f'',''g''), ''min''(''f'',''g''), ''arg max''{''y''&nbsp;≤&nbsp;''f''(''x'')}  e muitas outras combinações.

Os exemplos a seguir ilustram que uma função pode ser computável mesmo se não se conhece um algoritmo que a computa.

* A função ''f'' tal que ''f''(''n'') = 1 se existe uma sequência de ''pelo menos n'' cincos consecutivos em uma expansão decimal de [[Pi|π]], e ''f''(''n'') = 0 caso contrário, é computável. (A função ''f'' é ou a função 1 constante, que é computável, ou existe um ''k'' tal que ''f''(''n'') = 1 se ''n'' < ''k'' e ''f''(''n'') = 0 se ''n'' ≥ ''k''.  Todas essas funções são computáveis.  Não se sabe se existem execuções arbitrariamente longas de cincos na expansão decimal de π, então nós não sabemos ''qual'' dessas funções é ''f''.  Mesmo assim, nós sabemos que a função ''f'' deve ser computável.)
* Cada segmento finito de uma sequência ''in''computável dos números naturais (como a [[Algoritmo do castor#A função do algoritmo do castor Σ(n)|função do castor]] ''Σ'') é computável.  Por exemplo, para cada número natural ''n'', existe um algoritmo que computa uma sequência finita Σ(0), Σ(1), Σ(2), ..., Σ(''n'') — em contraste com o fato de que não há algoritmo que compute a sequência-Σ ''completamente'', ou seja, Σ(''n'') para todo ''n''. Portanto, "Imprima 0, 1, 4, 6, 13" é um algoritmo trivial para computar Σ(0), Σ(1), Σ(2), Σ(3), Σ(4); similarmente, para qualquer valor dado de ''n'', um algoritmo  ''existe'' (mesmo que ele nunca seja ''conhecido'' ou produzido por alguém) para computar Σ(0), Σ(1), Σ(2), ..., Σ(''n'').

== Tese de Church–Turing ==
{{Artigo principal|Tese de Church-Turing}}

A '''tese de Church–Turing''' afirma que qualquer função computável de um procedimento possuindo as três propriedades listadas [[#Características|acima]] é uma função computável.  Como essas três propriedades não são formalmente definidas, a tese de Church–Turing não pode ser provada.  Os seguintes fatos são frequentemente tomados como evidências para a tese:
* Muitos modelos de computação equivalentes são conhecidos, e todos eles dão a mesma definição de função computável (ou uma versão mais fraca, em algumas instâncias).
* Nenhum modelo de computação mais forte, que é geralmente considerado como sendo efetivamente calculável foi proposto.

A tese de Church–Turing é, algumas vezes, usada em provas para justificar que uma função particular é computável, dando uma descrição concreta de um procedimento para a computação. Isto é permitido porque acredita-se que todos os usos da tese podem ser removidos pelo processo tedioso de escrever um procedimento formal para a função em algum modelo de computação.

== Funções incomputáveis e problemas insolúveis ==
{{Artigo principal|Lista de problemas indecidíveis}}

Toda função computável tem um procedimento finito definindo instruções explícitas e não-ambíguas sobre como computar. Além disso, este procedimento tem que ser codificado em um alfabeto finito usado pelo modelo computacional, assim existem somente [[contabilidade|contavelmente]] muitas funções computáveis. Por exemplo, funções podem ser codificadas usando uma cadeia de bits (o alfabeto {{math|&Sigma; {{=}} {0, 1<nowiki>}</nowiki>}}).

O conjunto dos números reais é incontável. Assim, muitos números reais não são computáveis. Veja [[Número computável#Propriedades|número computável]]. O conjunto de funções finitárias sobre os números naturais é incontável, por isso a maior parte não é computável. Exemplos concretos de tais funções são o [[algoritmo do castor]], a [[complexidade de Kolmogorov]], ou qualquer função que gere como saída os dígitos de um número não computável, como a [[constante de Chaitin]].

De maneira similar, a maior parte dos subconjuntos dos números naturais não é computável. O [[problema da parada]] foi o primeiro conjunto do tipo a ser construído. O [[Entscheidungsproblem]] (termo alemão para "[[problema de decisão]]"), proposto por  [[David Hilbert]], perguntava se existe um procedimento efetivo para se determinar quais declarações matemáticas (codificadas como números naturais) são verdadeiras.  Turing e Church mostraram, independentemente, na década de 1930 que este conjunto dos números reais não é computável, por ser incontável. De acordo com a tese de Church–Turing, não há procedimento efetivo, ou algoritmo, que possa realizar tais computações.

== Extensões de computabilidade ==
=== Computabilidade relativa ===
A noção de computabilidade de uma função pode ser relativizada para um [[Conjunto (matemática)|conjunto]] arbitrário de [[números naturais]] ''A''. Uma função ''f'' é definida como sendo '''computável em ''A''''' (equivalentemente, '''''A''-computável''' ou '''computável relativa a ''A''''') quando ela satisfaz a definição de uma função computável com modificações permitindo o acesso a ''A'' como um oráculo. Tal como acontece com o conceito de uma função computável, a computabilidade relativa pode ter definições equivalentes em muitos modelos de computação diferentes.  Geralmente, isto é alcançado complementando o modelo de computação com uma operação primitiva adicional que pergunta se um dado inteiro é um membro de ''A''. Nós também podemos falar sobre ''f'' ser '''computável em ''g''''' identificando ''g'' com seu [[grafo]].

=== Teoria da recursão superior ===
A teoria hiperaritimética estuda aqueles conjuntos que podem ser computados a partir de um [[número ordinal]] computável de iterações de [[salto de Turing]] do [[conjunto vazio]].  Isto é equivalente aos conjuntos definidos por ambas fórmulas existenciais e universais na linguagem da aritmética de segunda ordem e em alguns modelos da [[Hipercomputação]]. Teorias de recursão ainda mais gerais têm sido estudadas, como a '''teoria da E-recursão''' aonde qualquer conjunto pode ser usado como um argumento para uma função E-recursiva.

=== Hipercomputação ===
{{AP|Hipercomputação}}
Embora a tese de Church-Turing afirme que as funções computáveis incluem todas as funções com algoritmos, é possível considerar classes mais amplas de funções que relaxem os requerimentos que os algoritmos possuem.  O campo da hipercomputação estuda modelos de computação que vão além da computação de Turing normal.  Estas não violam a tese de Church-Turing, já que elas permitem operações que, mesmo que possam (ou não) ser implementadas em um dispositivo físico, não podem ser realizadas por uma pessoa usando lápis e papel.{{carece de fontes|data=maio de 2011}}

{{Referências}}
* Cutland, Nigel. ''Computability''. [[Cambridge University Press]], 1980.
* Enderton, H.B. Elements of recursion theory.  ''Handbook of Mathematical Logic'' (North-Holland 1977) pp.&nbsp;527–566.
* Rogers, H.  ''Theory of recursive functions and effective computation'' (McGraw–Hill 1967).
* [[A. Turing|Turing, A.]] (1936), On Computable Numbers, With an Application to the Entscheidungsproblem. ''Proceedings of the London Mathematical Society'', Series 2, Volume 42 (1936). Reprinted in M. Davis (ed.), ''The Undecidable'', Raven Press, Hewlett, [[Nova Iorque (estado)|NY]], 1965.

== Ver também ==
{{div col}}
* [[Método efetivo]]
* [[Grau de Turing]]
* [[Hierarquia aritmética]]
* [[Algoritmo super-recursivo]]
* [[Função semicomputável]]
{{-fim}}

{{Controle de autoridade}}

{{DEFAULTSORT:Funcao Computavel}}
[[Categoria:Teoria da computação]]
[[Categoria:Teoria da computabilidade]]