Hacker News new | ask | show | jobs
by umanwizard 704 days ago
In determining whether you've returned to an identical state, are you including the tape? Or just the machine states?

If you are including the tape, it's not true that there are finitely many states. If you're not, then "looping" as you've defined it is not excluded from the definition of the busy beaver problem, and does not imply that the machine never halts.
1 comments
samatman 704 days ago
> If you are including the tape, it's not true that there are finitely many states.

An infinite Turing tape can be in an identical state, however. The number of states don't have to be finite. If a Turing machine returns to an identical state, it will not halt. That's what we call looping.

An example of an identical state is 1 at indexes 3 and 5 of the tape, and 0 everywhere else.

Another example is the Brainfuck program `++[]`. This trivially returns repeatedly to a given finite state.

link
umanwizard 704 days ago
Yes, but the original claim was that non-halting TMs must loop because the number of configurations is finite. But that's not true.

Here's an example of a bf program that never returns to an identical configuration, and also never halts. The corresponding TM would be excluded from consideration for the busy beaver number, despite never "looping" according to your definition.

    +[+]
A similar-in-spirit TM (with tape alphabet {0, 1}, and only one machine state) is the one that unconditionally sets the current symbol to 1 and then moves to the right. This never encounters the same configuration twice (the number of 1s on the tape increases each turn) and also never halts.
link