Teoria da computabilidade

A teoria da computabilidade, também chamada de teoria da recursão, é um ramo da lógica matemática que foi originado na década de 30 com o estudo das funções computáveis e dos graus de Turing. O ramo se estendeu e passou a incluir o estudo generalizado da computabilidade e definibilidade. Nessas áreas, a teoria da recursão sobrepõe-se à teoria da prova e teoria efetiva de descricão dos conjuntos. As questões básicas envolvidas na teoria da recursão são " O que significa para uma funcão(N->N) ser computável?" e "Como funções não-computáveis são classificadas em uma teoria baseada nos seus níveis de não-computabilidade?". As respostas para estas perguntas levaram a uma rica teoria que ainda está sendo estudada atualmente. O ramo se aproximou também com relação à 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 descritas neste artigo. Isto 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 estas duas comunidades de pesquisa. No entanto, não existe uma grande separação entre elas.

Conjuntos computáveis e não computáveis

A teoria da recursão foi originada com o trabalho de Kurt Godel, Alonzo Church, Alan Turing, Stephen Kleene e Emil Post nos anos 30. Os resultados fundamentais que os pesquisadores obtiveram estabeleceram a Turing computabilidade como uma formalização correta da ideia informal do cálculo efetivo. Esses resultados levaram Sthephen Kleene (1952) a unir os dois nomes "Church`s thesis" e "Turing`s Thesis" (p.376). Atualmente, essas hipóteses são consideradas como uma única hipótese, 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, Godel argumentou em favor dessa tese por volta de 1946.

"Tarski enfatizou nesta lição(e eu pensei justamente) na grande importância do conceito de recursividade geral(ou computabilidade de Turing). Parece para mim 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 epistemológica interessante, i.e., não dependendo do formalismo escolhido. "(Godel 1946 em Davis 1965: 84)

Com a definição do cálculo efetivo vieram as primeiras provas que existem problemas na matemática que não podem ser efetivamente dedicidos. Church (1936a, 1936b) e Turing(1936), inspirados por técnicas utilizadas por Godel(1931) para provar seus teoremas de incompletude, demonstraram independentemente que o problema de Entscheidung não é decidido efetivamente. 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 têm sido mostrados serem indecidíveis depois desses exemplos iniciais serem estabelecidos. Em 1947, Markov e Post publicaram artigos independentes mostrando que o problema da palavra para semigrupos não pode ser efetivamente decidida. Ampliando esse resultado, Puotr Novikov e William Boone mostraram independentemente nos anos 50 que o problem 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 questionou 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 pode ser realizado efetivamente e é as 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 pára 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, pára e retorna f(n). O uso de máquinas de Turing aqui não é 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 como também uma definição diferente de funções recursivas de Godel levaram à 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).Esse artigo segue o segundo destas convenções. 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 páram 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 do problema da parada não ser computável, é possível simular a execução do programa e produzir uma lista infinita de programas que páram. Logo, o problema da parada é um exemplo de um conjunto recursivamente enumerável, que é um conjunto que pode ser enumerado por uma máquina de Turing (outros termos para recursividade enumerável inclui computabilidade enumerável e semidecidível). Equivalentemente, um conjunto é recursivamente enumerável se e somente se ele for o "range" de algumas funções computáveis. Os conjuntos recursivamente enumeráveis, apesar de 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 maneira a abranger o estudo de vários tópicos relacionados. Essas áreas não são independentes de pesquisa: cada uma dessas áreas utiliza ideias e resultados das outras, e muitos teóricos da recursividade possuem familiariadade 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 oracle, introduzida por Turing(1939). Uma máquina de Turing oracle é um dispositivo hipotético que, além de realizar as ações de uma máquina de Turing regular, está apta para fazer perguntas de um oracle, que é um conjunto particular de números naturais. A máquina oracle deve só fazer perguntas da forma "n está no conjunto oracle?". Cada questão será imediatamente respondida corretamente, até mesmo se o conjunto oracle não for computável. Assim, uma máquina oracle com um oracle não-computável estará apta para computar conjuntos que não são computáveis sem um oracle. Informalmente, um conjunto de números naturais A é Turing redutível para um conjunto B se existe uma máquina oracle que diz corretamente se números estão em A quando executados com B como um conjunto oracle (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 quando os conjuntos são ditos terem o mesmo grau de Turing (também chamado grau de indecibilidade). O grau de Turing de um conjunto dá uma medida precisa de o 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 in comum:

1. Eles são recursivamente enumeráveis
2. cada um pode ser transformado num 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 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 não é sempre verdadeiro. Apesar de exemplos naturais de conjuntos não-computáveis serem 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 a redutibilidade muitos-um e com respeito a Turing redutibilidade. Post(1944) perguntou se todo conjunto recursivamente enumerável é tanto computável como Turing equivalente ao problema da parada, isto é, se não existe conjunto recursivamente enumerável com um grau de Turing intermediável entre os dois.

Como resultados intermediários, Post definiu tipos naturais de conjuntos recusivamente enumeráveis como conjuntos simples, super simples e super super simples. Post mostrou que esses conjuntos estão estritamente entre os conjuntos computáveis e o problema da parada com respeito a redutibilidade muitos-um. Post mostrou também que alguns deles são estritamente intermediários sob outras noções de redutibilidade mais fortes que Turing redutibilidade. Porém, Post deixou em aberto o principal problema da existência de conjuntos recursivamente enumeráveis do grau intermediário de Turing; esse problema se tornou conhecido como o problema de Post. 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 à aquele grau é majorizada por uma (não-relativizada) função computável; altos graus relativos os quais um 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) for all 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 oracle rodando com um oracle 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 Friedburg 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 mapeia um grau x para um grau do seu salto de Turing é definível na ordem parcial dos graus de Turing. Um recente estudo 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, bastante nomeadas porque elas implicam na redutibilidade de tabela-verdade. Uma máquina de Turing implementando uma redutibilidade sorte vai computar uma função total, independentemente de com qual oracle ela é apresentada. Reducibilidades fracas são aquelas onde o processo de redução talvez não termine para todos os oracles; redutibilidade de Turing é um exemplo.

