Teoria da computabilidade - Computability theory

A teoria da computabilidade , também conhecida como teoria da recursão , é um ramo da lógica matemática , da ciência da computação e da teoria da computação que se originou na década de 1930 com o estudo de funções computáveis e graus de Turing . O campo desde então se expandiu para incluir o estudo de computabilidade generalizada e definibilidade. Nessas áreas, a teoria da computabilidade se sobrepõe à teoria da prova e à teoria dos conjuntos descritivos eficazes .

As questões básicas abordadas pela teoria da computabilidade incluem:

  • O que significa uma função nos números naturais ser computável?
  • Como as funções não-computáveis ​​podem ser classificadas em uma hierarquia com base em seu nível de não-computável?

Embora haja uma sobreposição considerável em termos de conhecimento e métodos, os teóricos da computabilidade matemática estudam a teoria da computabilidade relativa, noções de redutibilidade e estruturas de grau; aqueles no campo da ciência da computação enfocam a teoria das hierarquias sub-cursivas , métodos formais e linguagens formais .

Conjuntos computáveis ​​e incomputáveis

A teoria da computabilidade teve origem na década de 1930, com o trabalho de Kurt Gödel , Alonzo Church , Rózsa Péter , Alan Turing , Stephen Kleene e Emil Post .

Os resultados fundamentais obtidos pelos pesquisadores estabeleceram a computabilidade de Turing como a formalização correta da ideia informal de cálculo efetivo. Esses resultados levaram Stephen Kleene (1952) a cunhar os dois nomes "tese de Church" (Kleene 1952: 300) e "Tese de Turing" (Kleene 1952: 376). Hoje em dia, essas são frequentemente 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 . Embora inicialmente cético, em 1946 Gödel argumentou a favor desta tese:

"Tarski enfatizou em sua palestra (e eu acho que com razão) a grande importância do conceito de recursividade geral (ou computabilidade de Turing). Parece-me que essa importância se deve em grande parte ao fato de que, com este conceito, temos pelo primeiro o tempo conseguiu dar uma noção absoluta a uma noção epistemológica interessante, ou seja, uma que não depende do formalismo escolhido. * "(Gödel 1946 em Davis 1965: 84).

Com uma definição de cálculo eficaz, vieram as primeiras provas de que existem problemas em matemática que não podem ser resolvidos de forma eficaz . Church (1936a, 1936b) e Turing (1936), inspirados nas técnicas utilizadas por Gödel (1931) para provar seus teoremas da incompletude, demonstraram de forma independente que o Entscheidungsproblem não é efetivamente decidível. Este 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 em matemática se mostraram indecidíveis depois que esses exemplos iniciais foram estabelecidos. Em 1947, Markov and Post publicou artigos independentes mostrando que o problema da palavra para semigrupos não pode ser efetivamente decidido. Estendendo este resultado, Pyotr Novikov e William Boone mostraram de forma independente na década de 1950 que o problema da palavra para grupos não é efectivamente resolvidas: não há um procedimento eficaz que, dada uma palavra em um número finito apresentada grupo , vai decidir se o elemento representado pela palavra é o elemento de identidade do grupo. Em 1970, Yuri Matiyasevich provou (usando os resultados de Julia Robinson ) o teorema de Matiyasevich , que implica que o décimo problema de Hilbert não tem solução eficaz; este problema perguntou se existe um procedimento eficaz para decidir se uma equação diofantina sobre os inteiros tem uma solução nos inteiros. A lista de problemas indecidíveis fornece exemplos adicionais de problemas sem solução computável.

O estudo de quais construções matemáticas podem ser efetivamente realizadas é às vezes chamado de matemática recursiva ; o Handbook of Recursive Mathematics (Ershov et al. 1998) cobre muitos dos resultados conhecidos neste campo.

Computabilidade de Turing

