Teoria da computabilidade

começando com a teoria dos conjuntos recursivos e funções descritas acima, o campo da teoria da recursão cresceu para incluir o estudo de muitos tópicos intimamente relacionados. Estas não são áreas independentes de pesquisa: cada uma dessas áreas atrai ideias e resultados dos outros, e a maioria dos teóricos da recursão está familiarizada com a maioria deles.

computabilidade Relativa e Turing degreesEdit

Recursion theory in mathematical logic has traditally focused on relative computability, a generalization of Turing computability defined using oracle Turing machines, introduced by Turing (1939). Uma máquina de Turing oracle é um dispositivo hipotético que, além de executar as ações de uma máquina de Turing regular, é capaz de fazer perguntas de um oracle, que é um conjunto particular de Números Naturais. A máquina oracle só pode fazer perguntas do formulário ” Is n In The oracle set?”. Cada pergunta será respondida imediatamente corretamente, mesmo que o conjunto oracle não seja computável. Assim, uma máquina oracle com um oracle não-computável será capaz de computar conjuntos que uma máquina de Turing sem um oracle não pode.

Informalmente, um conjunto de números naturais A é Turing redutível a um conjunto B se a é um oracle máquina que corretamente indica se os números estão em Um momento de executar com B como o oracle conjunto (neste caso, o conjunto A é dito ser (relativamente) computável a partir de B e recursiva em B). Se um conjunto A é Turing redutível para um conjunto B E B é Turing redutível para A então os conjuntos são ditos ter o mesmo grau de Turing (também chamado grau de unsolvibilidade). O grau de Turing de um conjunto dá uma medida precisa de como o conjunto não é computável.

natural exemplos de conjuntos que não são computáveis, incluindo vários conjuntos diferentes que codificam as variantes de travar o problema, tem duas propriedades em comum:

1. Eles são recursivamente enumerável, e
2. Cada um pode ser traduzido em qualquer outro meio de muitos-uma redução. Isto é, dado tais conjuntos A E B, há uma função computável total f tal que a = {x : f(x) ∈ B}. Estes conjuntos são ditos ser muitos-um equivalente (ou M-equivalente).

reduções de muitos-Um são “mais fortes” do que reduções de Turing: se um conjunto A é muitos-um redutível para um conjunto B, Então A é Turing redutível para B, mas o inverso nem sempre se mantém. Embora os exemplos naturais de conjuntos não-computáveis sejam todos muitos-um equivalentes, é possível construir recursivamente conjuntos enumeráveis a e B tais que A é Turing redutível a B, mas não muitos-um redutível a B. Pode ser mostrado que a cada recursivamente enumerável conjunto é de muitos-um redutível para a parada problema, e, assim, a suspensão problema é mais complicado recursivamente enumerável a respeito de muitos-uma reducibility e com respeito a Turing reducibility. Post (1944) perguntou se todo conjunto recursivamente enumerável é computável ou Turing equivalente ao problema da parada, ou seja, se não existe um conjunto recursivamente enumerável com um grau de Turing intermediário entre esses dois.

como resultados intermediários, os tipos naturais pós definidos de conjuntos recursivamente enumeráveis como os conjuntos simples, hipersimples e hiperperipersimples. Post mostrou que esses conjuntos estão estritamente entre os conjuntos computáveis e o problema da parada com relação à redutibilidade de muitos-um. Post também mostrou que alguns deles são estritamente intermediários sob outras noções de redutibilidade mais fortes que a redutibilidade de Turing. Mas Post deixou aberto o principal problema da existência de conjuntos recursivamente enumeráveis de grau de Turing intermediário; este problema tornou-se 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 não conseguiram mostrar que qualquer um destes graus contém um conjunto recursivamente enumerável. Logo depois disso, Friedberg e Muchnik resolveram independentemente o problema de Post, estabelecendo a existência de conjuntos recursivamente enumeráveis de grau intermediário. Este resultado inovador abriu um amplo estudo dos graus de Turing dos conjuntos recursivamente enumeráveis que acabaram por possuir uma estrutura muito complicada e não trivial.