As redutibilidades fortes incluem: redutibilidade um-um: A é um-um redutível (ou 1-reducí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: é essencialmente a reducibilidade um-um sem a condição de f ser injetiva. A é muitos-um redutível (ou m-reducí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 reducível a B através de uma máquina de Turing oracle que computa uma função total independentemente do oracle dado. Por causa da compactação do espaço de Cantos, isso é equivalente a dizer que a redução apresenta uma lista única de perguntas (dependendo somente da entrada) para o oracle simultaneamente, e assim tendo visto as respostas está apta a produzir uma saída sem perguntas adicionais independentemente da resposta do oracle para as consultas iniciais. Muitas variantes da tabela-verdade redutibilidade tem sido estudadas também.

O principal estudo nas reducibilidades fortes têm sido para comparar suas teorias, tanto para a classe de todos os conjuntos recursivamente enumeráveis como também para a classe de todos os subconjuntos dos números naturais. Além disso, as relações entre as reducibilidades têm sido estudadas. Por exemplo, é sabido que todo grau de Turing é tanto um grau tabela-verdade como uma união de infinitos muitos graus tabela-verdade. Reducibilidades mais fracas que Turing reducibilidade (isto é, reducibilidades que estão implícitas por Turing reducibilidade) têm sido estudadas também. As mais conhecidas são reducibilidade aritmética e reducibilidade hiperaritmética. Essas reducibilidades 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 rodos conjuntos r.e.) o índice E = {e: o n-ésimo conjunto r.e We está em C} tem uma propriedade que tanto o problema da parada como seu complemento é muitos-um reducível a E, isto é, pode ser mapeado utilizando uma redução muitos-um 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 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 co-finitos 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 indutivament, Σ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 dos matemáticos em subsistemas de aritmética de segunda ordem. Esse estudo se iniciou por Harvey Friedman e foi estudado com detalhes por Stephen Simpson e outros; Simpson (1999) dá uma discussão detalhada do programa. Os axiomas de existência de conjuntos em questão correspondem informalmente a axiomas dizendo que a força do conjunto dos números naturais está relacionada com variadas noções de reducibilidade. O axioma mais fraco estudado em matemática reversa é compreensão recursiva, que estabelece que a força do conjunto dos naturais está um pouco abaixo da reducibilidade de Turing.

Numerações

A numeração é uma enumeração de funcões; possui dois parâmetros, e e x e dá como saída o valor da ésima função na numeração da entrada x. Numerações podem ser recursivas parciais apesar de alguns de seus membros serem 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 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 o método da prioridade; um 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 adicionando números ao conjunto ou eliminando 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 de 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 provdos 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 notaçã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 uma estrutura muito conhecida. Conjuntos recursivos podem ser definidos nessa estrutura pelo resultado básico 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) já introduziu conjuntos hiper simples e hiper hiper simples; posteriormente, conjuntos r.e. máximos foram construídos tal que todo super conjunto r.e. é tanto uma variante finita do conjunto máximo dado como também co-finito. A motivação original de Post no estudo dessa estrutura era para encontrar uma noção estrutural tal que todo conjunto que satisfaça essa propriedade não pertença ao grau de Turing dos conjuntos recursivos nem ao grau de Turing do problema da parada. Post não encontrou uma propriedade e ao invés 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 automorfismo em estruturas teórico-recursivas. Uma dessas estruturas é aquela dos conjuntos recursivamente enumeráveis sob inclusão do módulo de diferenças finitas; nessa estrutura, A está abaixo e B se e somente se o conjunto de diferenças B - A é finita. Conjuntos máximos (de acordo com a definição do parágrafo anterior) têm a propriedade de que eles não podem ser automórficos 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 detém, ou seja, todo par de conjuntos máximos é automórfico. Assim, os conjuntos máximos formam uma órbita, ou seja, todo automorfismo preserva maximalidade e qualquer dois conjuntos máximos são transformados uns aos outros através de um automorfismo. Harrington deu outro exemplo de uma propriedade automórfica: os conjuntos criativos, os conjuntos os quais são muitos-um equivalentes ao problema da parada.

