PT - JOURNAL ARTICLE
AU - Beggs, E.J
AU - Tucker, J.V
TI - Experimental computation of real numbers by Newtonian machines
DP - 2007 Jun 08
TA - Proceedings of the Royal Society A: Mathematical, Physical and Engineering Science
PG - 1541--1561
VI - 463
IP - 2082
4099 - http://rspa.royalsocietypublishing.org/content/463/2082/1541.short
4100 - http://rspa.royalsocietypublishing.org/content/463/2082/1541.full
SO - PROC R SOC A2007 Jun 08; 463
AB - Following a methodology we have proposed for analysing the nature of experimental computation, we prove that there is a three-dimensional Newtonian machine which given any point x∈[0, 1] can generate an infinite sequence [pn, qn], for n=1, 2, …, of rational number interval approximations, that converges to x as n→∞. The machine is a system for scattering and collecting particles. The theorem implies that every point x∈[0, 1] is computable by a simple Newtonian kinematic system that is bounded in space and mass and for which the calculation of the nth approximation of x takes place in O(n) time with O(n) energy. We describe variants of the scatter machine which explain why our machine is non-deterministic.