Teoria da computabilidade

Teoria da Computação

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 Turing. 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 conjuntos.

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?" [2]. 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ção.

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 artigo. 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ção. 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 efetivo. Esses resultados levaram Stephen Kleene (1952) a cunhar os termos "Tese de Church" e "Tese de Turing". 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ável. Apesar de ser inicialmente cético, Gödel argumentou a favor dessa tese por volta de 1946.

Citação: Tarski enfatizou nesta lição (e eu pensei justamente) a grande importância do conceito de recursividade geral (ou computabilidade de Turing). Parece-me que esta importância é grande devido ao fato de que, com esse conceito, pela primeira vez foi dada uma noção absoluta para uma noção epistemologicamente interessante, i.e., não dependendo do formalismo escolhido.

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ível. 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 iniciais. Em 1947, Markov e Post publicaram artigos independentes mostrando que o problema da palavra para semigrupos não pode ser efetivamente decidido. 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 grupo. 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 inteiros. 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 campo.

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 conjunto. 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 padronizada. 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). 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.

Post (1944) questionou se todo conjunto recursivamente enumerável é tanto computável quanto Turing equivalente ao problema da parada, ou seja, se não existe conjunto recursivamente enumerável com um grau de Turing intermediário entre os dois. Esse problema se tornou conhecido como o problema de Post. Como resultados intermediários, Post definiu tipos naturais de conjuntos recursivamente enumeráveis como conjuntos simples, supersimples e supersupersimples. Post mostrou que esses conjuntos estão estritamente entre os conjuntos computáveis e o problema da parada com respeito à redutibilidade muitos-um. Post mostrou também que alguns deles são estritamente intermediários sob outras noções de redutibilidade mais fortes que a redutibilidade de Turing.

Porém, Post deixou em aberto o principal problema da existência de conjuntos recursivamente enumeráveis do grau intermediário de Turing. Após dez anos, Kleene e Post mostraram em 1954 que existem graus intermediários de Turing entre aqueles dos conjuntos computáveis e o problema da parada, mas eles não conseguiram mostrar que algum desses graus contém um conjunto recursivamente enumerável. Pouco tempo depois, Friedberg e Muchnik resolveram independentemente o problema de Post, estabelecendo a existência de conjuntos recursivamente enumeráveis de grau intermediário. Essa inovação resultou na abertura de uma grande área de estudo dos graus de Turing dos conjuntos recursivamente enumeráveis que passaram a possuir uma estrutura muito complicada e não-trivial.

Existem muitos conjuntos incontáveis que não são recursivamente enumeráveis, e a investigação dos graus de Turing de todos esses conjuntos é tão importante na teoria da recursão quanto a investigação dos graus de Turing recursivamente enumeráveis. Muitos graus com propriedades especiais foram construídos: graus livres de superimunidade onde toda função computável relativa àquele grau é majorizada por uma (não-relativizada) função computável; altos graus relativos aos quais se pode computar a função f que domina toda função computável g no sentido de que existe uma constante c dependendo de g tal que g(x) < f(x) para todo x > c; graus aleatórios contendo conjuntos algoritmicamente aleatórios; graus 1-genéricos de conjuntos 1-genéricos; e os graus abaixo do problema da parada dos conjuntos limite-recursivos.

O estudo de graus de Turing arbitrários (não necessariamente recursivamente enumeráveis) envolve o estudo do salto de Turing. Dado um conjunto A, o salto de Turing de A é um conjunto de números naturais codificando uma solução para o problema da parada para máquinas de Turing oráculo rodando com um oráculo A. O salto de Turing de qualquer conjunto é sempre de um grau mais alto de Turing que o do conjunto original, e o teorema de Friedberg mostra que qualquer conjunto que computa o problema da parada pode ser obtido como o salto de Turing de outro conjunto. O teorema de Post estabelece um relacionamento próximo entre a operação do salto de Turing e a hierarquia aritmética, que é uma classificação de certos subconjuntos dos números naturais baseados nas suas definibilidades na aritmética.

