[HN Gopher] BB(6) Is Hard (Antihydra) (2024)
       ___________________________________________________________________
        
       BB(6) Is Hard (Antihydra) (2024)
        
       Author : Fibra
       Score  : 32 points
       Date   : 2025-07-13 17:30 UTC (4 days ago)
        
 (HTM) web link (www.sligocki.com)
 (TXT) w3m dump (www.sligocki.com)
        
       | gliptic wrote:
       | Recent developments on BB(6) previously posted here:
       | https://scottaaronson.blog/?p=8972
        
         | cubefox wrote:
         | 272 points by bdr 18 days ago | 223 comments
         | 
         | https://news.ycombinator.com/item?id=44406171
        
       | _alternator_ wrote:
       | 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 wrote:
         | 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.
        
           | tromp wrote:
           | only the truth of finitely refutable conjectures...
        
         | david_for_you wrote:
         | 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_ wrote:
           | 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.
        
       ___________________________________________________________________
       (page generated 2025-07-17 23:02 UTC)