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.