A principal forma de computabilidade estudada na teoria da computabilidade foi introduzida por Turing (1936). Um conjunto de números naturais é considerado um conjunto computável (também chamado de conjunto decidível , recursivo ou computável de Turing ) se houver uma máquina de Turing que, dado um número n , para com a saída 1 se n estiver no conjunto e para com saída 0 se n não estiver no conjunto. Uma função F a partir de números naturais para números naturais é um (Turing) calculável , ou função recursiva se existe uma máquina de Turing que, na entrada n , pára e regressa saída 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 das máquinas de Turing; por exemplo, as funções μ-recursivas obtidas da recursão primitiva e o operador μ.

A terminologia para funções e conjuntos computáveis ​​não é completamente padronizada. A definição em termos de funções μ-recursivas, bem como uma definição diferente de funções rekursiv por Gödel, levou ao nome tradicional recursivo para conjuntos e funções computáveis ​​por uma máquina de Turing. A palavra decidível deriva da palavra alemã Entscheidungsproblem que foi usada nos artigos originais de Turing e outros. No uso contemporâneo, o termo "função computável" tem várias definições: de acordo com Cutland (1980), é uma função recursiva parcial (que pode ser indefinida para algumas entradas), enquanto de acordo com Soare (1987) é uma recursiva total ( equivalentemente, função recursiva geral). Este artigo segue a segunda dessas convenções. Soare (1996) fornece comentários adicionais sobre a terminologia.

Nem todo conjunto de números naturais é computável. O problema da parada , que é o conjunto de (descrições de) máquinas de Turing que param na entrada 0, é um exemplo bem conhecido de um conjunto não-computável. A existência de muitos conjuntos não computáveis ​​decorre do fato de que existem apenas contáveis ​​muitas máquinas de Turing e, portanto, apenas contáveis ​​muitos conjuntos computáveis, mas de acordo com o teorema de Cantor , existem incontáveis ​​muitos conjuntos de números naturais.

Embora o problema da parada não seja computável, é possível simular a execução do programa e produzir uma lista infinita dos programas que param. Assim, o problema da parada é um exemplo de um conjunto computavelmente enumerável (ce) , que é um conjunto que pode ser enumerado por uma máquina de Turing (outros termos para computavelmente enumerável incluem recursivamente enumerável e semidecidível ). Equivalentemente, um conjunto é ce se, e somente se, for o intervalo de alguma função computável. Os conjuntos ce, embora não sejam decidíveis em geral, foram estudados em detalhes na teoria da computabilidade.

Áreas de pesquisa

Começando com a teoria de conjuntos computáveis ​​e funções descritas acima, o campo da teoria da computabilidade cresceu para incluir o estudo de muitos tópicos intimamente relacionados. Essas não são áreas independentes de pesquisa: cada uma dessas áreas extrai ideias e resultados das outras, e a maioria dos teóricos da computabilidade está familiarizada com a maioria delas.

Computabilidade relativa e os graus de Turing

A teoria da computabilidade em lógica matemática tem tradicionalmente focado na computabilidade relativa , uma generalização da computabilidade de Turing definida usando máquinas de Turing oracle , introduzida por Turing (1939). Uma máquina de Turing oráculo é um dispositivo hipotético que, além de realizar as ações de uma máquina de Turing normal, é capaz de fazer perguntas a um oráculo , que é um conjunto particular de números naturais. A máquina oracle só pode fazer perguntas da forma "Está n no conjunto oracle?". Cada pergunta será imediatamente respondida corretamente, mesmo se o conjunto do 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 uma máquina de Turing sem um oráculo não pode.

Informalmente, um conjunto de números naturais A é Turing redutível a um conjunto B se houver uma máquina oráculo que diga corretamente se os números estão em A quando executado com B como o 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 a um conjunto B e B é Turing redutível a A, então os conjuntos são considerados como tendo o mesmo grau de Turing (também chamado de grau de insolubilidade ). O grau de Turing de um conjunto fornece uma medida precisa de quão incomputável o conjunto é.

