¿Cómo demostrar que un conjunto dado es recursivamente enumerable?

Question

Me dieron un juego $$ A = \{x \mid W_x \, \text{contains at least one prime number}\} $$ donde $W_x = \{y\mid \phi_x(y) \downarrow \}$ es el Dom de la función $\phi_x$

$\downarrow$ significa que la función converge o se detiene.

¿Alguna pista sobre qué probar primero? Ni siquiera estoy seguro de cómo abordar este tipo de problema, ya que no se parece a nada que hayamos resuelto durante las lecciones hasta ahora.

Answer 1

Daré la respuesta en máquinas de Turing.
Primero, construye una máquina de Turing R(x, y, z) con 3 entradas que haga lo siguiente

1. Comprobar si x es una codificación sintácticamente válida de una máquina de Turing.
2. Comprueba si y codifica un número y éste es primo.
3. Comprueba si z es una codificación válida que describe una ejecución de la TM x en la entrada y que se detiene y acepta.
   Si todos los pasos tienen éxito, R se detiene y acepta. Si no, rechaza.
   R es una TM determinista que se detiene en todas las entradas - por lo tanto computable.
   A es el conjunto $\{x:\exists y \exists z R(x,y,z)\}$ por lo que es computablemente enumerable.
   Ahora traduce a funciones recursivas.