We will show that Rice's theorem and the the halting problem are equivalent.
The Halting theorem implies Rice's theorem
Let $~$S$~$ be a non trivial set of computable partial functions, and suppose that there exists a Turing machine encoded by $~$[n]$~$ such that: $$~$ [n](m) = \left\{ \begin{array}{ll} 1 & [m] \text{ computes a function in $S$} \\ 0 & \text{otherwise} \\ \end{array} \right. $~$$
We can assume [without_loss_of_generality w.l.o.g.] that the empty function undefined on every input is not in $~$S$~$ %%note:Suppose that the empty function is in $~$S$~$. Then it is satisfied that the empty function is not in $~$S^c$~$, and if $~$S$~$ is decidable then it follows immediately that [thecomplementofadecidablesetis_decidable $~$S^c$~$ is decidable as well]. So we can use $~$S^c$~$ as our $~$S$~$ and the argument follows exactly the same.%%. Thus there exists a computable function in $~$S$~$ computed by some machine $~$[s]$~$ such that $~$[s](x)$~$ is defined for some input $~$x$~$.
Suppose we want to decide whether the machine $~$[m]$~$ halts on input $~$[x]$~$.
For that purpose we can build a machine $~$Proxy_s$~$ which does the following:
Proxy_s(z):
call [m](x)
return s[z]
Clearly, if $~$[m](x)$~$ halts then Proxy_z computes the same function as $~$[s]$~$, and thus $~$[n](Proxy_s)=1$~$.
If on the other hand $~$[m](x)$~$ does not halt, then Proxy_s(z) computes the empty function, which we assumed to not be in $~$S$~$, and therefore $~$[n](Proxy_s)=0$~$.
Thus we can use a Turing machine computing pertinence to $~$S$~$ 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.
Rice's Theorem implies the Halting theorem
Suppose that there was a Turing machine $~$HALT$~$ deciding the Halting Problem.
Let $~$S$~$ be the set of computable functions defined on a fixed input $~$x$~$, which is clearly non-trivial, as it does not contain the empty function but is not empty either. Let $~$[n]$~$ be a Turing machine, and we want to decide whether $~$[n]\in S$~$ or not. If this was possible for an arbitrary $~$[n]$~$, then we would have reached a contradiction, as Rice's theorem forbids this outcome.
But $~$[n]$~$ belongs to $~$S$~$ iff $~$[n]$~$ halts on input $~$x$~$, so we can use $~$HALT$~$ to decide whether $~$[n]$~$ belongs to $~$S$~$, in contradiction with Rice's theorem. So our supposition of the existence of $~$HALT$~$ was erroneous, and thus the Halting theorem is true.
Comments
Patrick Stevens
I think the halting problem probably should have its own page, rather than being linked to the umbrella uncomputability page.
Patrick Stevens
Surely they are equivalent. Given a Rice-deciding oracle, we can ask the oracle, "Does the partial function defined by machine $~$[n]$~$ specify where input $~$k$~$ should go?"; that determines whether $~$[n]$~$ halts on input $~$k$~$ or not.