On Computable Numbers, Nonuniversality, and the Genuine Power of Parallelism
Selim G. Akl and Nancy Salay
We present a simple example that disproves the universality principle. Unlike previous counterexamples to computational universality, it does not rely on extraneous phenomena, such as the availability of input variables that are time varying, computational complexity that changes with time or order of execution, physical variables that interact with each other, uncertain deadlines, or mathematical conditions among the variables that must be obeyed throughout the computation. In the most basic case of the new example, all that is used is a single pre-existing global variable whose value is modified by the computation itself. In addition, our example offers a new dimension for separating the computable from the uncomputable, while illustrating the power of parallelism in computation.
Keywords and Phrases: Nonuniversality in computation; universal computer; simulation; models of computation; time unit; time-varying variables; time-varying complexity; rank-varying computational complexity; interacting variables; uncertain time constraints; mathematical constraints; finite and fixed number of operations per time unit, general-purpose computer; finiteness condition; unbounded space; unbounded time; communication with the outside world; Turing machine; random access machine; parallel random access machine.