How to show the following problem is undecidable without Rice's theorem?

Question

The problem is '$W_x=\varnothing$'.

If I could reduce '$x\in W_x$' to '$W_x=\varnothing$' by s-m-n theorem and universal function, maybe there would be a solution. I have no idea how to reduce? Can you give me some details?

Answer 1

Well, you've almost got the right reduction in mind, but you're looking at it the wrong way around.

"$x\in W_x$" is a positive phenomenon: if $x\in W_x$, then we see that at some point. Meanwhile, "$W_x=\emptyset$" is a negative phenomenon: if $W_x\not=\emptyset$, we see that at some point (since at some point we see some number enter $W_x$).

It's usually easier to find a reduction between two sets of the same "type" (both positive, or both negative, or etc.); and positive phenomena tend to be easier to understand than negative. So, my suggestion is to try reducing "$x\in W_x$" to $W_x\not=\emptyset$.

As a hint towards this: fixing some $c$, do you see how to find a $d$ such that $c\in W_c$ iff $W_d\not=\emptyset$? HINT: think of $W_d$ as a box, and you put something into it as soon as you see $c\in W_c$ - what's a natural thing to put into the box when this happens?

Now, just show that the passage from $c$ to $d$ is in fact computable, and you'll have shown the desired reduction (in fact you'll have shown an $m$-reduction, and via the padding lemma you can turn this into a 1-reduction).