Várias pesquisas recentes nos graus de Turing têm focado na estrutura global do conjunto dos graus de Turing e o conjunto dos graus de Turing contendo conjuntos recursivamente enumeráveis. Um teorema específico de Shore e Slaman (1999) estabelece que a função que mapeia um grau x para um grau do seu salto de Turing é definível na ordem parcial dos graus de Turing. Um estudo recente de Ambos-Spies e Fejer (2006) dá uma visão dessa pesquisa e sua progressão histórica.

Outras Redutibilidades

Uma área contínua de pesquisa em teoria da recursão estuda relações de redutibilidade que não são redutibilidades de Turing. Post (1944) introduziu várias redutibilidades fortes, nomeadas assim porque elas implicam na redutibilidade de tabela-verdade. Uma máquina de Turing implementando uma redutibilidade forte vai computar uma função total, independentemente de com qual oráculo ela é apresentada. Redutibilidades fracas são aquelas onde o processo de redução talvez não termine para todos os oráculos; redutibilidade de Turing é um exemplo.

As redutibilidades fortes incluem:

• Redutibilidade um-um (1-redutibilidade): A é um-um redutível a B se existe uma função injetiva total computável f tal que cada n está em A se e somente se f(n) está em B.
• Redutibilidade muitos-um (m-redutibilidade): é essencialmente a redutibilidade um-um sem a condição de f ser injetiva. A é muitos-um redutível a B se existe uma função computável total tal que cada n está em A se e somente se f(n) está em B.
• Redutibilidade tabela-verdade: A é tabela-verdade redutível a B se A é Turing redutível a B através de uma máquina de Turing oráculo que computa uma função total independentemente do oráculo dado. Por causa da compactação do espaço de Cantor, isso é equivalente a dizer que a redução apresenta uma lista única de perguntas (dependendo somente da entrada) para o oráculo simultaneamente, e assim, tendo visto as respostas, é capaz de produzir uma saída sem perguntas adicionais independentemente da resposta do oráculo para as consultas iniciais. Muitas variantes da tabela-verdade redutibilidade têm sido estudadas também.

O principal estudo nas redutibilidades fortes tem sido para comparar suas teorias, tanto para a classe de todos os conjuntos recursivamente enumeráveis quanto para a classe de todos os subconjuntos dos números naturais. Além disso, as relações entre as redutibilidades têm sido estudadas. Por exemplo, é sabido que todo grau de Turing é tanto um grau tabela-verdade quanto uma união de infinitos muitos graus tabela-verdade.

Redutibilidades mais fracas que a redutibilidade de Turing (isto é, redutibilidades que estão implícitas por Turing redutibilidade) também têm sido estudadas. As mais conhecidas são redutibilidade aritmética e redutibilidade hiperaritmética. Essas redutibilidades estão fortemente conectadas com definibilidade sob o modelo padrão da aritmética.

Teorema de Rice e a Hierarquia Aritmética

Rice mostrou que para toda classe C não-trivial (que contém alguns, mas não todos os conjuntos recursivamente enumeráveis) o índice E = {e: o n-ésimo conjunto r.e. We está em C} tem uma propriedade que tanto o problema da parada quanto seu complemento são muitos-um redutíveis a E (veja o teorema de Rice para mais detalhes). Porém, muitos desses conjuntos de índices são ainda mais complicados que o problema da parada. Esses tipos de conjuntos podem ser classificados utilizando a hierarquia aritmética. Por exemplo, o conjunto de índices FIN de uma classe de todos os conjuntos finitos está no nível Σ2, o conjunto de índices REC da classe de todos os conjuntos recursivos está no nível Σ3, o conjunto de índices COFIN de todos os conjuntos cofinitos está também no nível Σ3 e o conjunto de índices COMP da classe de todos os conjuntos Turing-completos em Σ4. Esses níveis de hierarquia são definidos indutivamente, onde Σn+1 contém exatamente todos os conjuntos que são recursivamente enumeráveis relativo a Σn; Σ1 contém todos os conjuntos recursivamente enumeráveis. Os conjuntos de índices dados aqui são ainda mais completos para seus níveis, ou seja, todos os conjuntos nesses níveis podem ser muitos-um reduzidos para o conjunto de índices dados.

