# Use Rice's theorem to show that the language of optimisable Turing machines is undecidable

I have an assignment to do and I'm quite stuck with the following question :

Use Rice's theorem to show that

$$\qquad L' = \{ \langle M \rangle \mid \; (\exists \text{ TM } M') \; [ L(M') = L(M) \text{ and } M' \text{ has less than 29 states} ] \}$$

is undecidable.

I have absolutely no idea how to proceed.

Would someone be kind enough to, at least, give me some clues?

EDIT

First, I wrote the question wrong. It is now '$$M'$$ has less than 29 states' (not 'steps')."

Here's what I'm thinking after more reading and consulting other students at school.

Rice's theorem :

$$L = \{ \langle M \rangle \mid L(M) \text{ has some property } P \}$$ where :

1. $$P$$ is non-trivial, i.e. there exists at least one machine $$M_1$$ such that $$\langle M_1 \rangle \in L$$, and at least one machine $$M_2$$ such that $$\langle M_2 \rangle \not \in L$$.

2. $$P$$ is indeed a property of the language of TMs, i.e. whenever $$L(M_a) = L(M_b)$$, we have $$\langle M_a \rangle \in L$$ if and only if $$\langle M_b \rangle \in L$$.

Then, $$L$$ is undecidable.

So here, the property is "$$M'$$ has less than 29 states".

We can show that this property is non-trivial.

Let's take the language "abcdefghijklmnopqrstuvwxyz0123456789" (only one string is accepted). We can build a TM $$M$$ this way :

-> Enter in state $$q_0$$

-> In $$q_0$$ : if you read "a", proceed to $$q_a$$, otherwise go to $$q_{reject}$$ and halt.

-> In $$q_a$$ : if you read "b", proceed to $$q_{ab}$$, otherwise go to $$q_{reject}$$ and halt.

$$\vdots$$

-> In $$q_{abcdefghijklmnopqrstuvwxyz012345678}$$ : if you read "9" go to $$q_{accept}$$, otherwise go to $$q_{reject}$$ and halt.

So here we got 3 "basic states" : $$q_0$$, $$q_{reject}$$ and $$q_{accept}$$ and we have $$|abcdefghijklmnopqrstuvwxyz0123456789| - 1$$ states (there is no $$q_{abcdefghijklmnopqrstuvwxyz0123456789}$$ because when we read "9" at the end, we go to $$q_{accept}$$). So that's 26 + 10 - 1 = 35 states. We have a total of 35 + 3 = 38 states.

Unless I am wrong, there can't be a TM $$M'$$ that can test wether a string $$w$$ belongs to that language without having at least 38 states !

So the property "$$M'$$ has less than 29 steps" is non-trivial as there is at least one TM that respects it, and at least one that does not.

Now, $$P$$ is indeed a property of the language of TMs, because any two machines $$M_1$$ and $$M_2$$ such that $$L(M_1) = L(M_2)$$ implies :

$$\langle M_1 \rangle \in L' \Leftrightarrow L(M_1) = L(M_2) \Leftrightarrow \langle M_2 \rangle \in L'$$.

(I know there is at least one missing clause in there, but I can't figure how to write it, it's got something to do with that "$$M'$$ has less than 29 steps")

So, according to Rice's theorem, $$L'$$ is undecidable.

• Do you understand the theorem? Can you rephrase it so we may check your understanding? Do you get what is explained here?
– Raphael
Jul 29, 2013 at 8:26
• Hints: Rice's theorem shows undecidability for certain "properties" of Turing Machines. Can you show that being optimizable is this type of property? Jul 29, 2013 at 16:42
• Do you understand what $L'$ is? Ps., what is meant by a turing machine having $n$ steps? Jul 30, 2013 at 8:15
• Edited question with a potential answer. Jul 30, 2013 at 16:28
There is some TM which is not in $L'$, and there is some TM which is in $L'$. So the definition of $L'$ determines a nontrivial property on r.e. languages and so by Rice's theorem it is not decidable.