Experimental computation of real numbers by Newtonian machines
Edwin J Beggs, John Vivian Tucker · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences · 2007
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 [ p n , q n ], 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.