TY - JOUR
T1 - Experimental computation of real numbers by Newtonian machines
JF - Proceedings of the Royal Society A: Mathematical, Physical and Engineering Science
JO - PROC R SOC A
SP - 1541
LP - 1561
M3 - 10.1098/rspa.2007.1835
VL - 463
IS - 2082
AU - Beggs, E.J
AU - Tucker, J.V
Y1 - 2007/06/08
UR - http://rspa.royalsocietypublishing.org/content/463/2082/1541.abstract
N2 - 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.
ER -