Rice's Theorem — Jemoka Knowledge Base

For some predicate P:

\begin{equation} P: \left\{TM\right\} \to \left\{0,1\right\} \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 = \left\{M \mid P(M) = 1\right\} 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’t decidable. If the latter, than not ATM reduces to your language and your language isn’t recognizable. Proof Rice’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—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’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’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’s not always easy to tell if stuff is decidable. Key example:

\begin{equation} \left\{(M,w) \mid M\text{ is a turing machine that on $w$ tries to move its head past the left of the input}\right\} \end{equation}

(i.e. where you pump against the wall)

\begin{equation} \left\{(M,w) \mid M\text{ is a turing machine that on $w$ tries to move its head left, at least once}\right\} \end{equation}

problem 1 is undecidable, and the second one is decidable! problem 1 we can reduce A_{TM} to L’ 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. IfMtries to move to the cell with but haven’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’. If L is decidable, then A_{TM} should be too. But it isn’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.