1
$\begingroup$

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!

enter image description here

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

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ 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! $\endgroup$ – David Richerby Apr 3 '14 at 21:38
  • 4
    $\begingroup$ 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 $\endgroup$ – A.Schulz Apr 4 '14 at 8:57
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
0
$\begingroup$

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

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ And why do you think so? $\endgroup$ – Raphael♦ Apr 7 '14 at 10:52

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.