Os exemplos naturais de conjuntos que não são computáveis, incluindo muitos conjuntos diferentes que codificam variantes do problema de parada , têm duas propriedades em comum:

  1. Eles são computáveis ​​enumeráveis e
  2. Cada um pode ser traduzido em qualquer outro por meio de uma redução muitos-um . Ou seja, dados esses conjuntos A e B , existe uma função computável total f tal que A = { x  : f ( x ) ∈ B }. Esses conjuntos são considerados muitos-um equivalente (ou m-equivalente ).

As reduções muitos-um são "mais fortes" do que as reduções de Turing: se um conjunto A é redutível muitos-um a um conjunto B , então A é redutível de Turing a B , mas o inverso nem sempre é válido. Embora os exemplos naturais de conjuntos não-computáveis são todos muitos-um equivalente, é possível construir conjuntos computably enumeráveis A e B de tal modo que um é Turing redutível a B mas não muitos-redutível a um B . Pode ser mostrado que cada conjunto enumerável computável é muitos-um redutível ao problema da parada e, portanto, o problema da parada é o mais complicado conjunto computavelmente enumerável com respeito à redutibilidade muitos-um e com respeito à redutibilidade de Turing. Post (1944) perguntou se todo conjunto enumerável computável é computável ou equivalente de Turing ao problema da parada, isto é, se não há conjunto enumerável computável com um grau de Turing intermediário entre aqueles dois.

Como resultados intermediários, Post definiu tipos naturais de conjuntos computáveis ​​enumeráveis ​​como os conjuntos simples , hiper- simples e hiper- simples . Post mostrou que esses conjuntos estão estritamente entre os conjuntos computáveis ​​e o problema da parada com respeito à redutibilidade muitos-um. Post também mostrou que alguns deles são estritamente intermediários sob outras noções de redutibilidade mais fortes do que a redutibilidade de Turing. Mas Post deixou em aberto o problema principal da existência de conjuntos computavelmente enumeráveis ​​de grau de Turing intermediário; esse problema ficou conhecido como problema de Post . Depois de dez anos, Kleene e Post mostraram em 1954 que existem graus de Turing intermediários entre aqueles dos conjuntos computáveis ​​e o problema da parada, mas eles falharam em mostrar que qualquer um desses graus contém um conjunto computável enumerável. Logo depois disso, Friedberg e Muchnik resolveram independentemente o problema de Post, estabelecendo a existência de conjuntos computáveis ​​enumeráveis ​​de grau intermediário. Este resultado inovador abriu um amplo estudo dos graus de Turing dos conjuntos computáveis ​​enumeráveis ​​que revelaram possuir uma estrutura muito complicada e não trivial.

Existem incontáveis ​​muitos conjuntos que não são computavelmente enumeráveis, e a investigação dos graus de Turing de todos os conjuntos é tão central na teoria da computabilidade quanto a investigação dos graus de Turing computavelmente enumeráveis. Muitos graus com propriedades especiais foram construídos: graus hiperimune-livre onde cada função computável relativa a esse grau é majorizada por uma função computável (não relativizada); altos graus em relação aos quais se pode calcular uma 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 algorítmicos aleatórios ; 1- graus genéricos de 1-conjuntos genéricos; e os graus abaixo do problema de parada de conjuntos computáveis de limite .

O estudo de graus de Turing arbitrários (não necessariamente computáveis) envolve o estudo do salto de Turing. Dado um conjunto A , o salto de Turing de Um é um conjunto de números naturais que codificam uma solução para o problema da paragem para máquinas de Turing Oracle rodando com a Oracle Uma . O salto de Turing de qualquer conjunto é sempre de grau de Turing mais alto do que o conjunto original, e um teorema de Friedburg mostra que qualquer conjunto que calcula o problema de Halting pode ser obtido como o salto de Turing de outro conjunto. O teorema de Post estabelece uma relação estreita entre a operação de salto de Turing e a hierarquia aritmética , que é uma classificação de certos subconjuntos dos números naturais com base em sua definibilidade em aritmética.

