Science 28 April 1995: Vol. 268 no. 5210 pp. 545-548 DOI: 10.1126/science.268.5210.545 Article Computation Beyond the Turing Limit Hava T. Siegelmann + Author Affiliations Department of Information Systems Engineering, Faculty of Industrial Engineering, Technion, Haifa 32000, Israel. E-mail: iehava@ie.technion.ac.il Abstract 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.
note footnote at the bottom: "http://www.sciencemag.org/content/313/5786/504.abstract, http://www.cs.toronto.edu/~amnih/cifar/talks/salakhut_talk.pdf. In a strict sense, this work was obsoleted by a slew of papers from 2011 which showed that you can achieve similar results to this 2006 result with “simple” algorithms, but it’s still true that current deep learning methods are better than the best “simple” feature learning schemes, and this paper was the first example that came to mind. [return]"