BB(6) Is Hard (Antihydra) (2024)
11 comments
·July 13, 2025_alternator_
david_for_you
Hm, I'm not sure I would say that knowing an upper bound would be any help in solving these open problems, unless the way to prove that upper bound would involve a collatz type problem. We already know from the lower bound of BB(6) that we cannot iterate that far in this universe.
_alternator_
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
I 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.
thrance
See also: https://en.wikipedia.org/wiki/Chaitin%27s_constant
A number, that if known, would allow us to derive the truth value of any statements from it.
gliptic
Recent developments on BB(6) previously posted here: https://scottaaronson.blog/?p=8972
cubefox
272 points by bdr 18 days ago | 223 comments
Cool link, despite being a bit later than some of the other stuff on BB(6). Basically, it shows a 6-state Turing machine can encode a Collatz-type iteration:
``` a,b=8,0 while b!=-1: b+=2-a%2*3 a+=a>>1 ```
Showing that these halt or not are long-standing open problems, so knowing upper bounds BB(6) would immediately solve them (modulo a lot of compute time).