A teoria da computabilidade, também conhecida como teoria da recursão, é um ramo da lógica matemática que surgiu na década de 1930 com o estudo das funções computáveis e do grau de TuringSoare, Robert I. (1987). Recursively Enumerable Sets and Degrees. Springer-Verlag. p. 1. ISBN 0-387-15299-7.. O campo se expandiu para incluir o estudo generalizado da computabilidade e definibilidade. Nessas áreas, a teoria da recursão se sobrepõe à teoria da prova e à teoria descritiva efetiva de conjuntosCutland, Nigel J. (1980). Computability: An Introduction to Recursive Function Theory. Cambridge University Press. p. 1. ISBN 0-521-29465-7..
As questões básicas envolvidas na teoria da recursão são: "O que significa para uma função (N->N) ser computável?" e "Como as funções não-computáveis são classificadas em uma teoria baseada em seus níveis de não-computabilidade?" . As respostas a essas perguntas levaram a uma rica teoria que ainda está sendo estudada atualmente. A teoria da computabilidade também se aproximou da ciência da computaçãoSlaman, Theodore A. (1999). "Theories of Recursion". In The Handbook of Computability Theory. Elsevier. p. 231-255..
Estudiosos da recursão em lógica matemática frequentemente estudam a teoria da computabilidade relativa, noções de redutibilidade e estruturas de grau, como as descritas neste artigoDavis, Martin (1965). The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions. Dover Publications. p. 3.. Isso contrasta com a teoria das hierarquias subrecursivas, métodos formais e linguagens formais que são comuns no estudo da teoria da computabilidade na ciência da computaçãoRogers, Hartley (1987). Theory of Recursive Functions and Effective Computability. MIT Press. p. 1. ISBN 0-262-68052-1.. Existe uma sobreposição considerável no conhecimento e nos métodos entre essas duas comunidades de pesquisa, embora não haja uma grande separação entre elas.
Conjuntos Computáveis e Não Computáveis
A teoria da recursão teve origem com o trabalho de Kurt Gödel, Alonzo Church, Alan Turing, Stephen Kleene e Emil Post na década de 1930.
Os resultados fundamentais obtidos por esses pesquisadores estabeleceram a computabilidade de Turing como uma formalização correta da ideia informal de cálculo efetivoChurch, Alonzo (1936). "An Unsolvable Problem of Elementary Number Theory". American Journal of Mathematics. 58 (2): 345–363.. Esses resultados levaram Stephen Kleene (1952) a cunhar os termos "Tese de Church" e "Tese de Turing"Kleene, Stephen Cole (1952). Introduction to Metamathematics. North-Holland.. Atualmente, essas hipóteses são consideradas uma única, a Tese de Church-Turing, que afirma que qualquer função que é computável por um algoritmo é uma função computávelBoolos, George S.; Burgess, John P.; Jeffrey, Richard C. (2002). Computability and Logic. 4th ed. Cambridge University Press. p. 25.. Apesar de ser inicialmente cético, Gödel argumentou a favor dessa tese por volta de 1946Gödel, Kurt (1946). "Remarks before the Princeton Bicentennial Conference on Problems in Mathematics". In Davis, Martin (1965). The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions. Dover Publications. p. 84..
Com a definição do cálculo efetivo, surgiram as primeiras provas de que existem problemas na matemática que não podem ser efetivamente decididos. Church (1936a, 1936b) e Turing (1936), inspirados por técnicas utilizadas por Gödel (1931) para provar seus teoremas de incompletude, demonstraram independentemente que o Problema de Entscheidung não é efetivamente decidívelTuring, Alan M. (1936). "On Computable Numbers, with an Application to the Entscheidungsproblem". Proceedings of the London Mathematical Society. 2 (42): 230–265.. Esse resultado mostrou que não existe um procedimento algorítmico que possa decidir corretamente se proposições matemáticas arbitrárias são verdadeiras ou falsas.
Muitos problemas da matemática foram mostrados como indecidíveis após esses exemplos iniciaisPost, Emil L. (1944). "Recursively Enumerable Sets of Positive Integers and Their Decision Problems". Bulletin of the American Mathematical Society. 50 (5): 284–316.. Em 1947, Markov e Post publicaram artigos independentes mostrando que o problema da palavra para semigrupos não pode ser efetivamente decididoMarkov, Andrey A. (1947). "On Unsolvable Problems Concerning Matrices". Doklady Akademii Nauk SSSR. 57: 35–38. (em russo). Ampliando esse resultado, Pyotr Novikov e William Boone mostraram independentemente nos anos 1950 que o problema da palavra para grupos não é efetivamente resolvível: não existe um procedimento eficaz que, dada uma palavra em um grupo finito, decidirá se um elemento representado pela palavra é um elemento identificador do grupoNovikov, Pyotr S. (1955). "On the Algorithmic Unsolvability of the Problem of Identity in Group Theory". Doklady Akademii Nauk SSSR. 103: 981–983. (em russo)Boone, William W. (1959). "The Word Problem". Annals of Mathematics. 70 (2): 207–265.. Em 1970, Yuri Matiyasevich provou (usando resultados de Julia Robinson) o Teorema de Matiyasevich, o que implica que o Décimo problema de Hilbert não tem solução eficaz; esse problema questionava se existe um procedimento efetivo para decidir se uma equação diofantina sobre os inteiros tem uma solução no conjunto dos inteirosMatiyasevich, Yuri (1970). "Diophantine Representation of Recursively Enumerable Predicates". Doklady Akademii Nauk SSSR. 191: 279–282. (em russo). A lista de problemas indecidíveis tem exemplos adicionais de problemas sem solução computável.
O estudo de construções matemáticas que podem ser realizadas efetivamente é às vezes chamado de matemática recursiva; o livro Handbook of Recursive Mathematics (Ershov et al. 1998) cobre muitos dos resultados conhecidos neste campoErshov, Yuri L.; Goncharov, Sergei S.; Nerode, Anil; Remmel, Jeffrey B. (Eds.). (1998). Handbook of Recursive Mathematics. Volumes 1 and 2. North-Holland..
Computabilidade de Turing
A forma principal de computabilidade estudada na teoria da recursão foi introduzida por Turing (1936). Um conjunto de números naturais é dito ser um conjunto computável (também chamado de decidível, recursivo ou conjunto Turing computável) se existe uma Máquina de Turing que, dado um número n, para com saída 1 se n está no conjunto e para com saída 0 se n não está no conjuntoOdifreddi, Piergiorgio (1989). Classical Recursion Theory. Volume 1. North-Holland. p. 5.. Uma função f dos números naturais para eles mesmos é uma função recursiva ou (Turing) computável se existe uma máquina de Turing que, com entrada n, para e retorna f(n). O uso de máquinas de Turing aqui não é estritamente necessário: existem muitos outros modelos de computação que têm o mesmo poder de computação que máquinas de Turing; por exemplo, as funções μ-recursivas obtidas da recursão primitiva e do operador μ.
A terminologia para funções recursivas e conjuntos não é completamente padronizadaSoare, Robert I. (1996). "Computability and Recursion". Bulletin of Symbolic Logic. 2 (3): 283–305.. A definição em termos de funções μ-recursivas, bem como uma definição diferente de funções recursivas de Gödel, levou à tradicional palavra "recursividade" para conjuntos e funções computáveis por máquinas de Turing. A palavra "decidibilidade" nasce da palavra alemã Entscheidungsproblem, que foi usada nos artigos originais de Turing e outros. Atualmente, o termo "função computável" tem uma variedade de definições: de acordo com Cutland (1980), é uma função parcialmente recursiva (que pode ser indefinida para algumas entradas), enquanto de acordo com Soare (1987) é uma função recursiva total (equivalentemente, recursiva geral). Este artigo segue a segunda convenção. Soare (1996) deu comentários adicionais a respeito da terminologia.
Nem todo conjunto de números naturais é computável. O Problema da parada, que é um conjunto de (descrições de) máquinas de Turing que param com entrada 0, é um exemplo bem conhecido de conjunto não-computável. A existência de muitos conjuntos não-computáveis segue dos fatos de que existem somente muitas máquinas de Turing contáveis, logo somente muitos conjuntos computáveis contáveis, mas existem muitos conjuntos de números naturais incontáveis.
Apesar de o problema da parada não ser computável, é possível simular a execução do programa e produzir uma lista infinita de programas que param. Logo, o problema da parada é um exemplo de um conjunto recursivamente enumerável (também conhecido como computavelmente enumerável ou semidecidível), que é um conjunto que pode ser enumerado por uma máquina de Turing. Equivalentemente, um conjunto é recursivamente enumerável se e somente se ele for a imagem de alguma função computável. Os conjuntos recursivamente enumeráveis, embora não decidíveis em geral, têm sido estudados em detalhes na teoria da recursão.
Áreas de Pesquisa
Começando com a teoria dos conjuntos recursivos e funções descritas abaixo, o ramo da teoria da recursão tem crescido de forma a abranger o estudo de vários tópicos relacionados. Essas áreas não são independentes de pesquisa: cada uma delas utiliza ideias e resultados das outras, e muitos teóricos da recursividade possuem familiaridade com a maioria delas. Computabilidade Relativa e os Graus de Turing
A teoria da recursão na lógica matemática tem tradicionalmente ênfase na computabilidade relativa, uma generalização da computabilidade de Turing definida utilizando máquinas de Turing com oráculo, introduzidas por Turing (1939)Turing, Alan M. (1939). "Systems of Logic Based on Ordinals". Proceedings of the London Mathematical Society. 2 (45): 161–228.. Uma máquina de Turing com oráculo é um dispositivo hipotético que, além de realizar as ações de uma máquina de Turing regular, é capaz de fazer perguntas a um oráculo, que é um conjunto particular de números naturais. A máquina oráculo deve apenas fazer perguntas da forma "n está no conjunto oráculo?". Cada questão será imediatamente respondida corretamente, mesmo se o conjunto oráculo não for computável. Assim, uma máquina oráculo com um oráculo não-computável será capaz de computar conjuntos que não são computáveis sem um oráculo.
Informalmente, um conjunto de números naturais A é Turing redutível para um conjunto B se existe uma máquina oráculo que diz corretamente se números estão em A quando executados com B como um conjunto oráculo (neste caso, o conjunto A é também dito ser (relativamente) computável de B e recursivo em B). Se um conjunto A é Turing redutível para um conjunto B e B é Turing redutível a A, então os conjuntos são ditos terem o mesmo grau de Turing (também chamado de grau de indecidibilidade). O grau de Turing de um conjunto dá uma medida precisa de quão não-computável esse conjunto é.
Os exemplos naturais de conjuntos que não são computáveis, incluindo vários conjuntos diferentes que codificam variantes do problema da parada, possuem duas propriedades em comum: Eles são recursivamente enumeráveis. Cada um pode ser transformado em outro através de uma redução de muitos-um. Isto é, dados tais conjuntos A e B, existe uma função total computável f tal que A = {x : f(x) ∈ B}. Esses conjuntos são ditos serem muitos-um equivalentes (ou m-equivalentes).
Reduções muitos-um são "mais fortes" que reduções de Turing: se um conjunto A é muitos-um redutível a um conjunto B, então A é Turing redutível a B, mas o contrário nem sempre é verdadeiro. Embora exemplos naturais de conjuntos não-computáveis sejam todos muitos-um equivalentes, é possível construir recursivamente conjuntos enumeráveis A e B tal que A é Turing redutível a B mas não muitos-um redutível a B. Pode-se mostrar que todo conjunto recursivamente enumerável é muitos-um redutível ao problema da parada, e assim o problema da parada é o conjunto recursivamente enumerável mais complicado com respeito à redutibilidade muitos-um e com respeito à Turing redutibilidade.