Comment by gpm
8 months ago
Math's a cooperative endeavor, I want to know if I'm wrong!
I'm not sure I understand the distinction you're trying to make though, and I'm not sure it's right...
The argument that BB has to grow faster than any computable sequence is that if we have a computable f(n) where for all n f(n) > BB(n) then we can solve the halting problem by simulating turing machines of size n for f(n) steps and checking if they halt. Even if we can't prove f(n) > BB(n) the mere existence of this f would mean we could solve the halting problem (even though we couldn't prove we had done so).
I agree my "proof" (intuition really) rests on that assertion.
> As an easy example, consider f(n) = BB(n)^2.
This, like BB(n), isn't computable?
Thanks for the good attitude!
Ah, I didn't realize 'computable' had a specific meaning in this domain -- showing the limits of my experience a bit. After looking at the wikipedia page and rereading your sketch, I think it is true that
> it eventually needs to grow faster than any computable operator we define
I'm not sure if this has implications about how quickly BB() grows compared to the "operator strength" ladder though? It's familiar/convenient to refer to tetration, pentation, etc as f() for convenience, but this is just notational -- not related to computability. When comparing BB(n) and tetration(n), pentation(n), etc(n), I don't think there is really anything that can be said 'easily' about which values are larger. BB(n) will be larger than anything that can be computed in n steps. But pentation(n) is not necessarily computable in n steps, it may take much more. We may find pentation(n) > BB(n) for all n greater than some threshold. I might be misunderstanding a logical step here though that connects them?
> We may find pentation(n) > BB(n) for all n greater than some threshold.
No, that is impossible. Tetration, pentation, etc. are all computable sequences and BB grows faster than any computable sequence. So you have the > sign where you really want a < sign.
>BB(n) will be larger than anything that can be computed in n steps
Who said anything about "n steps"?
BB(n) is about an n-state Turing machine, not "n steps".