How to prove that a given set is recursively enumerable?

Question

I was given a set $$ A = \{x \mid W_x \, \text{contains at least one prime number}\} $$ where $W_x = \{y\mid \phi_x(y) \downarrow \}$ is the Dom of the function $\phi_x$

$\downarrow$ means that the function converges or halts.

Any hints on what to prove first? I am not even sure how to tackle this kind of problem as it doesn't look like anything we have solved during the lessons so far.

Answer 1

I'll give the answer in Turing machines.
First, build a Turing machine R(x, y, z) with 3 inputs that does the following

1. Check if x is a syntactically valid encoding of a Turing machine.
2. Check if y encodes a number and the number is prime.
3. Check if z is a valid encoding describing a run of the TM x on input y that stops and accepts.
   If all steps succeed, R stops and accepts. Else rejects.
   R is a deterministic TM that halts on all inputs - therefore computable.
   A is the set $\{x:\exists y \exists z R(x,y,z)\}$ so is computably enumerable.
   Now translate to recursive functions.