Abstract: Incorporating matter and energy
requirements into physically implemented machines sheds new light on
feasible computability. Under certain circumstances, conventional
mathematical models may not be asymptotically realizable due to the
limited availability of resources required to store data and execute
instructions.
Abstract: Turing's model of autonomous computation
is based on the idealized psychological characteristics of a human
calculator—its ability to change its "state of mind" in a stepwise
fashion based on the recognition of symbolic configurations. This leads
to a mathematical model of effective computability, with its well known
capabilities and limitations. We extend this analysis to the idealized
physiological characteristics of a machine computer—its ability to
manipulate matter using energy. This leads to a new notion of
feasibility based on physical resource bounds, in which mass and energy
constraints further restrict the usual notions of space and time
complexity.