2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Do you understand the theorem? Can you rephrase it so we may check your understanding? Do you get what is explained here? $\endgroup$ – Raphael Jul 29 '13 at 8:26
  • $\begingroup$ Hints: Rice's theorem shows undecidability for certain "properties" of Turing Machines. Can you show that being optimizable is this type of property? $\endgroup$ – jmite Jul 29 '13 at 16:42
  • 1
    $\begingroup$ Do you understand what $L'$ is? Ps., what is meant by a turing machine having $n$ steps? $\endgroup$ – Pål GD Jul 30 '13 at 8:15
  • $\begingroup$ Edited question with a potential answer. $\endgroup$ – Über Lem Jul 30 '13 at 16:28
  • $\begingroup$ @ÜberLem Please move your answer (attempt) into an answer for clarity. $\endgroup$ – Raphael Jul 31 '13 at 8:19
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.