3 ms·
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
by breuleux 1y ago
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.
- KalMann 1y ago> "a computable function that grows faster than BB(N)" In the context that Scott Aaronson was using it probably yes as that is necessary for the most straightforward /obvious proof to work.
- breuleux 1y agoI am curious if there is a proof for the less obvious case, though. Could a function be greater than BB most of the time? What are the conditions, exactly?