Matemática Reversa

O programa de matemática reversa pergunta quais axiomas de existência dos conjuntos são necessários para provar teoremas particulares da matemática em subsistemas de aritmética de segunda ordem. Esse estudo se iniciou por Harvey Friedman e foi estudado em detalhes por Stephen G. Simpson e outros; Simpson (1999) oferece uma discussão detalhada do programa. Os axiomas de existência de conjuntos em questão correspondem informalmente a axiomas que afirmam que a força do conjunto dos números naturais está relacionada com variadas noções de redutibilidade. O axioma mais fraco estudado em matemática reversa é a compreensão recursiva, que estabelece que a força do conjunto dos naturais está um pouco abaixo da redutibilidade de Turing.

Numerações

Uma numeração é uma enumeração de funções; possui dois parâmetros, e e x, e fornece como saída o valor da e-ésima função na numeração da entrada x. Numerações podem ser recursivas parciais, embora alguns de seus membros sejam recursivos totais, ou seja, funções computáveis. Numerações aceitáveis ou de Gödel são aquelas onde todas as outras podem ser transformadas. Uma numeração de Friedberg (nomeada após sua descoberta) é uma numeração um-um de todas as funções recursivas parciais; é necessariamente uma numeração não aceitável. Pesquisas posteriores lidaram também com numerações de outras classes, como classes de conjuntos recursivamente enumeráveis. Goncharov descobriu, por exemplo, uma classe de conjuntos recursivamente enumeráveis na qual as numerações se dividiram em exatamente duas classes com respeito a isomorfismos recursivos.

O Método da Prioridade

O problema de Post foi solucionado com um método chamado método da prioridade; uma prova usando esse método é chamada de argumento de prioridade. Esse método é primeiramente usado para construir recursivamente conjuntos enumeráveis com propriedades particulares. Para utilizar esse método, as propriedades desejadas do conjunto a ser construído são divididas em uma lista infinita de itens, chamados de requisitos, tal que satisfazendo todos os requisitos, o conjunto construído terá as propriedades desejadas. A cada requisito é atribuído um número natural que representa a prioridade desse requisito; então 0 é atribuído ao item mais importante, 1 ao segundo mais importante, e assim por diante. O conjunto é então construído em estágios, cada estágio com o intuito de satisfazer um ou mais requisitos através de adição de números ao conjunto ou eliminação de números do conjunto para que o conjunto final satisfaça o requisito. É provável que o fato de satisfazer um requerimento cause a não-satisfação de outro; a ordem de prioridade é usada para decidir o que fazer em um evento.

Argumentos de prioridade têm sido empregados para resolução de muitos problemas na teoria da recursão, e têm sido classificados em uma hierarquia baseada em suas complexidades (Soare 1987). Pelo fato de argumentos de prioridade complexos poderem ser técnicos e difíceis de acompanhar, tem-se tradicionalmente considerado desejável a prova de resultados sem argumentos de prioridade, ou para ver se os resultados provados com argumentos de prioridade podem também ser provados sem eles. Por exemplo, Kummer publicou um artigo em uma prova para existência das numerações de Friedberg sem usar o método de prioridade.

A Estrutura dos Conjuntos Recursivamente Enumeráveis

Quando Post definiu a noção de um conjunto simples como um conjunto recursivamente enumerável (r.e.), ele começou a estudar a estrutura dos conjuntos recursivamente enumeráveis sob inclusão. Essa estrutura se tornou muito conhecida. Conjuntos recursivos podem ser definidos nessa estrutura pelo resultado básico de que um conjunto é recursivo se e somente se o conjunto e seu complemento são ambos recursivamente enumeráveis. Infinitos conjuntos r.e. possuem sempre subconjuntos recursivos; por outro lado, conjuntos simples existem, mas não têm um superconjunto recursivo co-infinito.

