โ Scribed by Peter Elias
No coin nor oath required. For personal study only.
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.
๐ SIMILAR VOLUMES
A differential game is considered in which the time until a point reaches a target set is the pay functional. The sufficient conditions for the given discontinuous function to be identical with the value function of the game are obtained. The conditions are formulated in terms of the classical conce