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.
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.
I 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.)
If you had both Omega and the halting probability Omega_1 of a Universal Oracle Turing Machine with Omega as oracle, then it seems you could decide Sigma_2/Pi_2 conjectures. You can alternate bits from both Omegas to make it one number.
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.
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.
I 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.)
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...
Could any number give you the truth of non-finitely refutable conjectures?
If you had both Omega and the halting probability Omega_1 of a Universal Oracle Turing Machine with Omega as oracle, then it seems you could decide Sigma_2/Pi_2 conjectures. You can alternate bits from both Omegas to make it one number.
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