existem incontáveis muitos conjuntos que não são recursivamente enumeráveis, e a investigação dos graus de Turing de todos os conjuntos é tão central 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 hiperimune onde cada função computável relativa a esse grau é majorada por uma função computável (não relativizada) ; os altos graus em relação ao qual pode-se calcular uma função f que domina todos os computável função g no sentido de que existe uma constante c, dependendo de g tais que g(x) < f(x) para todo x > c; aleatório graus contendo, através de algoritmos de conjuntos aleatórios; 1-genérico graus de 1-genérico conjuntos; e graus abaixo a suspensão problema de limite-recursiva conjuntos.

the study of arbitrary (not necessarily recursively enumerable) Turing degrees involves the study of The Turing jump. Dado um conjunto A, o salto de Turing é um conjunto de números naturais de codificação de uma solução para a parada problema para oracle máquinas de Turing em execução com o oracle A. Turing saltar de qualquer conjunto é sempre de maior grau de Turing que o conjunto original, e um teorema de Friedburg mostra que qualquer conjunto que calcula a Travar, o problema pode ser obtida como o salto de Turing de um outro conjunto. O teorema de Post estabelece uma relação próxima entre a operação do salto de Turing e a hierarquia aritmética, que é uma classificação de certos subconjuntos dos números naturais com base em sua definibilidade na aritmética.

muita pesquisa recente sobre graus de Turing tem focado na estrutura geral do conjunto de graus de Turing e o conjunto de graus de Turing contendo conjuntos recursivamente enumeráveis. Um teorema profundo de Shore e Slaman (1999) afirma que a função mapeando 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) dá uma visão geral desta pesquisa e sua progressão histórica.Outras reducibilidadesedit

An ongoing area of research in recursion theory studies reducibility relations other than Turing reducibility. Post (1944) introduziu várias reducibilidades fortes, assim chamadas porque elas implicam reducibilidade de tabela-verdade. Uma máquina de Turing implementando uma redutibilidade forte irá computar uma função total independentemente de qual oráculo ela é apresentada. Reducibilidades fracas são aquelas onde um processo de redução não pode terminar para todos os oráculos; reducibilidade de Turing é um exemplo.

as reducibilidades fortes incluem::

redutibilidade um-um A é redutível um-um(ou 1-redutível) para B Se existe uma função injetiva computável total f tal que cada n está em um se e somente se f (n) está em B. redutibilidade muitos-um isto é essencialmente uma redutibilidade um-um sem a restrição que f seja injetiva. A é redutível por muitos-um (ou M-redutível) a B Se existe uma função computável total f tal que cada n está em a se e somente se f (n) está em B. Redutibilidade da tabela-verdade A é redutível para B se A é Turing redutível para B através de uma máquina de Turing oracle que computa uma função total independentemente do oracle que é dado. Devido a compacidade do Cantor espaço, isto é equivalente a dizer que a redução apresenta uma única lista de perguntas (dependendo apenas da entrada) para o oracle simultaneamente e, em seguida, depois de terem visto as respostas é capaz de produzir uma saída sem a formulação de perguntas adicionais, independentemente da oracle de resposta para as consultas iniciais. Muitas variantes da redutibilidade da tabela-verdade também foram estudadas.

outras reducibilidades (positivas, disjuntivas, conjuntivas, lineares e suas versões fracas e limitadas) são discutidas na redução do artigo (teoria da recursão).

a principal pesquisa sobre reducibilidades fortes tem sido comparar suas teorias, tanto para a classe de todos os conjuntos recursivamente enumeráveis, bem como para a classe de todos os subconjuntos dos números naturais. Além disso, as relações entre as reducibilidades foram estudadas. Por exemplo, sabe-se que todo grau de Turing é ou um grau de tabela-verdade ou é a união de infinitamente muitos graus de tabela-verdade.

Reducibilidades mais fracas que Turing reducibilidade (isto é, reducibilidades que são implícitas pela Turing reducibilidade) também foram estudadas. As mais conhecidas são reducibilidade aritmética e reducibilidade hiperaritmética. Estas reducibilidades estão intimamente ligadas à definibilidade sobre o modelo padrão da aritmética.

