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

Pascal Koiran and Cristopher Moore
Additional contact information
Cristopher Moore: http://www.santafe.edu/~moore/

Working Papers from Santa Fe Institute

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.

Key words. dynamical systems, universal computation, iterated maps, analytic functions, Halting Problem, Collatz functions, continuous computation, analog computation

Date: 1996-06
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wop:safiwp:96-06-037

Access Statistics for this paper

More papers in Working Papers from Santa Fe Institute Contact information at EDIRC.
Bibliographic data for series maintained by Thomas Krichel ().