BB(6) Is Hard (Antihydra) (2024)

https://www.sligocki.com//2024/07/06/bb-6-2-is-hard.html

by Fibra • 1 year ago

34 11 1 year ago

sligocki.com

gliptic• 1 year ago

Recent developments on BB(6) previously posted here: https://scottaaronson.blog/?p=8972

cubefox• 1 year ago

272 points by bdr 18 days ago | 223 comments

https://news.ycombinator.com/item?id=44406171

_alternator_3• 1 year ago

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

thrance• 1 year ago

A number, that if known, would allow us to derive the truth value of any statements from it.

tromp2• 1 year ago

only the truth of finitely refutable conjectures...

david_for_you2• 1 year ago

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_3• 1 year 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.

BB(6) Is Hard (Antihydra) (2024)

Related Stories