Arroz teorema e a aritmética hierarchyEdit

Arroz mostrou que, para cada tarefa não trivial de classe C (que contém alguns, mas não todos r.e. define) o índice de conjunto E = {e: a eth r.e. conjunto de Nós em C} tem a propriedade de que a interrupção do problema ou o seu complemento é muitos-um redutível a de E, isto é, pode ser mapeada usando um muitos-uma redução de a E (ver Arroz teorema para mais detalhes). Mas, muitos desses conjuntos de índices são ainda mais complicados do que o problema da parada. Estes tipos de conjuntos podem ser classificados usando a hierarquia aritmética. Por exemplo, o índice set FIN de classe de todos os conjuntos finitos é o nível Σ2, o índice definido REC da classe de todos os recursiva define é o nível Σ3, o índice definido COFIN de todos os cofinite define também está no nível de Σ3 e o índice definido COMP da classe de todos os Turing-completos Σ4. Estes níveis de hierarquia são definidos indutivamente, Σn+1 contém apenas todos os conjuntos que são recursivamente enumeráveis em relação a Σn; Σ1 contém os conjuntos recursivamente enumeráveis. Os conjuntos de índice indicados aqui são mesmo completos para seus níveis, ou seja, todos os conjuntos nesses níveis podem ser muitos-um reduzido para os conjuntos de índice dado.

Inverter mathematicsEdit

O programa de inverter matemática pede que defina-existência axiomas são necessárias para provar certos teoremas da matemática em subsistemas de segunda ordem aritmética. Este estudo foi iniciado por Harvey Friedman e foi estudado em detalhe por Stephen Simpson e outros; Simpson (1999) dá uma discussão detalhada do programa. Os axiomas da existência dos conjuntos em questão correspondem informalmente a axiomas dizendo que o conjunto dos números naturais é fechado sob várias noções de redutibilidade. O axioma mais fraco estudado na matemática reversa é a compreensão recursiva, que afirma que o conjunto de potências dos naturais está fechado sob a redutibilidade de Turing.

Numeringsedit

uma numeração é uma enumeração de funções; tem dois parâmetros, e E x e produz o valor da e-ésima função na numeração na entrada X. Numerações podem ser parcialmente recursivas, embora alguns de seus membros sejam recursivas totais, ou seja, funções computáveis. Números admissíveis são aqueles em que todos os outros podem ser traduzidos. Uma numeração Friedberg (nomeada em homenagem ao seu descobridor) é uma numeração única de todas as funções parcialmente recursivas; não é necessariamente uma numeração admissível. Pesquisas posteriores também trataram de números de outras classes como classes de conjuntos recursivamente enumeráveis. Goncharov descobriu, por exemplo, uma classe de conjuntos recursivamente enumeráveis para os quais os números caem em exatamente duas classes com respeito a isomorfismos recursivos.

the priority methodEdit

For further explanation, see the section Post’s problem and the priority method in the article Turing degree.

o problema de Post foi resolvido com um método chamado de método de prioridade; uma prova usando este método é chamado de argumento de prioridade. Este método é usado principalmente para construir recursivamente conjuntos enumeráveis com propriedades particulares. Para usar este método, as propriedades desejadas do conjunto a ser construído são divididas em uma lista infinita de objetivos, conhecidos como requisitos, de modo que satisfazer 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; assim, 0 é atribuído à prioridade mais importante, 1 ao segundo mais importante, e assim por diante. O conjunto é então construído em etapas, cada etapa tentando satisfazer um de mais dos requisitos, adicionando números ao conjunto ou banindo números do conjunto de modo que o conjunto final irá satisfazer o requisito. Pode acontecer que satisfazer um requisito Faça com que outro fique insatisfeito; a ordem de prioridade é usada para decidir o que fazer em tal evento.

argumentos prioritários foram empregados para resolver muitos problemas na teoria da recursão, e foram classificados em uma hierarquia baseada em sua complexidade (Soare 1987). Uma vez que argumentos prioritários complexos podem ser técnicos e difíceis de seguir, tradicionalmente tem sido considerado desejável provar resultados sem argumentos prioritários, ou para ver se os resultados provados com argumentos prioritários também podem ser provados sem eles. Por exemplo, Kummer publicou um artigo sobre uma prova da existência de números Friedberg sem usar o método de prioridade.

