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 uma ou mais fontes no fim do texto, mas nenhuma é citada 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]

Você deve especificar url = ao usar a
Predefinição:Citar web. Parâmetros disponíveis:

{{citar web
|url =             |ano =
|titulo =          |mes =
|acessodata =      |formato =
|acessodiames =    |obra =
|acessomesdia =    |publicado =
|acessoano =       |paginas =
|autor =           |lingua =
|ultimo =          |doi =
|primeiro =        |arquivourl =
|autorlink =       |arquivodata =
|coautores =       |citacao =
|data =
}}

.

  • Rogers Jr, H.. Theory of recursive functions and effective computability. [S.l.]: MIT Press Cambridge, MA, USA, 1987. ISBN 0-07-053522-1.
  • Shore, R.A.; Slaman, T.A.. (1999). "Defining the Turing jump". Mathematical Research Letters 6 (5–6): 711–722.
  • Soare, R.I.. Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets. [S.l.]: Springer, 1987. ISBN 3-540-15299-7.