1

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.

Bernard
  • 175,478
Dknot
  • 515
  • Do you mean computably enumerable? –  May 29 '21 at 10:18
  • @O.Peters yes I made a mistake in the usage of the terms (not studying in English, which makes translating somewhat tricky). I meant recursively enumerable – Dknot May 29 '21 at 10:23

1 Answers1

0

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.
  • Am I correct to assume, that we can say that $x \in A \Leftrightarrow \exists y \exists z ( \text{y is prime} \wedge \phi_{f(y)}(x) \downarrow , \text{is reachable in z steps})$? Or did I misunderstand how am I supposed to translate? – Dknot May 29 '21 at 12:28
  • I don't know what the $f$ in your notation is. You need something called Kleene's T predicate to define R in recursive function theory. You also need a function fo check primality which can be done which basic building blocks of primitive recursion. That's why I prefer Turing machines which are a more tractable model of conputation. –  May 29 '21 at 14:01
  • z is not the number of steps in a computation of x on input y. It's a description of a run of a computation of x on input y. That' what Kleene's T is for. –  May 29 '21 at 14:07