# Why is this set not recursively enumerable?

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?

• 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. Feb 9, 2017 at 22:35
• 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? Feb 9, 2017 at 23:04

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$: