Content area
Full text
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.
Humanity's intellectual quest to decipher nature and to master it has led to numerous efforts to build machines-endowed. with artificial intelligence-that simulate the world or communicate with it (1-4). The computational power and dynamic behavior of such computers is a central question for mathematicians, computer scientists, and physicists. Computer models are ultimately based on idealized physical systems, called "realizable" or "natural" models. Since 1936, the standard accepted model of universal computation has been the Turing machine (5), which forms the basis of modern computer science. The Church-Turing thesis, the prevailing paradigm in computer science, states that no realizable computing device can be more powerful (aside from relative polynomial speedups that are a result of richer instruction sets or parallel computation) than a Turing machine (5). This report questions that assumption, proposing an alternative model of computation, possibly realizable as well, whose computational power can surpass that of the Turing model. The proposed model builds on a particular chaotic dynamical system (6); by applying the system to computer science, a "super-Turing" model can be developed (7).
Demonstrating the existence of an ideally realizable super-Turing model has practical and theoretical implications. Theoretically, it could open the way for theories of computation that go beyond the Turing model. On a practical level, computers designed and built on the basis of super-Turing theories should be capable of modeling phenomena that existing computers are not powerful enough to model well.
In computer science, machines are classified according to the classes of tasks they can execute or the functions they can perform. The most popular model is the Turing machine, introduced by the English math ematician Alan Turing in 1936. The Turing machine (5) allows for unbounded "external" storage (tapes) in addition to the finite information represented by the current "internal" state (control) of the system. At every step,...