Embedding infinitely parallel computation in Newtonian kinematics

摘要

First, we reflect on computing sets and functions using measurements from experiments with a class of physical systems. We call this experimental computation. We outline a programme to analyse theoretically experimental computation in which a central problem is: Given a physical theory T, explore and classify the computational models that can be embedded in, and abstracted from, the physical systems specified by the physical theory T. We consider the embedding of arbitrary sets, functions, programs, and computers into designs for systems that can be specified in subtheories or fragments T of Newtonian kinematics in order to explore some of the physical assumptions of T that allows its systems to qualify as hyper-computers, i.e. physical models that compute sets and functions that cannot be computed in classical computability theory. In designing systems we work strictly within the chosen theory T and do not concern ourself with whether or not T is valid of the world today. We are interested in exploring the subtheory from a computational point of view and especially in restrictions on the assumptions of T that allow us to return from hyper-computation to classical computation.Secondly, we give a construction of an infinitely parallel machine that can decide all the arithmetical sets of natural numbers. We embed this hyper-computer as system in 3-dimensions obeying the laws of a fragment of Newtonian kinematics. In particular, the example shows that communication allowable in Newtonian kinematics is especially powerful. We conclude with further reflections and open problems.