3 ms·
An upper bound U for BB(6) implies that any program that runs longer than U never terminates. Thus the specific Collatz-type problems that can be encoded in 6 i
by _alternator_ 1y ago
An upper bound U for BB(6) implies that any program that runs longer than U never terminates. Thus the specific Collatz-type problems that can be encoded in 6 instructions can be run U+1 steps and if they don’t halt, they won’t halt.
The proof that BB(6) is relevant is that you can encode it in a 6 instruction program, which is what the link does.
- david_for_you 1y agoI understand that, what I am saying is, that the upper bound can never be useful because the lower bound is already so high that we cannot run U+1 steps, ever.
- _alternator_ 1y agoI see; thanks for clarifying. I suppose the only thing you’d get “for free” is that the termination of these programs becomes decidable. (Not sure if this is known for these specific programs. At some point, BB number bounds are necessarily unknowable.)