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