The following is an excerpt from the book "Introduction to the theory of Computation" by Michael Sipser, 2nd edition. enter image description here

As per the book, this Turing machine accepts the language L = { w#w | w ∈{0, 1}*}. I ran this machine for few strings and it's working properly.

My doubt is, I think there is no need of keeping a transition on the state q6 for 0 and 1.

I mean, if the transition on state q6 was x -> L in place of 0,1,x->L then also this machine will work properly. Please confirm the same.

  • 2
    $\begingroup$ You can confirm it on your own by programming your suggested Turing machine and running it on some inputs. $\endgroup$ – Yuval Filmus Sep 6 '17 at 19:14
  • $\begingroup$ I don't know how to program a Turing machine, I know only the theory part.. $\endgroup$ – Manu Thakur Sep 6 '17 at 19:26
  • 1
    $\begingroup$ If you know how a Turing machine works and you know how to program, then you should be able to program a Turing machine. $\endgroup$ – Yuval Filmus Sep 6 '17 at 19:28
  • 2
    $\begingroup$ You say you "ran [Sipser's] machine for a few strings" so why can't you do the same with your version? $\endgroup$ – David Richerby Sep 6 '17 at 19:31
  • $\begingroup$ I did it, then i only reached to this conclusion that this Turing Machine will also work without transition for 0 and 1 on state q6. as this machine is given in a standard book, i only want someone to confirm what i am thinking is correct or i am missing something. $\endgroup$ – Manu Thakur Sep 6 '17 at 19:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.