Closed-form Analytic Maps in One and Two Dimensions Can Simulate Turing Machines
Pascal Koiran, Cristopher Moore · 1996
We show closed-form analytic functions consisting of a finite number of trigonometric terms can simulate Turing machines, with exponential slowdown in one dimension or in real time in two or more. 1 A part of this author's work was done when he was visiting DIMACS at Rutgers University. 1 Introduction Various authors have independently shown [9, 12, 4, 14, 1] that finite-dimensional piecewise-linear maps and flows can simulate Turing machines. The construction is simple: associate the digits of the x and y coordinates of a point with the left and right halves of a Turing machine's tape. Then we can shift the tape head by halving or doubling x and y, and write on the tape by adding constants to them. Thus two dimensions suffice for a map, or three for a continuous-time flow. These systems can be thought of as billiards or optical ray tracing in three dimensions, recurrent neural networks, or hybrid systems. However, piecewise-linear functions are not very realistic from a physical p...