Computation Beyond the Turing Limit

Science  28 Apr 1995:
Vol. 268, Issue 5210, pp. 545-548
DOI: 10.1126/science.268.5210.545


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.