Post (1944) introduziu conjuntos hipersimples e hiper-hipersimples; posteriormente, conjuntos r.e. máximos foram construídos de tal forma que todo superconjunto r.e. é tanto uma variante finita do conjunto máximo dado quanto cofinito. A motivação original de Post no estudo dessa estrutura era encontrar uma noção estrutural tal que todo conjunto que satisfizesse essa propriedade não pertencesse ao grau de Turing dos conjuntos recursivos nem ao grau de Turing do problema da parada. Post não encontrou essa propriedade e, em vez disso, a solução para o seu problema aplicou métodos de prioridade; Harrington e Soare (1991) eventualmente encontraram uma propriedade.

Problemas de Automorfismo

Outra questão importante é a existência de automorfismos em estruturas teórico-recursivas. Uma dessas estruturas é a dos conjuntos recursivamente enumeráveis sob inclusão do módulo de diferenças finitas; nessa estrutura, A está abaixo de B se e somente se o conjunto de diferenças B - A é finito. Conjuntos máximos (de acordo com a definição do parágrafo anterior) têm a propriedade de que eles não podem ser automorfismos para conjuntos não-máximos, ou seja, se existe um automorfismo dos conjuntos recursivamente enumeráveis sob a estrutura mencionada, então todo conjunto máximo é mapeado para outro conjunto máximo. Soare (1974) mostrou que o inverso também se mantém, ou seja, todo par de conjuntos máximos é automorfismo. Assim, os conjuntos máximos formam uma órbita, ou seja, todo automorfismo preserva maximalidade e quaisquer dois conjuntos máximos são transformados uns nos outros através de um automorfismo. Harrington deu outro exemplo de uma propriedade automorfica: os conjuntos criativos, que são muitos-um equivalentes ao problema da parada.

Além da estrutura dos conjuntos recursivamente enumeráveis, automorfismos também são estudados para a estrutura dos graus de Turing de todos os conjuntos, bem como para a estrutura dos graus de Turing dos conjuntos r.e.. Em ambos os casos, Cooper alega ter construído automorfismos não-triviais que mapeiam alguns graus em outros graus; contudo, essa construção não tem sido verificada e alguns estudiosos acreditam que a construção contém erros e que a questão da existência de um automorfismo não-trivial nos graus de Turing ainda é uma das principais questões não-resolvidas nessa área (Slaman e Woodin 1986, Ambos-Spies e Fejer 2006).

A Complexidade de Kolmogorov

O ramo da complexidade de Kolmogorov e aleatoriedade algorítmica foi desenvolvido durante as décadas de 1960 e 1970 por Chaitin, Kolmogorov, Levin, Martin-Löf e Solomonoff (os nomes são dados aqui em ordem alfabética; muitas das pesquisas foram independentes, e a unidade do conceito de aleatoriedade não foi compreendida na época). A ideia principal é considerar uma máquina de Turing universal U e medir a complexidade de um número (ou string) x como o tamanho da menor entrada p tal que U(p) gera x como saída. Esta abordagem revolucionou os métodos conhecidos até então para determinar quando uma sequência infinita (equivalentemente, função característica do subconjunto dos números naturais) é aleatória ou não, invocando uma noção de aleatoriedade para objetos finitos. A complexidade de Kolmogorov tornou-se não só tema de estudo independente, mas também foi aplicada a outros temas como ferramenta de obtenção de provas. Existem ainda muitos problemas em aberto nessa área. Por essa razão, uma conferência de pesquisa recente nessa área foi realizada em janeiro de 2007 e uma lista de problemas abertos é mantida por Joseph Miller e Andre Nies.

Cálculo da Frequência

