Grau de Turing - Turing degree

Em ciência da computação e lógica matemática, o grau de Turing (em homenagem a Alan Turing ) ou grau de insolvência de um conjunto de números naturais mede o nível de insolvência algorítmica do conjunto.

Visão geral

O conceito de grau de Turing é fundamental na teoria da computabilidade , onde conjuntos de números naturais são freqüentemente considerados problemas de decisão . O grau de Turing de um conjunto é uma medida de quão difícil é resolver o problema de decisão associado ao conjunto, ou seja, determinar se um número arbitrário está no conjunto dado.

Dois conjuntos são equivalentes a Turing se tiverem o mesmo nível de insolvência; cada grau de Turing é uma coleção de conjuntos equivalentes de Turing, de modo que dois conjuntos estão em graus de Turing diferentes exatamente quando não são equivalentes de Turing. Além disso, os graus de Turing são parcialmente ordenados de modo que se o grau de Turing de um conjunto X for menor do que o grau de Turing de um conjunto Y, então qualquer procedimento (não computável) que decida corretamente se os números estão em Y pode ser efetivamente convertido em um procedimento que decide corretamente se os números estão em X . É nesse sentido que o grau de Turing de um conjunto corresponde ao seu nível de insolvência algorítmica.

Os graus de Turing foram introduzidos por Emil Leon Post (1944), e muitos resultados fundamentais foram estabelecidos por Stephen Cole Kleene e Post (1954). Os diplomas de Turing têm sido uma área de intensa pesquisa desde então. Muitas provas na área fazem uso de uma técnica de prova conhecida como método de prioridade .

Equivalência de Turing

No restante deste artigo, a palavra conjunto se referirá a um conjunto de números naturais. Um conjunto X é dito para ser Turing redutível a um conjunto Y se existe uma máquina de Turing a Oracle que decide adesão em X quando dado um Oracle para adesão em Y . A notação XT Y indica que X é Turing redutível para Y .

Dois conjuntos X e Y são definidos para ser Turing equivalente , se X é Turing redutível para Y e Y é Turing redutível a X . A notação XT Y indica que X e Y são equivalentes de Turing. A relação ≡ T pode ser vista como uma relação de equivalência , o que significa que para todos os conjuntos X , Y e Z :

  • XT X
  • XT Y implica YT X
  • Se XT Y e YT Z então XT Z .

A Turing grau é uma classe de equivalência da relação ≡ T . A notação [ X ] designa a classe de equivalência contendo um conjunto X . Toda a coleção de graus de Turing é indicada .

Os graus de Turing tem uma ordem parcial ≤ definido de modo a que [ X ] ≤ [ Y ] se e somente se XT Y . Existe um grau de Turing único contendo todos os conjuntos computáveis, e esse grau é menor do que qualquer outro grau. É denotado como 0 (zero) porque é o menor elemento do poset . (É comum usar a notação em negrito para graus de Turing, a fim de distingui-los dos conjuntos. Quando nenhuma confusão pode ocorrer, como com [ X ], o negrito não é necessário.)

Para quaisquer conjuntos X e Y , X junta Y, escrito XY , é definido como a união dos conjuntos {2 n  : nX } e {2 m +1: mY }. O grau de Turing XY é o menos limite superior dos graus de X e Y . Portanto, é uma junção semilática . O limite superior de menos graus a e b é denotado umb . Sabe-se que não é uma rede , pois existem pares de graus sem maior limite inferior.

Para qualquer conjunto X, a notação X ′ denota o conjunto de índices de máquinas oráculos que param (quando dados seu índice como entrada) ao usar X como um oráculo. O conjunto X 'é chamado de salto Turing de X . O salto de Turing de um grau [ X ] é definido como o grau [ X ′]; esta é uma definição válida porque X '≡ T Y ' sempre que XT Y . Um exemplo chave é 0 ′, o grau do problema da parada .

Propriedades básicas dos graus de Turing

  • Cada grau de Turing é contavelmente infinito , ou seja, contém exatamente conjuntos.
  • Existem diferentes graus de Turing.
  • Para cada grau a, a desigualdade estrita a < a ′ se mantém.
  • Para cada grau a , o conjunto de graus abaixo de a é contável . O conjunto de graus maior que a tem tamanho .

Estrutura dos graus de Turing

Uma grande quantidade de pesquisas foi conduzida sobre a estrutura dos graus de Turing. A pesquisa a seguir lista apenas alguns dos muitos resultados conhecidos. Uma conclusão geral que pode ser tirada da pesquisa é que a estrutura dos graus de Turing é extremamente complicada.

Propriedades do pedido

  • Existem graus mínimos . Um grau a é mínimo se a for diferente de zero e não houver grau entre 0 e a . Portanto, a relação de ordem nos graus não é uma ordem densa .
  • Para cada grau diferente de zero a, existe um grau b incomparável com a .
  • Existe um conjunto de graus de Turing incomparáveis ​​em pares.
  • Existem pares de graus sem o maior limite inferior. Portanto, não é uma rede.
  • Cada conjunto contável parcialmente ordenado pode ser incorporado nos graus de Turing.
  • Nenhuma sequência infinita de graus estritamente crescente tem um limite superior mínimo.

Propriedades envolvendo o salto

  • Para cada grau a existe um grau estritamente entre a e a ′ . Na verdade, existe uma família contável de graus incomparáveis ​​aos pares entre a e a ′ .
  • Inversão de salto: um grau a tem a forma b ′ se e somente se 0 ′a .
  • Para qualquer grau a existe um grau b tal que a < b e b ′ = a ′ ; tal grau b é chamado de baixo em relação a a .
  • Existe uma sequência infinita a i de graus tal que ai +1a i para cada i .

Propriedades lógicas

  • Simpson (1977) mostrou que a teoria de primeira ordem de na linguagem ⟨≤, =⟩ ou ⟨≤, ′, =⟩ é muitos-um equivalente à teoria da verdadeira aritmética de segunda ordem . Isso indica que a estrutura do é extremamente complicada.
  • Shore e Slaman (1999) mostraram que o operador de salto é definível na estrutura de primeira ordem de com a linguagem ⟨≤, =⟩ .

Graus de Turing recursivamente enumeráveis

Uma rede finita que não pode ser incorporada nos graus.

Um grau é denominado recursivamente enumerável (re) se contiver um conjunto recursivamente enumerável . Todo grau de re está abaixo de 0 ′ , mas nem todo grau abaixo de 0 ′ é re.

  • ( GE Sacks , 1964) Os re graus são densos; entre quaisquer dois graus, há um terceiro grau.
  • (AH Lachlan, 1966a e CEM Yates, 1966) Existem dois graus de recados sem maior limite inferior nos graus de recados.
  • (AH Lachlan, 1966a e CEM Yates, 1966) Há um par de graus diferentes de zero cujo maior limite inferior é 0 .
  • (AH Lachlan, 1966b) Não há nenhum par de graus cujo maior limite inferior seja 0 e cujo menor limite superior seja 0 ′ . Esse resultado é informalmente chamado de teorema do não-diamante .
  • (SK Thomason, 1971) Cada rede distributiva finita pode ser embutida nos re graus. Na verdade, a álgebra booleana atômica contável pode ser incorporada de uma maneira que preserva suprema e infima .
  • (AH Lachlan e RI Soare , 1980) Nem todas as redes finitas podem ser embutidas nos re graus (por meio de uma incorporação que preserva suprema e infima). Um exemplo particular é mostrado à direita.
  • ( LA Harrington e TA Slaman , ver Nies, Shore, e Slaman (1998)) A teoria de primeira ordem dos graus estiver no idioma ⟨ 0 , ≤, =⟩ é muitas-se um equivalente da teoria da verdadeira primeira ordem aritmética .

Problema de postagem e o método de prioridade

Emil Post estudou os graus de re Turing e perguntou se há algum grau de re estritamente entre 0 e 0 ′ . O problema de construir tal grau (ou mostrar que não existe) ficou conhecido como problema de Post . Esse problema foi resolvido independentemente por Friedberg e Muchnik na década de 1950, que mostraram que esses graus intermediários existem. Cada uma de suas provas desenvolveu o mesmo novo método para a construção de graus, que veio a ser conhecido como o método de prioridade . O método de prioridade agora é a principal técnica para estabelecer resultados sobre reconfigurações.

A ideia do método de prioridade para construir um re-conjunto X é listar uma sequência contável de requisitos que X deve satisfazer. Por exemplo, para construir um re-conjunto X entre 0 e 0 ′ é suficiente satisfazer os requisitos A e e B e para cada número natural e , onde A e requer que a máquina oráculo com índice e não calcule 0 ′ de X e B e requer que a máquina de Turing com índice de e (e não oracle) não computa X . Esses requisitos são colocados em uma ordem de prioridade , que é uma bijeção explícita dos requisitos e dos números naturais. A prova prossegue indutivamente com um estágio para cada número natural; esses estágios podem ser considerados como etapas de tempo durante as quais o conjunto X é enumerado. Em cada estágio, os números podem ser colocados em X ou impedidos para sempre de entrar em X em uma tentativa de satisfazer os requisitos (ou seja, forçá-los a permanecer assim que todo X tiver sido enumerado). Às vezes, um número pode ser enumerado em X para satisfazer um requisito, mas isso faria com que um requisito previamente satisfeito se tornasse insatisfeito (ou seja, seria lesado ). A ordem de prioridade nos requisitos é usada para determinar qual requisito satisfazer neste caso. A ideia informal é que, se um requisito for lesado, ele eventualmente deixará de sê-lo depois que todos os requisitos de maior prioridade pararem de ser lesados, embora nem todo argumento de prioridade tenha essa propriedade. Um argumento deve ser feito que o conjunto geral X é re e satisfaz todos os requisitos. Argumentos de prioridade podem ser usados ​​para provar muitos fatos sobre reconfigurações; os requisitos usados ​​e a maneira como são satisfeitos devem ser cuidadosamente escolhidos para produzir o resultado desejado.

Veja também

Referências

Monografias (nível de graduação)
  • Cooper, SB Computability theory . Chapman & Hall / CRC, Boca Raton, FL, 2004. ISBN  1-58488-237-9
  • Cutland, N. Computability. Cambridge University Press, Cambridge-New York, 1980. ISBN  0-521-22384-9 ; ISBN  0-521-29465-7
Monografias e artigos de pesquisa (nível de graduação)
  • Ambos-Spies, K. e Fejer, P. Degrees of Unsolvability. Não publicado. http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf
  • Lerman, M. Degrees of insolvability. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1983. ISBN  3-540-12155-2
  • Odifreddi, PG (1989), Classical Recursion Theory , Studies in Logic and the Foundations of Mathematics, 125 , Amsterdam: North-Holland, ISBN 978-0-444-87295-1, MR  0982269
  • Odifreddi, PG (1999), Teoria da recursão clássica. Vol. II , Studies in Logic and the Foundations of Mathematics, 143 , Amsterdam: North-Holland, ISBN 978-0-444-50205-6, MR  1718169
  • Rogers, H. Theory of Recursive Functions and Effective Computability , MIT Press. ISBN  0-262-68052-1 , ISBN  0-07-053522-1
  • Sacks, Gerald E. Degrees of Unsolvability (Annals of Mathematics Studies), Princeton University Press. ISBN  978-0-6910-7941-7
  • Simpson, S. Degrees of insolvability: a survey of results. Handbook of Mathematical Logic , North-Holland, 1977, pp. 631-652.
  • Shoenfield, Joseph R. Degrees of Unsolvability , North-Holland / Elsevier, ISBN  978-0-7204-2061-6 .
  • Shore, R. (1993). "As teorias dos graus T, tt e wtt re: indecidibilidade e além". Na Univ. Nac. del Sur, Bahía Blanca (ed.). Anais do IX Simpósio Latino-americano de Lógica Matemática, Parte 1 (Bahía Blanca, 1992) . Notas Lógica Mat. 38 . pp. 61–70.
  • Soare, R. Conjuntos e graus recursivamente enumeráveis. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. ISBN  3-540-15299-7
  • Soare, Robert I. Conjuntos e graus recursivamente enumeráveis. Touro. Amer. Matemática. Soc. 84 (1978), no. 6, 1149–1181. MR 508451
Artigos de pesquisa