malha de recursivamente enumerável setsEdit

Quando Postar definida a noção de um conjunto simples como um r.e. conjunto com uma infinita complementar não contendo qualquer infinito r.e. set, he started to study the structure of the recursively enumerable sets under inclusion. Esta estrutura tornou-se uma estrutura bem estudada. Conjuntos recursivos podem ser definidos nesta 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. Conjuntos r.e. infinitos têm sempre subconjuntos recursivos infinitos; mas por outro lado, conjuntos simples existem, mas não têm um superconjunto recursivo coinfinito. Post (1944) introduziu já conjuntos hiper simples e hiper simples; mais tarde conjuntos máximos foram construídos que são conjuntos R. E. tais que cada R. E. superconjunto é uma variante finita do conjunto máximo dado ou é co-finito. A motivação original de Post no estudo desta estrutura foi encontrar uma noção estrutural tal que todo conjunto que satisfaz esta propriedade não está nem no grau de Turing dos conjuntos recursivos nem no grau de Turing do problema da parada. Post não encontrou tal propriedade e a solução para o seu problema aplicou métodos prioritários em vez disso; Harrington e Soare (1991) acabaram por encontrar tal propriedade.

automorphism problemsEdit

Another important question is the existence of automorphisms in recursion-theoretic structures. Uma dessas estruturas é que um dos conjuntos recursivamente enumeráveis sob inclusão de diferença finita módulo; nesta estrutura, A é abaixo de B se e somente se a diferença de Conjunto B − A é finita. Conjuntos maximais (como definido no parágrafo anterior) têm a propriedade de que eles não podem ser automórficos para conjuntos não-maximais, isto é, se existe um automorfismo dos conjuntos recursivos enumeráveis sob a estrutura mencionada, então todo conjunto máximo é mapeado para outro conjunto maximal. Soare (1974) mostrou que também o inverso vale, ou seja, cada 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 um outro exemplo de uma propriedade automórfica: a dos conjuntos criativos, os conjuntos que são muitos-um equivalente ao problema da parada.

Além da rede de recursivamente enumerável de conjuntos, automorphisms também são estudados para a estrutura dos graus de Turing de todos os conjuntos, bem como para a estrutura de Turing graus de r.e. conjuntos. 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 foram verificadas e alguns colegas acreditam que a construção contém erros e que a questão de saber se há uma tarefa não trivial automorphism dos graus de Turing é ainda uma das principais por resolver questões nesta área (Slaman e Woodin 1986, Ambos Espiões e Fejer 2006).Complexidadediteedit

O campo de teste de Kolmogorov complexidade e algoritmos aleatoriedade foi desenvolvido durante os anos de 1960 e 1970 por Chaitin, o teste de Kolmogorov, Levin, de Martin-Löf e Solomonoff (os nomes são aqui apresentadas em ordem alfabética; a investigação era independente, e a unidade do conceito de aleatoriedade não foi entendido na época). A idéia principal é considerar uma máquina de Turing universal U e medir a complexidade de um número (ou Cadeia) x como o comprimento da menor entrada p tal que u(p) produz x. Esta abordagem revolucionou anteriores formas de se determinar quando uma seqüência infinita (equivalentemente, função característica de um subconjunto dos números naturais) é aleatória ou não recorrendo a uma noção de aleatoriedade para finitos objetos. Kolmogorov complexity became not only a subject of independent study but is also applied to other subjects as a tool for obtaining proofs.Há ainda muitos problemas em aberto nesta área. Por essa razão, uma recente conferência de investigação nesta área foi realizada em janeiro de 2007 e uma lista de problemas abertos é mantida por Joseph Miller e Andre Nies.

Frequência de computationEdit

