Rice's Theorem

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’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} \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’$

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