Come comprendere la definizione di $ \ Scegli $ nella gerarchia aritmetica

Question

sto leggendo un testo sulla teoria della computabilità, e secondo il testo, ad ogni livello $ k $ della gerarchia aritmetica, abbiamo due set, $ \ Sigma_k $ e $ \ pi_k $ , dove $ \ pi_k $ è definito come:

$$ \ Pi_k= co- \ sigma_k $$

Così per $ k= 0 $ , abbiamo la classe di set decidabili e $ \ Sigma_0=pi_0 $ e per $ k= 1 $ , abbiamo $ \ sigma_1 $ come il Classe di set computabilmente enumerabili (CE) e $ \ PI_1 $ Come la classe di set non elaborabilmente enumerabili (non CE) ....

Let $ L (M_E) $ Denna la lingua riconosciuta da Turing Machine $ M_E $ con Godel Numero $ e $ . Ho trovato la seguente lingua $ e $ , dove:

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

I.e. $ E $ è la lingua di tutti i codici macchina di Turing $ e $ che sono calcolabilmente enumerabili. Da un argomento di diagonalizzazione, può essere mostrato che $ e $ non è c.e. Questo implica che:

$$ E \ in \ pi_1 $$

Tuttavia, se $ e \ in \ pi_1 $ , significa che $ e= co-a $ , per alcuni $ a \ in \ sigma_1 $ , usando la definizione nell'istruzione sopra ... Tuttavia, il complemento di $ E $ è:

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

che (immagino) significa che $ \ overline {e} $ è la lingua di tutte le macchine Turing $ e $ tale che su alcuni ingressi, $ e $ diverge ... Tuttavia, è stato dimostrato che $ \ overline {e} \ equiv_m k ^ {2} $ , cioè $ \ overline {e} \ equiv_m k ^ k $ , in modo che Dato due set $ A $ e $ B $ , abbiamo $ A \ equiv_m B $ IFF $ A \ Leq_M B $ e $ B \ leq_m A $ < / span> e $ \ leq_m $ si riferisce a una riduzione di molti-to-one:

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

Dato che $ \ sigma_2 \ neq \ sigma_1 $ , sembra che $ \ overline {e} $ < / span> non è informativamente enumerabile ... ma questo non contraddice la definizione di $ \ pi_1 $ che afferma che il complemento di un ce set è c.e. ?

Penso che mi manchi qualcosa nella mia comprensione delle definizioni ...

Answer 1

per $ k $ Anche, una lingua $ l $ è in $ \ PI_K $ Se esiste un predicato ricorsivo $ r $ tale $$ x \ in l \ longleftrintingerow \ forall y_1 \ esiste y_2 \ cdots \ forall y_ {k-1} \ esiste y_k \, r (x, y_1, \ ldots, y_k) $$ I quantificatori si alternano tra $ \ forlt $ e $ \ esiste $ .

Quando $ k $ è dispari, la stessa definizione funziona, ma l'ultimo quantificatore è $ \ forlt $ : $$ x \ in l \ longleftrintingrow \ forlt y_1 \ esiste y_2 \ cdots \ esiste y_ {k-1} \ forall y_k \, r (x, y_1, \ ldots, y_k) $$

Ad esempio, la lingua di tutte le macchine Total Turing è $ \ PI_2 $ Da allora $$ x \ in \ mathsf {tot} \ longleftrightarrow \ forall y \ esiste z \, \ text {"macchina $ x $ fermata in ingresso $ y $ a $ y entro $ z $ passaggi"} $$

La classe $ \ sigma_k $ è definito nello stesso modo, con il primo quantificatore è $ \ esiste $ < / span> anziché $ \ forlt $ .

Se si completa una lingua in $ \ Sigma_K $ ottieni uno in $ \ pi_k $ , e viceversa. Ciò è dovuto alle leggi di De Morgan per i quantificatori e il fatto che anche la negazione di un predicato ricorsivo sia ricorsiva.

Ad esempio, la lingua di non -Total Turing Machines è $ \ Sigma_2 $ Da allora $$ x \ in \ mathsf {ntot} \ longleftrightarrow x \ notin \ mathsf {tot} \ longleftrightrow \ esiste y \ forlt z \, \ text {"macchina $ x $ non si fermano in ingresso $ y $ entro $ Z $ passi "} $$