Can Newtonian systems, bounded in space, time, mass and energy compute all functions?

• Published in: Theoretical computer science 2007-02, Vol.371 (1), p.4-19
• Main Authors: Beggs, Edwin J., Tucker, John V.
• Format: Article
• Language: English
• Subjects: Computability; Experimental computation; Hypercomputation; Newtonian machines
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/j.tcs.2006.10.010

In the theoretical analysis of the physical basis of computation there is a great deal of confusion and controversy (e.g., on the existence of hyper-computers). First, we present a methodology for making a theoretical analysis of computation by physical systems. We focus on the construction and analysis of simple examples that are models of simple sub-theories of physical theories. Then we illustrate the methodology by presenting a simple example for Newtonian Kinematics, and a critique that leads to a substantial extension of the methodology. The example proves that for any set A of natural numbers there exists a 3-dimensional Newtonian kinematic system M A , with an infinite family of particles P n whose total mass is bounded, and whose observable behaviour can decide whether or not n ∈ A for all n ∈ N in constant time. In particular, the example implies that simple Newtonian kinematic systems that are bounded in space, time, mass and energy can compute all possible sets and functions on discrete data. The system is a form of marble run and is a model of a small fragment of Newtonian Kinematics. Next, we use the example to extend the methodology. The marble run shows that a formal theory for computation by physical systems needs strong conditions on the notion of experimental procedure and, specifically, on methods for the construction of equipment. We propose to extend the methodology by defining languages to express experimental procedures and the construction of equipment. We conjecture that the functions computed by experimental computation in Newtonian Kinematics are “equivalent” to those computed by algorithms, i.e. the partial computable functions.