News for hackers. Stuff that matters.
Re:How the Slowest Computer Programs Illuminate Math’s Funda... by chalst on Friday December 11, 2020 @04:48AM (#25383979)
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.

There are no comments on this comment yet.