Skip to content



A physical analysis of mechanical computability

Lindell, S (Haverford)
Thursday 25 May 2006, 11:00-12:00

Seminar Room 1, Newton Institute


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.


[pdf ]

Back to top ∧