Esse ramo da teoria da recursão analisou a seguinte questão: para fixos m e n com 0 < m < n, para quais funções A é possível computar para quaisquer entradas n diferentes x1, x2, ..., xn uma tupla de n números y1, y2, ..., yn tal que ao menos m das equações A(xk) = yk sejam verdadeiras. Tais conjuntos são conhecidos como conjuntos (m,n)-recursivos. O primeiro principal resultado nesse ramo da teoria da recursão é o resultado de Trakhtenbrot, onde um conjunto é computável se ele for (m,n)-recursivo para algum m,n com 2m > n. Por outro lado, os conjuntos semirrecusivos de Jockusch (os quais já eram conhecidos informalmente antes de Jockusch introduzi-los em 1968) são exemplos de um conjunto o qual é (m,n)-recursivo se e somente se 2m < n + 1. Existem muitos desses conjuntos e também alguns recursivamente enumeráveis, mas conjuntos não-computáveis desse tipo. Posteriormente, Degtev estabeleceu uma hierarquia de conjuntos recursivamente enumeráveis que são (1, n + 1)-recursivos, mas não (1, n)-recursivos. Após um longo tempo de pesquisas realizadas por cientistas russos, esse tema se popularizou no ocidente com a tese de Beigel em consultas limitadas, as quais relacionaram cálculo de frequência com as redutibilidades limitadas mencionadas anteriormente e outras noções relacionadas. Um dos principais resultados foi a Teoria de Cardinalidade de Kummer, segundo a qual um conjunto A é computável se e somente se existe um n tal que algum algoritmo enumera para cada tupla de n números diferentes até n possíveis escolhas da cardinalidade desse conjunto de n números intersectado com A; essas escolhas devem conter a cardinalidade verdadeira, mas descartar ao menos uma falsa.

Inferência Indutiva

Esse é o ramo teórico-recursivo da teoria da aprendizagem. É baseado no modelo de Gold de aprendizado do limite de 1967 e tem sido desenvolvidos desde então muitos e muitos modelos de aprendizado. O cenário geral é o seguinte: Dada uma classe S de funções computáveis, existe um aprendiz (isto é, funcional recursivo) que dá como saída para qualquer entrada da forma (f(0), f(1), ..., f(n)) uma hipótese. Um aprendiz M aprende a função f se quase todas as hipóteses têm o mesmo índice e de f com respeito ao acertado anteriormente em uma numeração aceitável de todas as funções computáveis; M aprende S se M aprende todo f em S. Resultados básicos são todos os conjuntos recursivamente enumeráveis de dados positivos, que são um tópico estudado do artigo pioneiro de Gold em 1967 em diante.

Generalizações da Computabilidade de Turing

A teoria da recursão inclui o estudo de noções generalizadas desse tópico, como redutibilidade aritmética, redutibilidade hiperaritmética e a teoria α-recursão, como descrito por Sacks (1990). Essas noções generalizadas incluem redutibilidades que não podem ser executadas por máquinas de Turing, mas não obstante são generalizações naturais da redutibilidade de Turing. Esses estudos incluem aproximações para investigar a hierarquia analítica, que difere da hierarquia aritmética através da permissão da quantificação sob conjuntos de números naturais em adição à quantificação sob números individuais. Essas áreas estão relacionadas às teorias de formação de palavras; por exemplo, o conjunto de todos os índices de árvores (não-binárias) recursivas sem ramos infinitos é completo para o nível da hierarquia analítica. Tanto a redutibilidade quanto a redutibilidade hiperaritmética são importantes no ramo da teoria descritiva dos conjuntos. Uma noção ainda mais geral de graus de construtibilidade é estudada na teoria dos conjuntos.

Teoria da Computabilidade Contínua

A teoria da computabilidade para computação digital é bem desenvolvida. A teoria da computabilidade é menos bem desenvolvida para computação analógica que ocorre em computadores analógicos, processamento de sinal analógico, eletrônica analógica, redes neurais e teoria de controle de tempo contínuo, modelados por diferentes equações e sistemas dinâmicos contínuos.

Relacionamentos entre Definibilidade, Prova e Computabilidade