Muitas pesquisas recentes sobre graus de Turing enfocaram a estrutura geral do conjunto de graus de Turing e o conjunto de graus de Turing contendo conjuntos computáveis ​​enumeráveis. Um teorema profundo de Shore e Slaman (1999) afirma que a função que mapeia um grau x ao grau de seu salto de Turing é definível na ordem parcial dos graus de Turing. Uma pesquisa recente de Ambos-Spies e Fejer (2006) oferece uma visão geral dessa pesquisa e sua progressão histórica.

Outras redutibilidades

Uma área de pesquisa em andamento na teoria da computabilidade estuda relações de redutibilidade além da redutibilidade de Turing. Post (1944) introduziu várias redutibilidades fortes , assim chamadas porque implicam em redutibilidade de tabela de verdade. Uma máquina de Turing implementando uma forte redutibilidade computará uma função total, independentemente de com qual oráculo ela é apresentada. Redutibilidades fracas são aquelas em que um processo de redução pode não terminar para todos os oráculos; A redutibilidade de Turing é um exemplo.

As fortes redutibilidades incluem:

Redutibilidade um-um
Um é um-um redutível (ou 1-redutível ) para B , se houver um total de calculável função injetivo f de tal modo que cada n é de um , se e somente se f ( n ) é em B .
Redutibilidade muitos-um
Este é essencialmente um-um redutibilidade sem a restrição de que f ser injective. Um é muitas-ona redutível (ou m-redutível ) para B , se há uma função calculável total de f de tal modo que cada n é de um , se e somente se f ( n ) é em B .
Redutibilidade da mesa da verdade
A é uma tabela de verdade redutível a B se A é Turing redutível a B por meio de uma máquina de Turing oráculo que calcula uma função total independentemente do oráculo que ela é fornecida. Devido à compactação do espaço do Cantor , isso equivale a dizer que a redução apresenta uma única lista de perguntas (dependendo apenas da entrada) ao oráculo simultaneamente, e então tendo visto suas respostas é capaz de produzir uma saída sem fazer perguntas adicionais independentemente da resposta do oráculo às perguntas iniciais. Muitas variantes da redutibilidade da tabela de verdade também foram estudadas.

Outras redutibilidades (positiva, disjuntiva, conjuntiva, linear e suas versões fraca e limitada) são discutidas no artigo Redução (teoria da computabilidade) .

A principal pesquisa sobre redutibilidades fortes consistiu em comparar suas teorias, tanto para a classe de todos os conjuntos computáveis ​​enumeráveis ​​quanto para a classe de todos os subconjuntos dos números naturais. Além disso, as relações entre as redutibilidades foram estudadas. Por exemplo, sabe-se que cada grau de Turing é um grau da tabela de verdade ou é a união de um número infinito de graus da tabela de verdade.

Redutibilidades mais fracas do que a redutibilidade de Turing (isto é, redutibilidades que estão implícitas na redutibilidade de Turing) também foram estudadas. As mais conhecidas são a redutibilidade aritmética e a redutibilidade hiperaritmética . Essas redutibilidades estão intimamente ligadas à definibilidade sobre o modelo padrão da aritmética.

Teorema de Rice e a hierarquia aritmética

