Minimum times and memories needed to compute the values of a function

摘要

A deterministic sequential device receives one input symbol at a time, prints output symbols from left to right on an output tape, and halts for some input sequences. Such a device can be used to compute some representation of the value of a function when some representation of the argument of the function is supplied as input. Lower bounds to the times-required to find the values of the function and to averages of those times follow, even if the device is very powerful. The bounds can be attained by sufficiently powerful devices (which may not be finitely describable) and can be approached by finite-state machines when the appropriate representations of the range and the domain are chosen. A speedup theorem permits almost all values to be computed more rapidly, but does not reduce the average time to find a value. A universal three-state automaton computes the values of any properly represented function taking at most twice the average time required by the best computer for that function.