Função computável

Este artigo contém uma lista de referências no fim do texto, mas as suas fontes não são claras porque não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. Ajude a melhorar este artigo inserindo citações no corpo do artigo. (Maio de 2011)

Funções computáveis são os objetos básicos de estudo na teoria da computabilidade. Funções computáveis são uma analogia formalizada da noção intuitiva de algoritmos. 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 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ções Turing-computáveis e as funções μ-recursivas.

Antes de uma definição precisa do termo, matemáticos 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á exponencialmente (ou mesmo 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.

A classe de funções computáveis pode ser definida em vários modelos de computação diferentes, incluindo:

• Máquinas de Turing;
• Funções μ-recursivas;
• Cálculo lambda;
• Máquinas de Post (máquinas de Post-Turing e sistemas de tags);
• 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 f leva um número fixo e finito de números naturais como argumentos. Como, em geral, as funções são 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 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 f(x₁, ..., x_k)↓ indica que a função parcial f é definida sobre os argumentos x₁, ..., x_k, e a notação f(x₁, ..., x_k) = y indica que f é definida sobre os argumentos x₁, ..., x_k e o valor retornado é y. O caso em que a função f é indefinida para os argumentos x₁, ..., x_k é denotada por f(x₁, ..., x_k)↑ .

Ver 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 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 ${\displaystyle x}$ no domínio de ${\displaystyle f}$, então após uma quantidade finita de passos discretos o procedimento deve terminar e produzir ${\displaystyle f(x)}$. 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 ${\displaystyle x}$ que não está no domínio de ${\displaystyle f}$, 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 ${\displaystyle f}$ em ${\displaystyle x}$. Portanto, se um valor para ${\displaystyle f(x)}$ é 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.

Um conjunto ${\displaystyle A}$ de números naturais é chamada computável (ou ainda, recursivo ou decidível) se há uma função computável ${\displaystyle f}$ de forma que para cada número ${\displaystyle n}$, ${\displaystyle f(n)\downarrow =1}$ se ${\displaystyle n}$ está em ${\displaystyle A}$ e ${\displaystyle f(n)\downarrow =0}$ se ${\displaystyle n}$ não está em ${\displaystyle A}$.

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 ${\displaystyle f}$ de forma que, para cada número ${\displaystyle n}$, ${\displaystyle f(n)}$ é definida se e somente se ${\displaystyle n}$ 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 ${\displaystyle B}$ dos números naturais:

• ${\displaystyle B}$ está no domínio de uma função computável.
• ${\displaystyle B}$ está no intervalo de uma função computável. Se ${\displaystyle B}$ é infinito então a função pode ser assumida como injetora.

Se um conjunto ${\displaystyle B}$ está no intervalo de uma função ${\displaystyle f}$ então a função pode ser vista como uma enumeração de ${\displaystyle B}$, pois a lista ${\displaystyle f(0),f(1),\cdots }$ incluirá cada elemento de ${\displaystyle B}$.

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.

Ver artigo principal: Linguagem formal

Em teoria da computabilidade é comum se considerar linguagens formais. Um 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 ${\displaystyle \{0,1\}}$. 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 ${\displaystyle f}$ de forma que para cada palavra ${\displaystyle w}$ do alfabeto, ${\displaystyle f(w)\downarrow =1}$ se a palavra pertence à linguagem e ${\displaystyle f(w)\downarrow =0}$ 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 ${\displaystyle f}$ de forma que ${\displaystyle f(w)}$ é definida se e somente se a palavra ${\displaystyle w}$ 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.

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

• Cada função com um domínio finito; por exemplo, qualquer sequência finita dos números naturais.
• Cada função constante f : N^k → N, f(n₁,...n_k) := n.
• Adição f : N² → N, f(n₁,n₂) := n₁ + n₂
• 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: f + g, f * g, ${\displaystyle f\circ g}$ se f for unária, max(f,g), min(f,g), arg max{y ≤ 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 π, 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 incomputável dos números naturais (como a 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).

Ver 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 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.

Ver 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 contavelmente muitas funções computáveis. Por exemplo, funções podem ser codificadas usando uma cadeia de bits (o alfabeto Σ = {0, 1}).

O conjunto dos números reais é incontável. Assim, muitos números reais não são computáveis. Veja 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.

A noção de computabilidade de uma função pode ser relativizada para um 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.

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.

Ver artigo principal: 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?]}

Referências

• 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, Series 2, Volume 42 (1936). Reprinted in M. Davis (ed.), The Undecidable, Raven Press, Hewlett, NY, 1965.