I read that if BB(n) did not grow faster than all computable sequences of integers, you could solve the halting problem and contradict Turing's theorem.
I'm trying to figure out how you could specifically do this. One obvious possibility is to build an n-state Turing machine that looks for a solution to an undecidable problem, then simply waiting for it to pass BB(n) transitions. This should be feasible since BB(n), in this scenario, is small, and surpassing it would prove that the machine loops forever.
But this isn't a satisfactory answer because surely decidability isn't about how feasible a procedure is in practice, but whether it's decidable in theory - what if computers were powerful enough to be able to implement this in our current universe where BB(n) is very large? Shouldn't we just assume that the machine is independent of number theory instead?