I was reading about the busy beaver problem the other day and I'm confused as to why we can't keep an array of Turing machine states that the machine has been through and simply iterate through it at each new machine state to see if it exactly matches a state we've previously seen. That ought to tell us there's an infinite loop, no? Then following this, shouldn't we be able to solve the problem for any given Turing machine, instruction set and tape?

  • $\begingroup$ its easier for some to understand when realizing that "solving" the busy beaver problem would allow solving the halting problem $\endgroup$ – vzn Sep 5 '14 at 22:48
  • $\begingroup$ For a lot of algorithms it's easy enough, but some will be utterly pathological on every level. Like not knowing if there chaotic, or provably unprovable, or they're testing the coldatz conjecture. "{1}, {2, 1}, {3, 10, 5, 16, 8, 4, 2, 1}, {4, 2, 1}" now what? Either "{…, 425…682, 331…520, …} - False" or "{5, 16, 8, 4, 2, 1}, {6, 3, 10, 5, 16, 8, 4, 2, 1}, …" - True. $\endgroup$ – alan2here Nov 23 '18 at 19:07

The state of a TM includes its tape contents. Since the tape is infinite, the number of different tape contents we may encounter is infinite as well. So a TM is not required to repeat a state in order to never halt.

As a very simple example, consider the TM that will in each step write a character on the tape and move to the right. -- It will never halt but also never repeat a state.

| cite | improve this answer | |
  • $\begingroup$ Ah I'd somehow forgotten the tape was infinite. Makes sense. $\endgroup$ – Fab Castel Sep 5 '14 at 21:16

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.