Estoy trabajando en el siguiente problema: que $W_e$ sea el conjunto computablemente enumerable que es el dominio del $e$ -año del programa de Turing, y $K$ sea el problema de Halting, ¿en qué nivel de la jerarquía aritmética aparece cada uno de los siguientes conjuntos?
- $A_1=\{e: W_e$ no contiene números pares $\}$
- $A_2=\{e: W_e$ contiene algún elemento de $K\;\}$
- $A_3=\{e: W_e$ contiene todos los elementos de $K\;\}$
- $A_4=\{e: W_e$ es infinito $\}$
Creo que $A_1 \in \Pi_1$ porque se puede escribir como $A_1=\{\exists x \in W_e (\forall n \neg (x=2n) )\}$ es decir, un cuantificador universal y otro acotado. Me preocupa un poco que el conjunto acotado sea c.e., ¿cambia las cosas?
Desde $K \in \Sigma_1$ y $A_2=\{e: \exists x \in W_e (x \in K)\}$ , $A_2$ está en $\Sigma_1$ pero no es $\Pi_1$ por lo que no es $\Delta_1$ .
$A_3=\{e: \forall x \in K (x \in W_e)\}$ por lo que es $\Pi_1$
No estoy seguro de qué hacer con $A_4$
También me gustaría ver estos conjuntos en el contexto de la máquina de Turing, pero no puedo entenderlo.
