4 ms·

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 a

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.

cft 6y ago
Yes, I should have thought more about it. So these BB(N) numbers are direct complexity bounds on various mathematical statements.