We will show that Rice's theorem and the the halting problem are equivalent.
Let be a non trivial set of computable partial functions, and suppose that there exists a Turing machine encoded by such that:
We can assume w.l.o.g. that the empty function undefined on every input is not in [1]. Thus there exists a computable function in computed by some machine such that is defined for some input .
Suppose we want to decide whether the machine halts on input .
For that purpose we can build a machine which does the following:
Proxy_s(z):
call [m](x)
return s[z]
Clearly, if halts then Proxy_z computes the same function as , and thus .
If on the other hand does not halt, then Proxy_s(z) computes the empty function, which we assumed to not be in , and therefore .
Thus we can use a Turing machine computing pertinence to to decide the halting problem, which we know is undecidable. We conclude that such a machine cannot possibly exists, and thus Rice's theorem holds.
Suppose that there was a Turing machine deciding the Halting Problem.
Let be the set of computable functions defined on a fixed input , which is clearly non-trivial, as it does not contain the empty function but is not empty either. Let be a Turing machine, and we want to decide whether or not. If this was possible for an arbitrary , then we would have reached a contradiction, as Rice's theorem forbids this outcome.
But belongs to iff halts on input , so we can use to decide whether belongs to , in contradiction with Rice's theorem. So our supposition of the existence of was erroneous, and thus the Halting theorem is true.
Suppose that the empty function is in . Then it is satisfied that the empty function is not in , and if is decidable then it follows immediately that is decidable as well. So we can use as our and the argument follows exactly the same.