Este ramo da recursão teoria analisada a seguinte pergunta: Para fixo m e n, com 0 < m < n, para os quais as funções de Um é possível calcular para qualquer n entradas x1, x2, …, xn a tuple of n numbers y1,y2,…,yn tal que pelo menos m das equações a(xk) = yk são verdadeiras. Tais conjuntos são conhecidos como conjuntos (m, n)-recursivos. O primeiro resultado maior neste ramo da teoria da recursão é o resultado de Trakhtenbrot de que um conjunto é computável se for (m, n)-recursivo para algum m, n com 2m > n. Por outro lado, os conjuntos semirecursivos de Jockusch (que já eram conhecidos informalmente antes de Jockusch os introduzir 1968) são exemplos de um conjunto que é (m, n)-recursivo se e somente se 2m < n + 1. Existem incontáveis muitos desses conjuntos e também alguns recursivamente enumeráveis, mas Conjuntos não-computáveis deste tipo. Mais tarde, Degtev estabeleceu uma hierarquia de conjuntos recursivamente enumeráveis que são (1, n + 1)-recursivos mas não (1, n)-recursivos. Depois de uma longa fase de pesquisa por cientistas russos, este assunto tornou-se repopularizado no Ocidente pela tese de Beigel sobre consultas limitadas, que ligava computação de frequência às reducibilidades delimitadas acima mencionadas e outras noções relacionadas. Um dos principais resultados foi Kummer da Cardinalidade Teoria que diz que um conjunto A é computável se e somente se existe um n tal que o algoritmo de alguns enumera para cada tupla de n números diferentes até n muitas escolhas possíveis da cardinalidade do conjunto de n números cruzaram com Um; estas escolhas devem conter a cardinalidade verdadeira, mas deixar de fora pelo menos uma falsa.

indutive inferenceEdit

This is the recursion-theoretic branch of learning theory. Ele é baseado no modelo de E. Mark Gold de aprendizagem no limite a partir de 1967 e tem desenvolvido desde então mais e mais modelos de aprendizagem. O cenário geral é o seguinte: dada uma classe S de funções computáveis, existe um aprendiz (isto é, funcional recursiva) que produz qualquer entrada da forma (f(0),f(1),…, f(n)) a hypothesis. Um aluno M aprende uma função f se quase que todas as hipóteses são o mesmo índice e de f com respeito a um previamente acordada aceitável a numeração de todas as funções computáveis; M aprende a S se M aprende a cada f em S. Basic resultados são de que todos recursivamente enumerável classes de funções que pode ser aprendida enquanto a classe REC de todas as funções computáveis não se aprende. Muitos modelos relacionados foram considerados e também a aprendizagem de classes de conjuntos recursivamente enumeráveis a partir de dados positivos é um tópico estudado a partir do trabalho pioneiro de Gold em 1967 em diante.

generalizações de Turing computabilityEdit

teoria da recursão inclui o estudo de noções generalizadas deste campo, tais como redutibilidade aritmética, redutibilidade hiperaritmética e teoria Da α-recursão, como descrito por Sacks (1990). Estas noções generalizadas incluem reducibilidades que não podem ser executadas por máquinas de Turing, mas são generalizações naturais da reducibilidade de Turing. Estes estudos incluem abordagens para investigar a hierarquia analítica que difere da hierarquia aritmética, permitindo quantificação sobre conjuntos de números naturais, além de quantificação sobre números individuais. Estas áreas estão ligadas às teorias do bem-ordenações e árvores; por exemplo, o conjunto de todos os índices de forma recursiva (não binários) de árvores sem infinito ramos é completa para o nível Π 1 1 {\displaystyle \Pi _{1}^{1}}

da hierarquia analítica. Tanto a redutibilidade de Turing quanto a redutibilidade hiperaritmética são importantes no campo da teoria descritiva dos conjuntos efetiva. A noção ainda mais geral de graus de construtibilidade é estudada na teoria dos conjuntos.

teoria da computabilidade contínua theoryEdit

teoria da computabilidade para computação digital está bem desenvolvida. A teoria da computabilidade é menos bem desenvolvida para computação analógica que ocorre em computadores analógicos, processamento de sinais analógicos, Eletrônica Analógica, redes neurais e teoria do controle de tempo contínuo, modelada por equações diferenciais e sistemas dinâmicos contínuos (Orponen 1997; Moore 1996).