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).
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.
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.
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).
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.
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.
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.
only the truth of finitely refutable conjectures...
Recent developments on BB(6) previously posted here: https://scottaaronson.blog/?p=8972
272 points by bdr 18 days ago | 223 comments
https://news.ycombinator.com/item?id=44406171