If a computation goes through N states before completing the universe in which it takes place has to have at least N possible states. One theory (https://en.wikipedia.org/wiki/Bekenstein_bound) would state that the possible number of bits of information in a universe with radius R is the surface of the sphere 4 * pi * R^2 expressed in Planck units. This gives a limit to how many states this universe can have.
Nope. Suppose that say, state #16 and state #416 are in fact identical. Well then this machine does not halt, as of course being in this state leads back to the same state again in just four hundred moves, state #17 and #417 and so on will be the same too.
The notional paper tape might have identical states, but if this happens in a machine that does eventually halt the rest of the machine state must be different, and these are both state that a universe must keep in order to instantiate the machine.
Different senses of the word "state". Such a machine could have fewer state-machine states than steps, but the overall state of the machine (including all its auxiliary storage) must never repeat, or it's in a loop and will never terminate. And BB machines must terminate, by definition.
Smaller, yes: if a TM uses n bits of space, its execution time can exceed any polynomial of n in steps.
But any such space-bounded deterministic computation that takes 2^n steps will not terminate, by exhaustion of possible state transitions, and nontermination would mean it does not compute a function over all inputs. This constraint is small in terms of the kind of growth functions this kind of maths deals with.
