# Rice's theorem and the Halting problem

https://arbital.com/p/rice_and_halt

by Jaime Sevilla Molina Jul 29 2016 updated Aug 14 2016

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.

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.