---
title: "Rice's Theorem"
type: concept
source: https://www.jemoka.com/posts/kbhrice_s_theorem/
confidence: high
status: active
---

For some predicate \(P\):
\begin{equation} P: \qty {TM} \to \qty {0,1} \end{equation}
think of \(0\) (false), \(1\) (true), where \(P\) satisfies:
non trivial: there are Turing Machines \(M_{yes}\), \(M_{no}\) such that \(P(M_{yes}) = 1\), and \(P(M_{no}) = 0\) semantic: for all Turing Machines \(M_1\) and \(M_2\), if \(L(M_1) = L(M_2)\) then \(P(M_1) = P(M_2)\) then, the language \(L = \qty {M \mid P(M) = 1}\) is undecidable.
to do this, check if \(P(M_{\emptyset}) = 0\) or \(P(M_{\emptyset}) = 1\); if the former, then ATM reduces to your language and your language isn&rsquo;t decidable. If the latter, than not ATM reduces to your language and your language isn&rsquo;t recognizable.
Proof Rice&rsquo;s Undecidable Basic idea: reduce \(A_{TM}\) or \(\not A_{TM}\) to \(L\).
Let us define \(M_{\varnothing}\) such that \(L(M_{\emptyset}) = \emptyset\)
case 1: \(P(M_{\emptyset}) = 0\), since \(P\) is non-trivial, there is an \(P(M_{yes}) = 1\) reduction from \(A_{TM}\) to \(L\) (i.e. \(L\) is not decidable) for \((M,w)\), we produce \(M_{w}(x)\) for which both \(M\) accepts \(w\) AND \(M_{yes}\) accepts $x$&mdash;meaning, \(L(M_{w}) = L(M_{yes})\) when \(M\) accepts \(w\); meaning \(P(M_{yes}) = 1\), we have \(P(M_{w}) = 1\) (because \(P\) is semantic); and so \(M_{W} \in L\) if \(M\) doesn&rsquo;t accept \(w\), then \(L(M_{w}) = L(M_{\emptyset}) = \emptyset\), and similarly, \(P(M_{\emptyset} = 0)\), so we have \(M_{W} \not \in L\) case 2: \(P(M_{\emptyset}) = 1\), since \(P\) is non-trivial, there is an \(P(M_{no}) = 0\) reduction from \(\neg A_{TM}\) to \(L\) (i.e. \(L\) is not even recognizable) for \((M,w)\), we produce \(M_{w}(x)\) for which both \(M\) accepts \(w\) AND \(M_{no}\) accepts \(x\); if \(M\) doesn&rsquo;t accept \(w\), we have \(L(M_{w}) = L(M_{\emptyset}) = \emptyset\), since \(P(M_{\emptyset}) = 1\), then \(M_{w} \in L\); otherwise, if \(M\) accepts \(w\) then \(L(M_{w}) = L(M_{no})\), similarly, since \(P(M_{NO}) = 0\), we have \(P(M_{w}) = 0\), so \(M_{w}\) is not in \(L\) Examples of Predicates that are Semantic M accepts 0 for all w, M(w) accepts IFF M(wr) accepts L(M) = {0} L(M) is empty L(M) = sigma^* M accepts 154 strings these are all therefore all undecidable!
Some Motivation It&rsquo;s not always easy to tell if stuff is decidable.
Key example:
\begin{equation} \qty {(M,w) \mid M\text{ is a turing machine that on $w$ tries to move its head past the left of the input}} \end{equation}
(i.e. where you pump against the wall)
\begin{equation} \qty {(M,w) \mid M\text{ is a turing machine that on $w$ tries to move its head left, at least once}} \end{equation}
problem 1 is undecidable, and the second one is decidable!
problem 1 we can reduce \(A_{TM}\) to \(L&rsquo;\)
In particular, let us take input \((M,w)\), we will make a truing machine that \(N\) that shifts \(w\) over by one cell, and marks a special symbol $ on the now-empty leftmost cell. If \(M\) tries to move to the cell with $ but haven&rsquo;t yet accepted, we move its head back one step to the right; if \(M\) accepts, we then roll our way all the way to the left.
Hence, \(A_{TM}\) reduces to \(L&rsquo;\). If \(L\) is decidable, then \(A_{TM}\) should be too. But it isn&rsquo;t.
problem 2 on input \((M,w)\), run \(M\) on \(w\) for \(|Q|+|w|+1\) for \(|Q|\) number of states of \(M\).
accept if \(M\) ever move to the left reject otherwise acceptance is clear; we can reject after \(|Q|+|w|+1\), after moving to the right \(|w|+1\) steps, we will get to an empty cell; we will then move over \(|Q|\) more times. After this, by pigeonhole we will land in another state which we have seen before. We are hence in a similar situation as before, which means we will keep moving forwards the right.
