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.
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.