Arroz mostraram que, para todas as classes não trivial C (que contém alguns, mas nem todos os conjuntos ce) o índice conjunto E = { e : o e po ce conjunto W e é em C } tem a propriedade de que, quer o problema da paragem ou o seu complemento é muitas -um redutível a E , isto é, pode ser mapeado usando uma redução muitos-um a E (consulte o teorema de Rice para obter mais detalhes). Porém, muitos desses conjuntos de índices são ainda mais complicados do que o problema da parada. Esses tipos de conjuntos podem ser classificados usando a hierarquia aritmética . Por exemplo, o conjunto de índices FIN da 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 também está no nível Σ 3 e o conjunto de índice COMP da classe de todos os conjuntos completos de Turing Σ 4 . Esses níveis de hierarquia são definidos indutivamente, Σ n +1 contém apenas todos os conjuntos que são computavelmente enumeráveis ​​em relação a Σ n ; Σ 1 contém os conjuntos enumeráveis ​​computáveis. Os conjuntos de índices fornecidos aqui são completos para seus níveis, ou seja, todos os conjuntos nesses níveis podem ser muitos e um reduzidos aos conjuntos de índices fornecidos.

Matemática reversa

O programa da matemática reversa pergunta quais axiomas de existência de conjunto são necessários para provar teoremas particulares da matemática em subsistemas de aritmética de segunda ordem . Este estudo foi iniciado por Harvey Friedman e foi estudado em detalhes por Stephen Simpson e outros; Simpson (1999) apresenta uma discussão detalhada do programa. Os axiomas de existência de conjunto em questão correspondem informalmente a axiomas que dizem que o conjunto de poderes dos números naturais é fechado sob várias noções de redutibilidade. O mais fraco desses axiomas estudados na matemática reversa é a compreensão recursiva , que afirma que o conjunto de poderes dos naturais é fechado sob redutibilidade de Turing.

Numerações

Uma numeração é uma enumeração de funções; tem dois parâmetros, e e x e emite o valor de a e função -ésimo na numeração na entrada x . As numerações podem ser computáveis ​​parcialmente, embora alguns de seus membros sejam funções computáveis ​​totais. Numerações admissíveis são aquelas para as quais todas as outras podem ser traduzidas. Uma numeração de Friedberg (nomeada em homenagem a seu descobridor) é uma numeração um-um de todas as funções computáveis ​​parciais; não é necessariamente uma numeração admissível. Pesquisas posteriores lidaram também com numerações de outras classes, como classes de conjuntos enumeráveis ​​computáveis. Goncharov descobriu, por exemplo, uma classe de conjuntos enumeráveis ​​computáveis ​​para os quais as numerações caem em exatamente duas classes com respeito a isomorfismos computáveis.

O método de prioridade

O problema de Post foi resolvido com um método chamado método de prioridade ; uma prova usando esse método é chamada de argumento de prioridade . Este método é usado principalmente para construir conjuntos enumeráveis ​​computáveis ​​com propriedades particulares. Para utilizar este método, as propriedades desejadas do conjunto a ser construído são desdobradas em uma lista infinita de objetivos, conhecidos como requisitos , de forma que atender a todos os requisitos fará com que o conjunto construído tenha as propriedades desejadas. Cada requisito é atribuído a um número natural que representa a prioridade do requisito; portanto, 0 é atribuído à prioridade mais importante, 1 à segunda mais importante e assim por diante. O conjunto é então construído em estágios, cada estágio tentando satisfazer um ou mais dos requisitos, adicionando números ao conjunto ou banindo números do conjunto para que o conjunto final satisfaça o requisito. Pode acontecer que a satisfação de um requisito faça com que outro se torne insatisfeito; a ordem de prioridade é usada para decidir o que fazer em tal evento.

Argumentos de prioridade foram empregados para resolver muitos problemas na teoria da computabilidade e foram classificados em uma hierarquia com base em sua complexidade (Soare 1987). Porque argumentos de prioridade complexos podem ser técnicos e difíceis de seguir, tradicionalmente tem sido considerado desejável provar resultados sem argumentos de prioridade, ou ver se os resultados provados com argumentos de prioridade também podem ser provados sem eles. Por exemplo, Kummer publicou um artigo sobre uma prova da existência de numerações de Friedberg sem usar o método de prioridade.

A rede de conjuntos enumeráveis ​​computáveis

