Como entender a definição de $ \ pick $ in hierarquia aritmética

Question

Estou lendo um texto sobre a teoria da computação, e de acordo com o texto, em cada nível $ K $ da hierarquia aritmética, temos dois conjuntos, $ \ sigma_k $ e $ \ pi_k $ , onde $ \ pi_k $ é definido como:

$$ \ Pi_k= co- sigma_k $$

para que para $ k= 0 $ , temos a classe de conjuntos decidíveis e $ \ sigma_0=pi_0 $ , e para $ k= 1 $ , temos $ \ sigma_1 $ como classe de conjuntos cálculos (CE) e $ \ pi_1 $ como a classe de conjuntos não conumíveis (não CE) ....

Deixe $ l (m_e) $ denotam o idioma reconhecido pela máquina Turing $ m_e $ com Godel número $ e $ . Eu me deparei com a seguinte língua $ e $ , onde:

$$ e= {E | l (m_e)=sigma ^ *} $$

i.e. $ e $ é a linguagem de todos os códigos de máquina de Turing $ e $ que são computableamente enumeráveis. Por um argumento de diagonalização, ele pode ser mostrado que $ e $ não é c.e. Isso implica que:

$$ E \ in \ pi_1 $$

No entanto, se $ e \ in \ pi_1 $ significa que $ E= CO-A $ , para algumas $ a \ in \ sigma_1 $ , usando a definição na declaração acima ... no entanto, o complemento do recipiente de matemática $ E $ é:

$$ \ overline {e}=overline {\ {\ {E | l (m_e)=sigma ^ *}} $$

Quais (eu acho) significa que $ \ overline {e} $ é a linguagem de todas as máquinas de Turing $ E $ tal que em algumas entradas, $ e $ divergenta ... No entanto, foi mostrado que $ \ overline {e} \ equiv_m k ^ {2} $ , ou seja $ \ overline {e} \ equiv_m k ^ k $ , de modo que, onde Dado dois conjuntos $ a $ e $ B $ , temos $ A \ equiv_m b $ iff $ a \ leq_m b $ e $ b \ leq_m a $ < / span>, e $ \ leq_m $ refere-se a uma redução de muitos para um:

$$ \ overline {e} \ equiv_m k ^ k \ in \ sigma_2 $$

Dado que $ \ sigma_2 \ neq \ sigma_1 $ , parece que $ \ overline {e} $ < / span> não é computableamente enumerável ... mas isso não contradiz a definição de $ \ pi_1 $ que afirma que o complemento de um não CE conjunto é c.e. ?

Eu acho que estou perdendo algo na minha compreensão das definições ...

Answer 1

para $ K $ Mesmo, uma linguagem $ l $ está em $ \ pi_k $ Se existe um predicado recursivo $ R $ tal que $$ x \ in l \ longleftrightarrow \ forall y_1 \ existe y_2 \ cdots \ forall y_ {k-1} \ existe y_k \, r (x, y_1, \ ldots, y_k) $$ Os quantificadores alternam entre $ \ forall $ e $ \ existe $ .

Quando $ k $ é ímpar, a mesma definição funciona, mas o último quantificador é $ \ forall $ : $$ x \ in l \ longleftrightarrow \ forall y_1 \ existe y_2 \ cdots \ existe y_ {k-1} \ forall y_k \, r (x, y_1, \ ldots, y_k) $$

Por exemplo, a linguagem de todas as máquinas Turing é $ \ pi_2 $ desde $$ x \ in \ mathsf {tot} \ longleftrightarrow \ forall y \ existe z \, \ text {"máquina $ x $ halts na entrada $ y $ no $ z $ z $ sta etapas"} $$

a classe $ \ sigma_k $ é definido da mesma maneira, com o primeiro quantificador sendo $ \ existe $ < / span> em vez de $ \ forall $ .

Se você complementar um idioma na $ \ sigma_k $ Você obtém um em $ \ pi_k $ , e vice versa. Isto é devido às leis de de Morgan para quantificadores, e o fato de que a negação de um predicado recursivo também é recursiva.

Por exemplo, a linguagem de não -Máquinas de Turing -Total é $ \ sigma_2 $ desde $$ x \ in \ mathsf {ntot} \ longleftrightarrow x \ notin \ mathsf {tot} \ longleftrightarrow \ existe y \ forall z \, \ text {"máquina $ x $ não interrompe a entrada $ y $ Z $ Z $ } $$