Why is this set not recursively enumerable?

Question

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?

Answer 1

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.