Salto de Turing

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Text document with red question mark.svg
Este artigo ou secção contém fontes no fim do texto, mas que não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. (desde julho de 2012)
Por favor, melhore este artigo introduzindo notas de rodapé citando as fontes, inserindo-as no corpo do texto quando necessário.

Em teoria da computabilidade, o Salto de Turing ou Operador de Salto de Turing, nomeado por Alan Turing, é um operador que designa para cada problema de decisão X um sucessivo problema de decisão mais difícil X que tem a propriedade X é não-decidível por uma Máquina Oráculo com um oráculo para X.

O operador é chamado de operador de salto porque ele aumenta o Grau de Turing do problema X. Ou seja, o problema X é redutível por uma máquina de Turing (Redução de Turing) para X. O Teorema de Post estabelece um relacionamento entre o operador de Salto de Turing e a hierarquia aritmética de conjuntos pertencentes ao conjunto dos números naturais. Informalmente, dado um problema, o Salto de Turing retorna o conjunto de máquinas de Turing que param quando se é dado um acesso a um oráculo que resolve este problema.

Definição[editar | editar código-fonte]

Dado um conjunto X e um Número de Gödel φiX das funções X-computáveis, o Salto de Turing X de X é definido como:

X'= \{x \mid \varphi_x^X(x) \ \mbox{é definido} \}.

O n-ésimo Salto de Turing X(n) é definido indutivamente por

X^{(0)} = X, \,
X^{(n+1)}=(X^{(n)})'. \,

O ω Salto X(ω) do X é a união das sequências de conjuntos X(n) para nN:

X^{(\omega)} = \{p_i^k \mid k \in X^{(i)}\},\,

onde pi denota o i-ésimo primo.

A notação 0′ ou ∅′ é, de vez em quando, utilizado para o Salto de Turing de um conjunto vazio. Lê-se salto-zero ou, às vezes, primo-zero.

De forma similar, 0(n) é o n-ésimo salto do conjunto vazio. Para um n finito, esses conjuntos são relacionados à hierarquia aritmética.

O salto pode ser iterado por números Transfinitos: os conjuntos 0(α) para α < ω1CK, onde ω1CK é o Ordinal de Church-Kleen, são muito relacionados à hierarquia hiperaritmética. Por trás de ω1CK, o processo pode ser contínuo através dos ordinais contáveis do Universo construível, utilizando métodos da teoria dos conjuntos(Hodes 1980). O Conceito também foi generalizado para ser estendido aos cardinais regulares incontáveis(Lubarsky 1987).

Exemplos[editar | editar código-fonte]

  • O Salto de Turing 0′ do conjunto vazio é Turing equivalente ao Problema da parada.
  • Para cada n, o conjunto 0(n) é redutível por mapeamento (redução por mapeamento) no nível \Sigma^0_n da hierarquia aritmética
  • O conjunto dos números de Gödel das fórmulas com valor verdade na linguagem da Aritmética de Peano que possuem um predicado para X é computável através de X(ω).

Propriedades[editar | editar código-fonte]

Muitas das propriedades do operador de Salto de Turing são discutidos no artigo Grau de Turing.

Referências[editar | editar código-fonte]

  • Ambos-Spies, K. and Fejer, P. Degrees of Unsolvability. Unpublished. http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf
  • Hodes, Harold T. (1980). "Jumping Through the Transfinite: The Master Code Hierarchy of Turing Degrees". Journal of Symbolic Logic Association for Symbolic Logic [S.l.] 45 (2): 204–220. doi:10.2307/2273183. JSTOR 2273183. 
  • Lerman, M. (1983). Degrees of unsolvability: local and global theory Berlin; New York: Springer-Verlag [S.l.] ISBN 3-540-12155-2. 
  • Lubarsky, Robert S. (1987). "Uncountable Master Codes and the Jump Hierarchy". Journal of Symbolic Logic. pp. 952–958. JSTOR 2273829.  Falta a |url= (Ajuda)
  • Rogers Jr, H. (1987). Theory of recursive functions and effective computability MIT Press Cambridge, MA, USA [S.l.] ISBN 0-07-053522-1. 
  • Shore, R.A.; Slaman, T.A. (1999). "Defining the Turing jump" (PDF). Mathematical Research Letters [S.l.: s.n.] 6 (5–6): 711–722. Consult. 2008-07-13. 
  • Soare, R.I. (1987). Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets Springer [S.l.] ISBN 3-540-15299-7.