1
$\begingroup$

So I tried to prove that $D =\{x \in \mathbb{N} | \Phi_x(x)\uparrow\}$ is not recursively enumerable in the following way:

  • let's suppose that $g$ is the computable function that represents $D$ $$g(x) = \left\{\begin{array}{rcl} 1 & \mbox{if} & \Phi_x(x)\downarrow\ \\ 0 & \mbox{if} & \Phi_x(x)\uparrow\ \end{array}\right.$$
  • let's suppose that it exists a Turing machine of index $i_0$ such that $g = \Phi_{i_0}$, than it is possible to define the function: $$g'(x) = \left\{\begin{array}{rcl} \uparrow & \mbox{if} & g(x)=1=\Phi_{i_0}(x) \\ 0 & \mbox{if} & g(x)=0=\Phi_{i_0}(x) \end{array}\right.$$
  • so $g'$ is also computable thus there is a Turing machine of index $i_1$ such that $g' = \Phi_{i_1}$, but then we will have that: $$\Phi_{i_1}(i_1)\downarrow \iff g'(i_1) = 0 \iff g(i_1) = 0 \iff \Phi_{i_1}(i_1)\uparrow $$ $$\Phi_{i_1}(i_1)\uparrow \iff g'(i_1) \uparrow \iff g(i_1) = 1 \iff \Phi_{i_1}(i_1)\downarrow $$

which is a contraddiction. So an index $i_1$ doesn't exists that is the index $i_0$ that computes $g$ doesn't exists, that is $g$ is not recursive so $D$ is not recursive enumerable.

I'm quite confused on this topic, so tell me if I made any kind of error.

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ I think there is a slight error in your definition of $D$. Do you mean $D = \{ x \in \mathbb{N} | \Phi_i (x) \uparrow \}$ ? Note that $\Phi_i$ denotes one goedelized Turing Machine with Goedelnumber $i$ $\endgroup$
    – Panzerkroete
    Commented Jul 28, 2018 at 3:06
  • $\begingroup$ Yes you are rigth. Thank you... anything else? I think I also messed up the last definition. I wrote that if $g$ is not recursive than $D$ is not recursive enumerable, but I don't find any theorem that states that. $\endgroup$
    – tokenizer
    Commented Jul 28, 2018 at 8:29
  • 4
    $\begingroup$ You proved that D is not recursive (also known as decidable) because you starting assumption was that there is a computable $g$ which decides membeship of $D$. To prove that $D$ is not recursively enumerable, your starting assumption must be tht there is a computable $h$ whose image is $D$. $\endgroup$
    – Andrej Bauer
    Commented Jul 28, 2018 at 9:02
  • $\begingroup$ I'm doing a mess here, but I came with this: $\psi_d(x) = \left\{\begin{array}{rcl} 1 & \mbox{if} & x \in D \\ \uparrow & \mbox{if} & x \notin D\end{array}\right.$ this means that $D=dom(\psi_d)$. So $x\in A \iff \exists y \text{ such that } \Phi_y(x)\uparrow$. Then $\psi_d(x) = \left\{\begin{array}{rcl} 1 & \mbox{if} &\exists y. \Phi_y(x)\uparrow\\ \uparrow & \mbox{if} & \exists y. \Phi_y(x)\downarrow\end{array}\right.$ but that is a contraddiction. $\endgroup$
    – tokenizer
    Commented Jul 28, 2018 at 9:42
  • 1
    $\begingroup$ Yes but checking if $\Phi_i(0)\uparrow$ it's not computable, isn't it? I understood that there is no way to know if a function terminates or not its computation. I'm really confused on this topic so please have patience with me. $\endgroup$
    – tokenizer
    Commented Jul 28, 2018 at 19:57

1 Answer 1

Reset to default
2
$\begingroup$

As Andrej states, what you've (correctly) done is show that $D=\{x:\Phi_x(x)\uparrow\}$ is not recursive. However, there are plenty of sets which are recursively enumerable but not recursive, so you're not done yet: you need to show that $D$ is not the domain of any partial recursive function.

REMARK: Some texts define a set to be r.e. if it is the range of a total recursive function, or is empty. This is slightly less elegant since it requires a separate clause to handle $\emptyset$; it also generalizes less well if one looks into higher computability theory. However, regardless of what definition your book gives, the equivalence between them should be a very early exercise.

There are a couple ways to do this:

  • You could argue directly: suppose $D$ is the domain of $\Phi_i$. Can you use the recursion theorem to cook up a $j$ such that $\Phi_j(j)\downarrow\iff \Phi_i(j)\downarrow$? Do you see why this gives a contradiction?

  • Alternately, note that $D$ is the complement of the Halting Problem $H=\{x: \Phi_x(x)\downarrow\}$. Two early results in computability theory are that (i) $H$ is r.e. but not recursive and (ii) if a set and its complement are r.e., then they are each recursive. Do you see how to prove each of these facts, and apply them to the current problem? (Note that this approach isn't actually much different than the first one, since the recursion theorem is used in proving (i).)

REMARK: Some texts define the Halting Problem differently, some common alternate candidates being $\{x: \Phi_x(0)\downarrow\}$ and $\{\langle x, y\rangle:\Phi_x(y)\downarrow\}$. It's a good exercise to show that these are all r.e. and Turing equivalent (indeed $1$-equivalent!) to each other.

By similar arguments you can show that minor variations of $D$ are also not r.e. - e.g. can you show that $\{x: \Phi_x(17)\uparrow\}$ is not r.e.?

Responding to the comments: one may be tempted to try to enumerate $D$, or things like $D$, by looking at approximations given by stages. E.g. we could let $D_s=\{x:\Phi_x(x)[s]\uparrow\}$; this is the set of indices of machines which on their own input don't halt in fewer than $s$ steps. The $D_s$s are r.e. - indeed, uniformly recursive - and approximate $D$ "from above" in the sense that $D=\bigcap_{s\in\mathbb{N}} D_s$. However, this ultimately isn't relevant to this problem since the intersection of infinitely many r.e. sets need not be r.e.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.