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

DIMACS TR: 96-25

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

Authors: Pascal Koiran and Cristopher Moore

ABSTRACT
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