Re:BB(10) > Graham's Number
by SAI_Peregrinus on Tuesday October 13, 2026 @01:54PM
(#50075833)
You can always exhaustively run all Turing machines of a given size, at each step comparing the state & tape to all previous steps. If they ever reach the same state with the same tape as a previous step, they're in an infinite loop and never halt. If not, they eventually reach the halt state. BB(n) is computable. But BB is not computable, because there's no general algorithm requiring finite storage and time which computes the results of BB(n) for all n. You have to brute-force it for every positive integer n, which takes infinite time (and space) and is therefore not computable.
[ Parent
| on HN ]
Re:BB(10) > Graham's Number
by davrosthedalek on Tuesday October 13, 2026 @02:31PM
(#50076381)
There is no requirement to have a recurring state when not halting. Indeed, the most trivial machine "write 1 and move right", will never have the same tape state.
Re:BB(10) > Graham's Number
by Jerrrrrrrrry on Tuesday October 13, 2026 @07:55PM
(#50080611)
Total state, not just tape.
Meaning stack, pointer Location, etc.
Re:BB(10) > Graham's Number
by davrosthedalek on Tuesday October 13, 2026 @10:35PM
(#50081688)
First, TMs don't have a stack. Second, still no recurrent state needed.
Extending a state with additional variables doesn't make a unique state less unique anyway, so "total state" is always more or same unique as "just tape".
Re:BB(10) > Graham's Number
by Jerrrrrrrrry on Wednesday October 14, 2026 @06:33AM
(#50085366)
Some turing machine variants have multiple tapes, effectively registers.
If the tape, instruction position, and all other variables are the same as any previous step, then the deterministic machine is going to continue to find itself in that loop, and never halt.
Think Collatz like functions - if the output starts into a loop, you know the end result.
However, any program trying to detect all loops by maintaining a bloom filter of every previous state doesnt work, that drags any computation down by a scale of its inputs^runtime.
Re:BB(10) > Graham's Number
by davrosthedalek on Thursday October 15, 2026 @07:20AM
(#50102104)
Yes, doesn't change the fact that you do not have to hit such a state to have a non-halting program. I already gave an example: a program that continuously writes to the tape will not stop, and since the tape is always different, will not trigger your loop detection.
Re:BB(10) > Graham's Number
by Jerrrrrrrrry on Saturday October 17, 2026 @12:48PM
(#50132663)
It increments its tape position variable. Its never the same state.
State isnt just tape, its all dependent variables.
Re:BB(10) > Graham's Number
by davrosthedalek on Saturday October 17, 2026 @01:04PM
(#50132856)
Exactly, never the same state. And still doesn't halt. That's the point. You cannot detect all non-halting programs by detecting if they go into the same state again. They can, but don't have to.