# Rice's theorem and the Halting problem

We will show that Rice’s the­o­rem and the the halt­ing prob­lem are equiv­a­lent.

# The Halt­ing the­o­rem im­plies Rice’s theorem

Let $$S$$ be a non triv­ial set of com­putable par­tial func­tions, and sup­pose that there ex­ists a Tur­ing ma­chine en­coded 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 as­sume w.l.o.g. that the empty func­tion un­defined on ev­ery in­put is not in $$S$$ noteSup­pose that the empty func­tion is in $$S$$. Then it is satis­fied that the empty func­tion is not in $$S^c$$, and if $$S$$ is de­cid­able then it fol­lows im­me­di­ately that $$S^c$$ is de­cid­able as well. So we can use $$S^c$$ as our $$S$$ and the ar­gu­ment fol­lows ex­actly the same.. Thus there ex­ists a com­putable func­tion in $$S$$ com­puted by some ma­chine $$[s]$$ such that $$[s](x)$$ is defined for some in­put $$x$$.

Sup­pose we want to de­cide whether the ma­chine $$[m]$$ halts on in­put $$[x]$$.

For that pur­pose we can build a ma­chine $$Proxy_s$$ which does the fol­low­ing:

Proxy_s(z):
call [m](x)
re­turn sz


Clearly, if $$[m](x)$$ halts then Proxy_z com­putes the same func­tion as $$[s]$$, and thus $$[n](Proxy_s)=1$$.

If on the other hand $$[m](x)$$ does not halt, then Proxy_s(z) com­putes the empty func­tion, which we as­sumed to not be in $$S$$, and there­fore $$[n](Proxy_s)=0$$.

Thus we can use a Tur­ing ma­chine com­put­ing per­ti­nence to $$S$$ to de­cide the halt­ing prob­lem, which we know is un­de­cid­able. We con­clude that such a ma­chine can­not pos­si­bly ex­ists, and thus Rice’s the­o­rem holds.

# Rice’s The­o­rem im­plies the Halt­ing theorem

Sup­pose that there was a Tur­ing ma­chine $$HALT$$ de­cid­ing the Halt­ing Prob­lem.

Let $$S$$ be the set of com­putable func­tions defined on a fixed in­put $$x$$, which is clearly non-triv­ial, as it does not con­tain the empty func­tion but is not empty ei­ther. Let $$[n]$$ be a Tur­ing ma­chine, and we want to de­cide whether $$[n]\in S$$ or not. If this was pos­si­ble for an ar­bi­trary $$[n]$$, then we would have reached a con­tra­dic­tion, as Rice’s the­o­rem for­bids this out­come.

But $$[n]$$ be­longs to $$S$$ iff $$[n]$$ halts on in­put $$x$$, so we can use $$HALT$$ to de­cide whether $$[n]$$ be­longs to $$S$$, in con­tra­dic­tion with Rice’s the­o­rem. So our sup­po­si­tion of the ex­is­tence of $$HALT$$ was er­ro­neous, and thus the Halt­ing the­o­rem is true.

Parents:

• Rice's Theorem

Rice’s The­o­rem tells us that if we want to de­ter­mine pretty much any­thing about the be­havi­our of an ar­bi­trary com­puter pro­gram, we can’t in gen­eral do bet­ter than just run­ning it.

• Turing machine

A Tur­ing Ma­chine is a sim­ple math­e­mat­i­cal model of com­pu­ta­tion that is pow­er­ful enough to de­scribe any com­pu­ta­tion a com­puter can do.

• I think the halt­ing prob­lem prob­a­bly should have its own page, rather than be­ing linked to the um­brella un­com­putabil­ity page.

• Surely they are equiv­a­lent. Given a Rice-de­cid­ing or­a­cle, we can ask the or­a­cle, “Does the par­tial func­tion defined by ma­chine $$[n]$$ spec­ify where in­put $$k$$ should go?”; that de­ter­mines whether $$[n]$$ halts on in­put $$k$$ or not.

• The prob­lem I have in mind is de­cid­ing whether the Halt­ing prob­lem is equiv­a­lent to any state­ment of the form “You can­not de­cide mem­ber­ship for $$S$$”, where $$S$$ is a non-triv­ial set of com­putable func­tions.

Clearly the ar­gu­ment ex­posed above shows that the Halt­ing prob­lem im­plies any of these state­ments, but does the re­verse im­pli­ca­tion hold di­rectly? In my proof of how Rice im­plies Halt­ing I am hand­pick­ing an $$S$$. Can we make do with­out the hand­pick­ing?

In other words, given a Halt­ing or­a­cle, can we make a Rice or­a­cle for an ar­bi­trary $$S$$?

• I think the an­swer is no. In­deed, there are un­countably many $$S$$, but only countably many ma­chines which can ac­cess or­a­cles.