Além da estrutura dos conjuntos recursivamente enumeráveis, automorfismos são também estudados para a estrutura dos graus de Turing de todos os conjuntos como também para a estrutura dos graus de Turing dos conjuntos r.e.. Em ambos os casos, Cooper alega ter construído automorfismos não-triviais os quais 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~encia de um automorfismo não-trivial nos graus de Turing é ainda uma das principais questões não-resolvidas nessa área (Slaman and Woodin 1986, Ambos-Spies e Fejer 2006).

A complexidade de Kolmogorov

O ramo da complexidade de Kolmogorov e aleatoriedade algorítmica foi desenvolvido durante a década de 60 e 70 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 entendido no momento). 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 se tornou não só tema do estudo independente mas foi também aplicada para outros temas como uma 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 mantida em janeiro de 2007[2] e uma lista de problemas abertos[3] é 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, ...n 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 semirecursivos 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 reducibilidades 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 enumere 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.

Referência indutiva

Esse é o ramo na 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 é, recursivo funcional) 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 são um tópico estudado do artigo pioneiro de Gold em 1967 avante.

Generalizações da computabilidade de Turing

A teoria da recursão inclu o estudo de noções generalizadas desse tópico como reducibilidade aritmética, reducibilidade hiper aritmética e a teoria α-recursão, como descrito por Sacks (1990). Essas noções generalizadas incluem reducibilidades que não podem ser executadas por máquinas de Turing mas não obstante generalizações naturais da reducibilidade de Turing. Esses estudos incluem aproximações para investigar 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 a 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 reducibilidade e reducibilidade hiper aritmética são importantes no ramo da teoria descritiva dos conjuntos. Uma noção ainda mais geral de graus de construcibilidade é 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 análoga que ocorre em computadores analógicos, sinal de processamento 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. [4][5]

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 um 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 indefibilidade de Tarski pode ser interpretado tanto em termos de definibilidade e em termos de computabilidade.

A teoria da recursão é também 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 implicam 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 a aritmética de Peano, como também 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, em recursividade primitiva, enquanto a aritmética de Peano prova que funções como a de Ackerman, 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[7] e Simpson.[8] 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.[9]

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.

Rogers (1967) has suggested that a key property of recursion theory is that its results and structures should be invariant under computable bijections on the natural numbers (this suggestion draws on the ideas of the Erlangen program in geometry). The idea is that a computable bijection merely renames numbers in a set, rather than indicating any structure in the set, much as a rotation of the Euclidean plane does not change any geometric aspect of lines drawn on it. Since any two infinite computable sets are linked by a computable bijection, this proposal identifies all the infinite computable sets (the finite computable sets are viewed as trivial). According to Rogers, the sets of interest in recursion theory are the noncomputable sets, partitioned into equivalence classes by computable bijections of the natural numbers.

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.