Abstract Geometrical Computation and the Linear Blum, Shub and Smale Model

摘要

Abstract geometrical computation naturally arises as a continuous counterpart of cellular automata. It relies on signals (dimension-less points) traveling at constant speed in a continuous space in continuous time. When signals collide, they are replaced by new signals according to some collision rules. This simple dynamics relies on real numbers with exact precision and is already known to be able to carry out any (discrete) Turing-computation. The Blum, Shub and Small (BSS) model is famous for computing over R (considered here as a R unlimited register machine) by performing algebraic computations. We prove that signal machines (set of signals and corresponding rules) and the infinite-dimension linear (multiplications are only by constants) BSS machines can simulate one another.