DIMACS TR: 96-25

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

Authors: Pascal Koiran and Cristopher Moore


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.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-25.ps.gz
DIMACS Home Page