Physical Computation: How General are Gandys Principles for Mechanisms?
What are the limits of physical computation? In his Churchs Thesis and Principles for Mechanisms, Turings student Robin Gandy proved that any machine satisfying four idealised physical principles is equivalent to some Turing machine. Gandys four principles in effect define a class of computing machines (Gandy machines). Our question is: What is the relationship of this class to the class of all (ideal) physical computing machines? Gandy himself suggests that the relationship is identity. We do not share this view. We will point to interesting examples of (ideal) physical machines that fall outside the class of Gandy machines and compute functions that are not Turing-machine computable.
physical computation gandy churchs thesis accelerating turing machine asynchronous computation davies determinism hogarth hypercomputation pitowsky supertask thesis m