Rice's theorem and the Halting problem

Written by Jaime Sevilla Molina last updated

We will show that Rice's theorem and the the halting problem are equivalent.

The Halting theorem implies Rice's theorem

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.

Rice's Theorem implies the Halting theorem

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.

  1. ^︎

    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.