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

Question

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.

Answer 1

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.