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 w.l.o.g. that the empty function undefined on every input is not in $S$ noteSuppose 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 $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 sz

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.

Patrick Stevens 30 Jul 2016 19:16 UTC
I think the halting problem probably should have its own page, rather than being linked to the umbrella uncomputability page.
Patrick Stevens 14 Aug 2016 16:41 UTC
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.
- Jaime Sevilla Molina 14 Aug 2016 19:31 UTC
  The problem I have in mind is deciding whether the Halting problem is equivalent to any statement of the form “You cannot decide membership for $S$”, where $S$ is a non-trivial set of computable functions.
  
  Clearly the argument exposed above shows that the Halting problem implies any of these statements, but does the reverse implication hold directly? In my proof of how Rice implies Halting I am handpicking an $S$. Can we make do without the handpicking?
  
  In other words, given a Halting oracle, can we make a Rice oracle for an arbitrary $S$?
- Patrick Stevens 14 Aug 2016 20:05 UTC
  I think the answer is no. Indeed, there are uncountably many $S$, but only countably many machines which can access oracles.

Rice's theorem and the Halting problem

The Halting theorem implies Rice’s theorem

Rice’s Theorem implies the Halting theorem