Is there a difference between the end state of a Turing machine and the halt state? Especially, for example the Busy Beaver 3. It is said that it is with 3 states but there is also a halt. Is the end state $q_2$ or the $halt$?

  • 1
    $\begingroup$ Busy Beaver is a famous Turing machine problem, which aims of determining the maximum number of steps, done by a TM, when computing the number of 1s starting from an empty tape. For one 1 (one state) - one step, for four 1s (2 states) - six steps, for six 1s (3 states) - fourteen steps. So it grows exponentially. Therefore, it is proved that it`s not computable. The problem however, dates back from 1960s. $\endgroup$ – user8 Jan 28 '15 at 20:13
  • 3
    $\begingroup$ The growth is not exponential, it is super-exponential. Also, exponential growth (and even super-exponential growth) doesn't imply non-computable. However it happens to be the case that the busy beaver function growths faster than every computable function. $\endgroup$ – kasperd Feb 22 '15 at 22:04

"End(ing) state" and "halt(ing) state" are just two (four) different ways of saying the same thing.


In the specific case of the Busy Beaver , the end state is the halt state, al other states (q0,q1,q2) must have a transition defined for every symbol in the alphabet of the TM so the machine doesn't halt on them.

  • $\begingroup$ Also, considering the definition of the busy beaver problem, the halting state is not considered a "regular" state, probably because it is not optional. I believe you are making the common mistake of thinking that the state with the higher index ($q_2$, in your example) has some special attribute, but it doesn't. $\endgroup$ – André Souza Lemos Apr 24 '15 at 4:05

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.