Note to users. If you're seeing this message, it means that your browser cannot find this page's style/presentation instructions -- or possibly that you are using a browser that does not support current Web standards. Find out more about why this message is appearing, and what you can do to make your experience of our site the best it can be.

Science 28 April 1995:
Vol. 268. no. 5210, pp. 545 - 548
DOI: 10.1126/science.268.5210.545
Prev | Table of Contents | Next

Articles

Computation Beyond the Turing Limit

Hava T. Siegelmann 1

1 Department of Information Systems Engineering, Faculty of Industrial Engineering, Technion, Haifa 32000, Israel. E-mail: iehava@ie.technion.ac.il

Extensive efforts have been made to prove the Church-Turing thesis, which suggests that all realizable dynamical and physical systems cannot be more powerful than classical models of computation. A simply described but highly chaotic dynamical system called the analog shift map is presented here, which has computational power beyond the Turing limit (super-Turing); it computes exactly like neural networks and analog machines. This dynamical system is conjectured to describe natural physical phenomena.

Submitted on July 26, 1994
Accepted on January 25, 1995


THIS ARTICLE HAS BEEN CITED BY OTHER ARTICLES:
The Cardiac Physiome: perspectives for the future.
J. Bassingthwaighte, P. Hunter, and D. Noble (2009)
Exp Physiol 94, 597-605
   Abstract »    Full Text »    PDF »


To Advertise     Find Products

Science. ISSN 0036-8075 (print), 1095-9203 (online)