Suggest edit — Rice's Theorem

Title

Name

Note

---
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.