I think Scott's reasoning is correct in the end. If you suppose you had a computable function f(N) such that f(N) is always greater than BB(N). Then you could exploit the function f to solve the halting problem. Given a program of length N, run the program for f(N) steps. If it halts within that time, you know it's a halting program. If it doesn't halt within that time you know it will never halt.
But does "a computable function that grows faster than BB(N)" actually mean that f(N) is always greater than BB(N), or could it be taken to simply mean that f(N) > BB(N) for a proportion of N that trends towards 1? In other words, could you have a function that almost always upper bounds BB(N), except for a tiny (but still technically infinite) proportion of exceptions? Such a function would be larger than BB in a meaningful sense, but if the sequence of exceptions is not computable, it wouldn't be possible to solve the halting problem with it. There may be a problem with this concept, but it doesn't appear obvious to me.
Yes, this I understand. I agree that it is impossible to “prove” that a computable function f(N) is always greater than BB(N).
My concern is that the argument leaves open the possibility of a larger computable function, even if it would be impossible to demonstrate that it is in fact larger for all N.
I’m sure that this possibility is somehow foreclosed (that is, I’m not trying to say that the claim is wrong, just that I think there is a case that isn’t covered by the argument). But I don’t quite see it.
No, it has been proven that there exists no turing machine that can solve the halting problem. If we assume that there exists a computable f(N) that is always greater than BB(N) then we can construct a Turing machine that solves the halting problem. Therefore no computable f(N) can exist.
I think the issue is related to notion of a "direct" proof vs "proof by contradiction". What I gave was a proof by contradiction. Once you start thinking about the philosophy of proofs it, it's an interesting question to ask whether or not proofs by contradiction should really count. I don't know much about this but you can search up the term "Law of the excluded middle" is a good place to start reading about these concepts.
Trust me, I understand proof by contradiction :). The point I was missing was the difference between an undecidable question vs impossible. See the rest of the thread above.