Quando Post definiu a noção de um conjunto simples como um conjunto ce com um complemento infinito não contendo nenhum conjunto ce infinito, ele começou a estudar a estrutura dos conjuntos computáveis ​​enumeráveis ​​sob inclusão. Esta rede tornou-se uma estrutura bem estudada. conjuntos computáveis ​​podem ser definidos nesta estrutura pelo resultado básico de que um conjunto é computável se e somente se o conjunto e seu complemento são enumeráveis ​​computavelmente. Conjuntos de ce infinitos têm sempre subconjuntos computáveis ​​infinitos; mas, por outro lado, conjuntos simples existem, mas nem sempre têm um superconjunto computável coinfinito. Post (1944) já introduziu conjuntos hipersimples e hiperhipersimple; posteriormente, foram construídos conjuntos máximos, que são conjuntos ce tais que cada superconjunto ce é uma variante finita do conjunto máximo dado ou é co-finito. A motivação original de Post no estudo desta rede foi encontrar uma noção estrutural tal que cada conjunto que satisfaça esta propriedade não esteja nem no grau de Turing dos conjuntos computáveis ​​nem no grau de Turing do problema da parada. Post não encontrou essa propriedade e a solução para seu problema aplicou métodos de prioridade; Harrington e Soare (1991) encontraram eventualmente tal propriedade.

Problemas de automorfismo

Outra questão importante é a existência de automorfismos em estruturas teóricas da computabilidade. Uma dessas estruturas é aquela de conjuntos computavelmente enumeráveis ​​sob o módulo de inclusão de diferença finita; nesta estrutura, A está abaixo de B se e somente se a diferença de conjunto B  -  A for finita. Conjuntos máximos (conforme definido no parágrafo anterior) têm a propriedade de não poderem ser automórficos para conjuntos não maximais, ou seja, se houver um automorfismo dos conjuntos enumeráveis ​​computáveis ​​sob a estrutura recém mencionada, então cada conjunto máximo é mapeado para outro conjunto máximo. Soare (1974) mostrou que também o inverso é válido, ou seja, todos os dois conjuntos máximos são automórficos. Assim, os conjuntos máximos formam uma órbita, ou seja, todo automorfismo preserva a maximalidade e quaisquer dois conjuntos máximos são transformados um no outro por algum automorfismo. Harrington deu outro exemplo de propriedade automórfica: a dos conjuntos criativos, os conjuntos que são muitos-um equivalentes ao problema da parada.

Além da rede de conjuntos computavelmente enumeráveis, os 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 de ce. Em ambos os casos, Cooper afirma ter construído automorfismos não triviais que mapeiam alguns graus para outros graus; esta construção, no entanto, não foi verificada e alguns colegas acreditam que a construção contém erros e que a questão de saber se há um automorfismo não trivial dos graus de Turing ainda é uma das principais questões não resolvidas nesta área (Slaman e Woodin 1986, Ambos-Spies e Fejer 2006).

Complexidade de Kolmogorov

