patternModerate
Why is "accepted by Turing Machine with even number of states" a trivial property?
Viewed 0 times
whynumberwithstatesacceptedtrivialpropertymachineturingeven
Problem
$$
L = \left\{ \left~\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.
L = \left\{ \left~\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.
Solution
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.
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.
Context
StackExchange Computer Science Q#87426, answer score: 14
Revisions (0)
No revisions yet.