|
|
|
|
|
by samatman
705 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. |
|
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.