Existem fortes ligações entre os graus de Turing de um conjunto de números naturais e a dificuldade (em termos da hierarquia aritmética) em definir o conjunto usando fórmula de primeira ordem. Um relacionamento é feito precisamente pelo teorema de Post. Um relacionamento mais fraco foi demonstrado por Kurt Gödel nas provas do seu teorema da completude e teoremas de incompletude. As provas de Gödel mostram que o conjunto de consequências lógicas de uma teoria efetiva de primeira ordem é um conjunto recursivamente enumerável, e que se a teoria é forte o suficiente, esse conjunto será não computável. Similarmente, o teorema da indefinibilidade de Tarski pode ser interpretado tanto em termos de definibilidade quanto em termos de computabilidade.

A teoria da recursão também está relacionada com a aritmética de segunda ordem, uma teoria formal dos números naturais e conjuntos de números naturais. O fato de que certos conjuntos são computáveis ou relativamente computáveis frequentemente implica que esses conjuntos podem ser definidos em fracos subsistemas de aritmética de segunda ordem. O programa de matemática reversa usa esses subsistemas para medir a não-computabilidade herdada em teoremas matemáticos conhecidos. Simpson (1999) discute vários aspectos de aritmética de segunda ordem e matemática reversa.

O ramo da teoria da prova inclui o estudo da aritmética de segunda ordem e da aritmética de Peano, bem como teorias formais dos números naturais mais fracas que a aritmética de Peano. Um método de classificar a força desses sistemas fracos é caracterizando as funções computáveis que o sistema pode provar serem totais (veja Fairtlough e Wainer (1998)). Por exemplo, a recursividade primitiva, enquanto a aritmética de Peano prova que funções como a de Ackermann, as quais não são recursivas primitivas, são totais. Nem toda função total computável é comprovadamente total na aritmética de Peano, contudo; um exemplo de uma função é obtido pelo teorema de Goodstein.

Nome do tema

O campo de lógica matemática lidando com computabilidade e suas generalizações tem sido chamado "teoria da recursão" desde os antepassados. Robert I. Soare, um proeminente pesquisador no ramo, tem proposto (Soare 1996) que o ramo deve ser chamado na verdade "teoria da computabilidade" . Ele argumenta que a terminologia de Turing usando a palavra "computável" é mais natural e mais abrangente entendida do que a terminologia usando a palavra "recursiva" introduzida por Kleene. Muitos pesquisadores contemporâneos também usam a terminologia como função parcial computável e conjunto computável enumerável (c.e.) ao invés de função parcial recursiva e conjunto recursivamente enumerável (r.e.). Nem todos os pesquisadores têm se convencido, contudo, como explicado por Fortnow e Simpson. Alguns comentaristas argumentam que tanto os nomes teoria da recursão e teoria da computabilidade falharam em transmitir que o fato que a maioria dos objetos estudados em teoria da recursão não são computáveis.

Rogers (1967) tem sugerido que uma propriedade chave da teoria da recursão é que seus resultados e estruturas devam ser invariantes sob bijeções computáveis nos números naturais (essa sugestão desenha nas ideias do programa de Erlangen em geometria). A ideia é que uma bijeção computável apenas renomeia números em um conjunto, ao invés de indicar alguma estrutura no conjunto, como uma rotação do plano Euclidiano não muda nenhum aspecto geométrico das linhas desenhadas nele. Uma vez que quaisquer dois conjuntos infinitos computáveis são interligados por uma bijeção computável, essa proposta identifica todos os conjuntos computáveis infinitos (os conjuntos finitos computáveis são vistos como triviais). De acordo com Rogers, os conjuntos de interesse em teoria da recursão são conjuntos não computáveis, particionados em classes de equivalência por bijeções computáveis dos números naturais.

Organizações profissionais

A principal organização profissional para teoria da recursão é a Association for Symbolic Logic, a qual mantém muitas conferências todo ano. A CiE(Association Computability in Europe) também organiza uma série de conferências anuais. CiE 2012 será a Turing Centenary Conference, mantida em Cambridge como parte do Alan Turing Year.