Notes - Models of Computation MT23, Rice's theorem
Flashcards
State Rice’s theorem, first informally and then define in detail.
Every non-trivial property $P$ of $\text{RE}$ languages is undecidable.
- $P$: A language consisting of encodings of Turing machines that satisfy the property
- Property of $\text{RE}$ languages: For all TMs $M _ 1$ and $M _ 2$ where $L(M _ 1) = L(M _ 2)$, $\langle M _ 1 \rangle \in P \iff \langle M _ 2 \rangle \in P$, i.e. membership depends only on the language, not the encoding
- Non-trivial: There exists TMs $M _ 1$ and $M _ 2$ where $\langle M _ 1 \rangle \in P$ and $\langle M _ 1 \rangle \notin P$
What reduction is used in the proof of Rice’s theorem?
We reduce the decision problem for any non-trivial property to the Halting problem.
Why would “$M$ halts all inputs” not be an appropriate property to use Rice’s theorem on?
There could be two Turing machines that represent the same language, but one loops rather than rejecting.
Quickly prove Rice’s theorem, i.e. that every non-trivial property $P$ of $\text{RE}$ languages is undecideable, where this means:
- $P$: A language consisting of encodings of Turing machines that satisfy the property
- Property of $\text{RE}$ languages: For all TMs $M _ 1$ and $M _ 2$ where $L(M _ 1) = L(M _ 2)$, $\langle M _ 1 \rangle \in P \iff \langle M _ 2 \rangle \in P$, i.e. membership depends only on the language, not the encoding
- Non-trivial: There exists TMs $M _ 1$ and $M _ 2$ where $\langle M _ 1 \rangle \in P$ and $\langle M _ 1 \rangle \notin P$
Wlog, we can assume that if for some Turing machine $M$, $L(M) = \emptyset$, then $\langle M\rangle \notin P$. (Why? If this weren’t the case, we can instead consider $P^{\mathsf C}$. If $P^\mathsf{C}$ is undecideable, then $P$ is, since we can just output the opposite, and $P^\mathsf{C}$ does not contain Turing machines that recognise the empty language since if $L(M _ 1) = L(M _ 2)$, then $\langle M _ 1 \rangle \in P \iff \langle M _ 2\rangle \in P$).
Suppose we had a decider $D$ for the language $P$ and we wanted to decide if $\langle M, x\rangle$ were in $\text{HALT}$. Define $\langle N _ {M, x} \rangle$ as follows:
N_{M, x} (y): # y is the input
Simulate M, x
If M halts on x:
Run K on y # K is any Turing machine in P
If K accepts:
Accept
(Letting $K$ be any Turing machine with the property is where we use the non-triviality assumption).
Then we have the following
- $M$ halts on $x$ $\implies$ $L(N _ {M, x}) = L(K)$ $\implies$ $\langle N _ {M, x}\rangle \in P$
- $M$ does not halt on $x$ $\implies$ $L(N _ {M, x}) = \emptyset$ $\implies$ $\langle N _ {M, x} \rangle \notin P$
So
\[M \text{ halts on }x \iff \langle N_{M, x}\rangle \in P\]since we can decide whether $\langle N _ {M, x}\rangle \in P$, we can solve the halting problem. This is a contradiction, and we are done.
How could you apply Rice’s theorem to deduce that
\[L = \\{\langle M_1, M_2 \rangle \mid L(M_1) \cap L(M_2) \ne \emptyset\\}\]
is undecideable?
Rice’s theorem only applies to languages consisting of encodings of Turing machines, but this language is over pairs of Turing machines. Note that
\[L' = \\{\langle M \rangle \mid L(M) \ne \emptyset\\}\]reduces to $L$ via the reduction where $M _ 1$ is set to $M$ and $M _ 2$ is set a Turing machine that accepts every string.
From Rice’s theorem, it then follows that $L’$ is undecideable, so $L$ must also be undecideable.