The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

An Isaac Newton Institute Programme

Logic and Algorithms

A physical analysis of mechanical computability

25th May 2006

Author: Steven Lindell (Haverford)

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.