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?EDITFirst, 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 :$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$.$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.
Use Rice's theorem to show that the language of optimisable Turing machines is undecidable
computability;undecidability;rice theorem