RT Journal Article
SR Electronic
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
FD The Royal Society
SP 1541
OP 1561
DO 10.1098/rspa.2007.1835
VO 463
IS 2082
A1 Beggs, E.J
A1 Tucker, J.V
YR 2007
UL http://rspa.royalsocietypublishing.org/content/463/2082/1541.abstract
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.