O campo da complexidade de Kolmogorov e aleatoriedade algorítmica foi desenvolvido durante os anos 1960 e 1970 por Chaitin, Kolmogorov, Levin, Martin-Löf e Solomonoff (os nomes são dados aqui em ordem alfabética; grande parte da pesquisa era independente e a unidade do conceito de aleatoriedade não foi compreendido 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 comprimento da entrada mais curta p tal que U ( p ) produz x . Esta abordagem revolucionou as formas anteriores de determinar quando uma sequência infinita (equivalentemente, função característica de um 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 apenas um assunto de estudo independente, mas também é aplicada a outros assuntos como uma ferramenta para obter provas. Ainda existem muitos problemas em aberto nesta área. Por esse motivo, uma recente conferência de pesquisa nesta área foi realizada em janeiro de 2007 e uma lista de problemas em aberto é mantida por Joseph Miller e Andre Nies.

Cálculo de freqüência

Este ramo da teoria da computabilidade analisou a seguinte questão: Para m e n fixos com 0 <  m  <  n , para as quais as funções A é possível calcular para quaisquer n entradas diferentes x 1x 2 , ...,  x n uma tupla de n números y 1 , y 2 , ..., y n de modo que pelo menos m das equações A ( x k ) = y k sejam verdadeiras. Esses conjuntos são conhecidos como conjuntos ( mn ) -recursivos. O primeiro resultado importante neste ramo da teoria da computabilidade é o resultado de Trakhtenbrot de que um conjunto é computável se for ( mn ) -recursivo para algum mn com 2 m  >  n . Por outro lado, os conjuntos semirecursivos de Jockusch (que já eram conhecidos informalmente antes de Jockusch os apresentar em 1968) são exemplos de um conjunto que é ( mn ) -recursivo se e somente se 2 m  <  n  + 1. Existem incontáveis ​​muitos de esses conjuntos e também alguns conjuntos computáveis ​​enumeráveis, mas não computáveis, desse tipo. Posteriormente, Degtev estabeleceu uma hierarquia de conjuntos computáveis ​​enumeráveis ​​que são (1,  n  + 1) -recursivos, mas não (1,  n ) -recursivos. Após uma longa fase de pesquisa por cientistas russos, este assunto foi repopularizado no oeste pela tese de Beigel sobre consultas limitadas, que vinculava o cálculo de frequência às redutibilidades limitadas mencionadas acima e outras noções relacionadas. Um dos principais resultados foi a Teoria da Cardinalidade de Kummer, que afirma que um conjunto A é computável se e somente se houver um n tal que algum algoritmo enumera para cada tupla de n números diferentes até n muitas escolhas possíveis da cardinalidade deste conjunto de n números interseccionados com A ; essas opções devem conter a cardinalidade verdadeira, mas deixar de fora pelo menos uma falsa.

Inferência indutiva

Este é o ramo teórico da computabilidade da teoria da aprendizagem. É baseado no modelo de aprendizagem no limite de E. Mark Gold de 1967 e tem desenvolvido cada vez mais modelos de aprendizagem. O cenário geral é o seguinte: Dada uma classe S de funções computáveis, existe um aluno (isto é, funcional computável) que produz para qualquer entrada da forma ( f (0), f (1), ..., f ( n )) uma hipótese. Um aprendiz M aprende uma função f se quase todas as hipóteses são o mesmo índice e de f em relação a uma numeração aceitável previamente acordada de todas as funções computáveis; M aprende S se M aprende cada f em S . Os resultados básicos são que todas as classes de funções computáveis ​​enumeráveis ​​podem ser aprendidas, enquanto a classe REC de todas as funções computáveis ​​não pode ser aprendida. Muitos modelos relacionados foram considerados e também o aprendizado de classes de conjuntos computáveis ​​enumeráveis ​​a partir de dados positivos é um tópico estudado do artigo pioneiro de Gold de 1967 em diante.

Generalizações da computabilidade de Turing

a teoria da computabilidade inclui o estudo de noções generalizadas desse campo, como redutibilidade aritmética , redutibilidade hiperaritmética e teoria α-recursão , conforme descrito por Sacks (1990). Essas noções generalizadas incluem redutibilidades que não podem ser executadas por máquinas de Turing, mas são generalizações naturais da redutibilidade de Turing. Esses estudos incluem abordagens para investigar a hierarquia analítica que difere da hierarquia aritmética por permitir a quantificação sobre conjuntos de números naturais, além da quantificação sobre números individuais. Essas áreas estão ligadas às teorias de ordenações e árvores; por exemplo, o conjunto de todos os índices de árvores computáveis ​​(não binárias) sem ramificações infinitas está completo para o nível da hierarquia analítica. Tanto a redutibilidade de Turing quanto a redutibilidade hiperaritmética são importantes no campo da teoria de conjuntos descritivos eficaz . A 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 está bem desenvolvida. Teoria Computability é menos bem desenvolvido para o cálculo analógico que ocorre em computadores analógicos , processamento de sinal analógico , electrónica analógica , redes neurais e de tempo contínuo teoria de controlo , modelada por equações diferenciais e contínuas sistemas dinâmicos (Orponen 1997; Moore, 1996).

Relações entre definibilidade, prova e computabilidade

Existem relações estreitas entre o grau de Turing de um conjunto de números naturais e a dificuldade (em termos de hierarquia aritmética ) de definir esse conjunto usando uma fórmula de primeira ordem . Uma dessas relações é tornada precisa pelo teorema de Post . Uma relação mais fraca foi demonstrada por Kurt Gödel nas provas de seu teorema da completude e teoremas da incompletude . As provas de Gödel mostram que o conjunto de consequências lógicas de uma teoria de primeira ordem eficaz é um conjunto computávelmente enumerável e que, se a teoria for forte o suficiente, esse conjunto será incomputável. Da mesma forma, o teorema da indefinibilidade de Tarski pode ser interpretado tanto em termos de definibilidade quanto em termos de computabilidade.

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

O campo 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 fracos do que a aritmética de Peano. Um método de classificar a força desses sistemas fracos é caracterizar quais funções computáveis ​​o sistema pode provar ser total (ver Fairtlough e Wainer (1998)). Por exemplo, na aritmética recursiva primitiva, qualquer função computável que seja comprovadamente total é na verdade recursiva primitiva , enquanto a aritmética de Peano prova que funções como a função de Ackermann , que não são recursivas primitivas, são totais. No entanto, nem toda função computável total é comprovadamente total na aritmética de Peano; um exemplo de tal função é fornecido pelo teorema de Goodstein .

Nome

O campo da lógica matemática que lida com computabilidade e suas generalizações tem sido chamado de "teoria da recursão" desde seus primeiros dias. Robert I. Soare , um proeminente pesquisador na área, propôs (Soare 1996) que o campo deveria ser chamado de "teoria da computabilidade". Ele argumenta que a terminologia de Turing usando a palavra "computável" é mais natural e mais amplamente compreendida do que a terminologia usando a palavra "recursiva" introduzida por Kleene. Muitos pesquisadores contemporâneos começaram a usar essa terminologia alternativa. Esses pesquisadores também usam terminologia como função computável parcial e conjunto ( ce ) enumerável computável em vez de função recursiva parcial e conjunto ( re ) enumerável recursivamente . Nem todos os pesquisadores foram convencidos, no entanto, como explicado por Fortnow e Simpson. Alguns comentaristas argumentam que os nomes teoria da recursão e teoria da computabilidade falham em transmitir o fato de que a maioria dos objetos estudados na teoria da computabilidade não são computáveis.

Rogers (1967) sugeriu que uma propriedade chave da teoria da computabilidade é que seus resultados e estruturas devem ser invariáveis ​​sob bijeções computáveis nos números naturais (esta sugestão baseia-se nas idéias do programa Erlangen em geometria). A ideia é que uma bijeção computável meramente renomeia números em um conjunto, ao invés de indicar qualquer estrutura no conjunto, da mesma forma que uma rotação do plano euclidiano não muda nenhum aspecto geométrico das linhas desenhadas nele. Uma vez que quaisquer dois conjuntos computáveis ​​infinitos são ligados por uma bijeção computável, esta proposta identifica todos os conjuntos computáveis ​​infinitos (os conjuntos computáveis ​​finitos são vistos como triviais). De acordo com Rogers, os conjuntos de interesse na teoria da computabilidade são os 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 a teoria da computabilidade é a Association for Symbolic Logic , que realiza várias conferências de pesquisa a cada ano. A pesquisa interdisciplinar Association Computability in Europe ( CiE ) também organiza uma série de conferências anuais.

Veja também

Notas

Referências

Textos de graduação
Textos avançados
Artigos de pesquisa e coleções
Artigos de pesquisa e coleções

links externos