Closed-form Analytic Maps in One and Two Dimensions Can Simulate Universal Turing Machines

Pascal Koiran and Cristopher Moore

Theoretical Computer Science 210 (1999) 217-223 (Special Issue on Real Numbers)

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.

Click here to download.


Cris Moore <moore@santafe.edu>