Hacker News Reader

Comment by feoren | Hacker News Reader

> What if there is a beaver that never halts or loops

A Turing machine with finite states must eventually either halt or loop. Those are the only options, because there are only finitely many configurations it can be in, and each configuration completely determines the next.

A "beaver" is defined to not loop. All "beavers" must halt, because otherwise they're just not considered for BB(n). All the challenge is in proving whether a given Turing machine does (or does not) halt, and therefore must not (or must) loop. Proving "halt" or "loop" proves the other one.

Yes, the function `busy_beaver_6() = 576125642131574254..." must exist.

View on HN

I disagree unless you state what you mean by "loop". If it's just "repeat a state" then any 6-state TM "loops" or halts after at most 6 turns... and many that "loop" will eventually halt.

There are infinitely many configurations if you consider the tape.

It is still true, of course, that every Turing machine either halts on a given input, or doesn't.

I don't understand what you're disagreeing with. "loop" has a well-understood meaning here: return to an identical state. Not a similar one, identical. Because if it does that once, being a deterministic automaton, it will do so an infinite number of times without halting.

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.

> 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.

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.

You're right: my argument is flawed. I had thought TFA relied on that argument, but the machine that writes 1 and moves right forever is a counterexample.

Yet something about that still seems extremely "loopy". Is there something that must stop increasing after a while? Kolmogorov complexity? Or is that begging the question, since that's basically measuring the smallest TM that can produce that output?

You’re right that it “feels loopy”, intuitively. I also don’t know how to formalize this notion.

How about this: given any arbitrarily large window size W, we can find an infinite number of timestamps (it may even be enough to say we can find two) in which the tape within the range of Head-W and Head+W is identical. So if you say 10, I can give you an infinite list of step-counts at which the 21 symbols on the tape centered at the head is identical to all the other times in that list. Assuming we can do that for any arbitrary window size, then the TM is in a "looping" state. Of course, a halted TM also has this property. So perhaps this is true of all Turing Machines?

> A Turing machine with finite states must eventually either halt or loop. Those are the only options, because there are only finitely many configurations it can be in, and each configuration completely determines the next.

The Turing machine writes and reads from an infinite tape, and as such, the number of configurations (the machine's state + tape) is countably infinite.

Reply on news.ycombinator.com