# Can a Turing Machine have fewer states?

I am currently learning about Turing Machines, I am curious if a Turing Machine can have fewer states ? Can it be done like a Transition Graph where you can have multiple states at once ?

I got this TM off of a youtube video sorry for bad hand writing, but could I just merge some of the states like you would do in Transition Graph, so instead of having 5 states it would have 4 states ? TM are more advanced so I don't know if you are even able to do this...thanks!

how could I make this into 4 states TM instead of 5 states ? in TG if would take 5 seconds do it...

• Have fewer states than what? If two states are identical, they can be merged; if they're not, they can't. There's always going to be a point where no more states can be merged: if that wasn't the case, every Turing machine would have only one state, and there aren't many different one-state machines! – David Richerby Apr 3 '14 at 21:38
• Maybe two related results: (1) there is a universal TM with 2 states and $|\Gamma|=3$. (2) It is undecidable to test if the size of the code of a TM is minimal – A.Schulz Apr 4 '14 at 8:57

## 2 Answers

It is undecidable to check whether a turing maching has a smaller encoding than a given one. Hence there cannot be any such concept as a transition graph.

If you simply want a smaller turing maching for your example, I would guess no, from a quick glance of it.

The language of your Turing Machine is : $\{ a^nb^n | n > 0 \}$. What about this?

I think language of this Turing Machine is : $\{ a^nb^n | n > 0 \}$ but with the condition of $A,B \notin \Sigma$.

• And why do you think so? – Raphael Apr 7 '14 at 10:52