3
$\begingroup$

$$ L = \left\{ \left< M \right>~\middle|~ \small{ \begin{array}{l} L(M)\text{ is recognized by a Turing Machine} \\ \text{having even number of states} \end{array} } \right\}. $$

Isn't $L$ same as asking if $L\left(M\right)$ is recursively enumerable (RE)? How is it trivial?

I know what it means for a property to be trivial, but I don't understand how the above property is trivial and decidable.

$\endgroup$
13
$\begingroup$

All recognisable languages are recognised by a TM with an even number of states, so the property is trivial.

If a language is recognisable, there is (by definition) a TM that recognises it. If it happens to have an even number of states, then you're done. If it has an odd number of states, add another state that doesn't do anything (or duplicates an existing state), then you have a new TM with an even number of states, and are done.

$\endgroup$
  • $\begingroup$ Why is L(M) always R.E ? Can't it be Non R.E ? If it's always r.e I understand that it's trivial as there will always be a T.M accepting that language but in case L(M) is non R.E, how is it trivial? $\endgroup$ – Rajesh R Jan 28 '18 at 10:56
  • 1
    $\begingroup$ @RajeshR Check the definitions. $\endgroup$ – Raphael Jan 28 '18 at 11:04
  • 8
    $\begingroup$ @RajeshR $L(M)$ is the language recognised by the TM $M$. So, again by definition, it's recognisable. $\endgroup$ – Luke Mathieson Jan 28 '18 at 11:30
7
$\begingroup$

In the context of Rice's theorem, a class of languages is trivial if either

  • it contains all RE languages;
  • it contains no RE languages.

In your case, the language is trivial for the first reason, as Luke explains.

$\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.