0
$\begingroup$

I need to show why this set is not recursively enumerable: $\{i \mid W_i=\emptyset\}$.

Here $W_i$ is the set of things that can be accepted by the Turing machine $M_i$.

I know that for a set to recursively enumerable, it must be accepted by a Turing machine so that the Turing machine can enumerate over all the elements in that set. Here, I do not understand why a Turing machine wouldn't be able to enumerate over the elements of this set.

Can someone provide an explanation of why this set is not recursively enumerable or hint at a method that can be used to show this?

$\endgroup$
2
  • $\begingroup$ If a Turing machine hasn't halted and hasn't accepted something, how do you know it won't accept something in the future? You should look for a way to formalize the statement that if you could solve this you can solve the halting problem. $\endgroup$
    – Ross Millikan
    Feb 9, 2017 at 22:35
  • $\begingroup$ On those same lines, do you have any thoughts on how $\{i \mid W_i= \mathbb{Z}\}$ can be shown to not be recursively enumerable? $\endgroup$
    – jshapy8
    Feb 9, 2017 at 23:04

1 Answer 1

Reset to default
1
$\begingroup$

The way to show some language is not in $RE$ (recursively enumerable) is to show a reduction from a known language which is not in $RE$ such as $\overline{HP}$.

the reduction may be as follows: $$f(\left < M \right >, x) = i_{M_x} $$

where $i_{M_x}$ is the index of the machine $M_x$ described bellow:

$M_x$ on input $w$:

  1. run M on x
  2. accept

I'll leave the correctness proof to you.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .