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


2 Answers 2


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.

  • $\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$
    – Ramesh
    Commented Jan 28, 2018 at 10:56
  • 1
    $\begingroup$ @RajeshR Check the definitions. $\endgroup$
    – Raphael
    Commented Jan 28, 2018 at 11:04
  • 8
    $\begingroup$ @RajeshR $L(M)$ is the language recognised by the TM $M$. So, again by definition, it's recognisable. $\endgroup$ Commented Jan 28, 2018 at 11:30

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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