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 [the*complement*of*a*decidable*set*is_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.