Teorema de Post

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.
Por favor, melhore este artigo introduzindo notas de rodapé citando as fontes, inserindo-as no corpo do texto quando necessário.
Ambox rewrite.svg
Esta página precisa ser reciclada de acordo com o livro de estilo (desde abril de 2013).
Sinta-se livre para editá-la para que esta possa atingir um nível de qualidade superior.

Na teoria da computação, o Teorema de Post,em homenagem à Emil Post, descreve a conexão entre hierarquia aritmética e os graus de Turing.

Background[editar | editar código-fonte]

A demonstração do teorema de Post usa vários conceitos relativos à definibilidade e teoria da recursão. Esta seção apresenta uma visão geral desses conceitos, que são abordados em profundidade em seus respectivos artigos.

A hierarquia aritmética classifica os conjuntos de números naturais que são definíveis na linguagem da aritmética de Peano. Uma fórmula é dita ser \Sigma^{0}_m se é uma afirmação existencial na forma normal prenex (todos os quantificadores na frente) com m alternâncias entre quantificadores existenciais e universais aplicadas a uma fórmula livre de quantificador Formalmente uma fórmula\phi(s) na linguagem da aritmética de Peano é uma\Sigma^{0}_m fórmula se ele é da forma

\exists n_1 \forall n_2 \exists n_3 \forall n_4 \cdots Q n_m \rho(n_1,\ldots,n_m,x_1,\ldots,x_k),

onde ρ é uma fórmula livre quantificador e Q é \forall se m é par e \exists se m é impar. Note-se que qualquer fórmula na forma

\left(\exists n^1_1\exists n^1_2\cdots\exists n^1_{j_1}\right)\left(\forall n^2_1 \cdots \forall n^2_{j_2}\right)\left(\exists n^3_1\cdots\right)\cdots\left(Q_1 n^m_1 \cdots \right)\rho(n^1_1,\ldots n^m_{j_m},x_1,\ldots,x_k)

Onde \rho contém apenas quantificadores delimitados é comprovadamente equivalente a uma fórmula da forma acima dos axiomas da Aritmética de Peano. Assim, não é incomum ver \Sigma^{0}_m fórmulas definidas nesta forma alternativa e não equivalentes tecnicamente, já que na prática a distinção raramente é importante.

Um conjunto de números naturais A é dito ser \Sigma^0_m se é definida por uma \Sigma^0_m fórmula, isto é, se houver uma \Sigma^0_m fórmula \phi(s) tal que cada número n está em A, se e somente se \phi(n) detem. Sabe-se que, se um conjunto é \Sigma^0_m então ele é \Sigma^0_n para cada n > m, mas para cada m existe um \Sigma^0_{m+1} conjunto que não é \Sigma^0_m. Assim, o número de quantificadores alternados necessários para definir um conjunto dá uma medida da complexidade do conjunto.

O teorema de Post usa a hierarquia aritmética relativizada, bem como a hierarquia não relativizada apenas definida. Um conjunto A' de números naturais é dito ser\Sigma^0_m relativo à um conjunto B, escrito\Sigma^{0,B}_m, se A é definível por uma\Sigma^0_m fórmula em uma linguagem estendida que inclui um predicado para a adesão em B.

Enquanto a hierarquia aritmética mede definibilidade de conjuntos de números naturais, graus de Turing medem o nível de não computabilidade do conjunto dos números naturais. Um conjunto A é dito ser Turing redutível à um conjunto B, escrito A \leq_T B, se existe uma máquina de Turing oráculo tal que, dado um oráculo para B, compute as funções características de A. O salto de Turing de um conjunto A é uma forma do problema da parada relativo à A. Dado um conjunto A, O salto de Turing A' é o conjunto de indices da máquina de turing orraculo que para na entrada 0 quando computando com o oráculo A. Sabemos que todo conjunto A é Turing redutível para o seu salto de Turing, mas o salto de Turing de um conjunto nunca é Turing redutivel ao seu conjunto original.

O teorema de Post usa infinitos saltos iterados de Turing . Para qualquer conjunto A nos números naturais a notação A^{(n)} indica a "n"-vezes reiterou o salto de Turing de A AssimA^{(0)} é apenas A, e A^{(n+1)} é o salto de Turing deA^{(n)}.

Teorema de Post e corolários[editar | editar código-fonte]

O teorema de Post's estabelece uma conexão proxima entre a hierarquia aritmética e os graus de turing da forma\emptyset^{(n)}, que é, finitos saltos iterados de Turing do conjunto vazio. (O conjunto vazio pode ser substituido por qualquer outro conjunto computavel sem que haja mudança na definição do teorema).

Estados do teorema de Post :

  1. Um conjunto B é \Sigma^0_{n+1} se e somente se B é recursivamente enumeravel por uma máquina de Turing oráculo, com um oraculo para \emptyset^{(n)}, ou seja, se e somente se B é \Sigma^{0,\emptyset^{(n)}}_1.
  2. O conjunto \emptyset^{(n)} é \Sigma^0_n completo para cada n > 0. Isso significa que cada \Sigma^0_n conjunto é redutivel em muitos para um para \emptyset^{(n)}.

O teorema de Post's possue muitos corolários que mostram relaçoes adicionais entre hierarquia aritmetica e os graus de Turing. Os quais incluem:

  1. Ajustar um conjunto C. Um conjunto B é \Sigma^{0,C}_{n+1} se e somente se B é \Sigma^{0,C^{(n)}}_1. Esta é a relativização da primeira parte do teorema de Post para o oráculo C.
  2. Um conjunto B é \Delta_{n+1} se e somente se B \leq_T \emptyset^{(n)}. Mais genericamente, B é \Delta^C_{n+1} se e somente se B \leq_T C^{(n)}.
  3. Um conjunto é dito ser aritmético se ele é \Sigma^0_n para algum n. O teorema de Post mostra que , equivalentemente, um conjunto é aritmético se e somente se ele é Turing redutivel à \emptyset^{(m)} para algum m.

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

Rogers, H. The Theory of Recursive Functions and Effective Computability, MIT Press. ISBN 0-262-68052-1; ISBN 0-07-053522-1

Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. ISBN 3-540-15299-7