THREE COUNTEREXAMPLES TO DISPEL THE MYTH OF THE UNIVERSAL COMPUTER
Abstract
It is shown that the concept of a Universal Computer cannot be realized. Specifically, instances of a computable function
are exhibited that cannot be computed on any machine
that is capable of only a finite and fixed number of operations per step. This remains true even if the machine
is endowed with an infinite memory and the ability to communicate with the outside world while it is attempting to compute
. It also remains true if, in addition,
is given an indefinite amount of time to compute
. This result applies not only to idealized models of computation, such as the Turing Machine and the like, but also to all known general-purpose computers, including existing conventional computers (both sequential and parallel), as well as contemplated unconventional ones such as biological and quantum computers. Even accelerating machines (that is, machines that increase their speed at every step) cannot be universal.
This research was supported by the Natural Sciences and Engineering Research Council of Canada.
References
- Science 266, 1021 (1994). Crossref, ISI, Google Scholar
-
S. G. Akl , Parallel Computation: Models And Methods ( Prentice Hall , Upper Saddle River, New Jersey , 1997 ) . Google Scholar - Parallel and Distributed Computing Practices 4(3), 301 (2001). Google Scholar
- Parallel and Distributed Computing Practices 5(2), 193 (2002). ISI, Google Scholar
- Computing and Informatics 21(5), 455 (2002). ISI, Google Scholar
- Parallel Processing Letters 13(1), 65 (2003). Link, ISI, Google Scholar
S. G. Akl , Computing in the presence of uncertainty: Disturbing the peace, Proceedings of the International Conference on Parallel and Distributed Processing Techniques and ApplicationsI pp. 442–448. Google Scholar- The Journal of Supercomputing 29(1), 89 (2004). Crossref, ISI, Google Scholar
- Parallel Processing Letters 16(1), (2006). Google Scholar
- International Journal of High Performance Computing and Networking 4(2), (2006). Google Scholar
- , Parallel Computing: Models, Algorithms, and Applications , eds.
S. Rajasekaran and J. H. Reif ( Taylor and Francis, CRC Press , Boca Raton, Florida , 2006 ) . Google Scholar - Parallel Processing Letters 9(4), 499 (1999). Link, Google Scholar
- International Journal of Computers and their Applications, Special Issue on High Performance Computing Systems 7(1), 31 (2000). ISI, Google Scholar
- The Journal of Supercomputing 19(2), 219 (2001). ISI, Google Scholar
- International Journal of Parallel, Emergent and Distributed Systems 20(2), 147 (2005). Crossref, ISI, Google Scholar
S. G. Akl and L. Fava Lindon , Paradigms admitting superunitary behaviour in parallel computation, Proceedings of the Joint Conference on Vector and Parallel Processing (CONPAR 94, VAPP VI) pp. 301–312. Google Scholar- Journal of Mathematical Modelling and Algorithms, Special Issue on Parallel and Scientific Computations with Applications 4, 5 (2005). Google Scholar
- Journal of Supercomputing 35(2), 155 (2006). Crossref, ISI, Google Scholar
-
I. Antoniou , C. S. Calude and M. J. Dinneen (eds.) , Unconventional Models of Computation ( Springer-Verlag , London , 2001 ) . Crossref, Google Scholar - Progress in Nuclear Energy 43(1 - 4), 137 (2003). Crossref, ISI, Google Scholar
-
L. Blum , Complexity and Real Computation ( Springer-Verlag , New York , 1998 ) . Crossref, Google Scholar - Theoretical Computer Science, Special Issue on: Super-recursive algorithms and hypercomputation 317(1–3), (2004). Google Scholar
-
J. Brown , The Quest for the Quantum Computer ( Simon & Schuster , New York , 2000 ) . Google Scholar - Theory of Computing Systems 34(6), 565 (2001). Crossref, ISI, Google Scholar
- Journal of Parallel and Distributed Computing 61(5), 688 (2001). Crossref, ISI, Google Scholar
-
C. S. Calude , J. Casti and M. J. Dinneen (eds.) , Unconventional Models of Computation ( Springer-Verlag , Singapore , 1998 ) . Google Scholar -
C. S. Calude , M. J. Dinneen and F. Peper (eds.) , Unconventional Models of Computation ( Springer-Verlag , Berlin , 2002 ) . Google Scholar - BioSystems 77, 175 (2004). Crossref, ISI, Google Scholar
- Quantum Information Processing 1(1–2), 107 (2002). Crossref, ISI, Google Scholar
- American Journal of Mathematics 58, 345 (1936). Crossref, ISI, Google Scholar
- B. J. Copeland, The Church-Turing thesis, http://plato.stanford.edu/entries/church-turing/ . Google Scholar
- Complexity 4, 30 (1998). Crossref, Google Scholar
- Minds and Machines 12(4), 461 (2002). Crossref, ISI, Google Scholar
- Mind and Machines 12(2), 281 (2002). Crossref, ISI, Google Scholar
- Scientific American 280(4), 77 (1999). ISI, Google Scholar
- B. J. Copeland and D. Proudfoot, Introduction to hypercomputation: Computing the uncomputable, http://www.calculemus.org/x/Copeland-etc/copeland1.html . Google Scholar
- Australasian Journal of Philosophy 77(1), 46 (1999). Crossref, ISI, Google Scholar
- B. J. Cordy, private communication . Google Scholar
- Comments on Theoretical Biology 7(3), 177 (2002). Crossref, Google Scholar
- M. Davis, The myth of hypercomputation, in [80] . Google Scholar
D. Deutsch , Quantum theory, the Church-Turing principle of the Universal Quantum Computer, Proceedings of the Royal Society of London pp. 97–117. Google Scholar-
D. Deutsch , The Fabric of Reality ( Penguin , New York , 1997 ) . Google Scholar -
S. Eilenberg , Automata, Languages and Machines A ( Academic Press , New York , 1974 ) . Google Scholar - Journal of Experimental and Theoretical Artificial Intelligence 14, 1 (2002). Crossref, ISI, Google Scholar
- International Journal of Theoretical Physics 41(2), 341 (2002). Crossref, ISI, Google Scholar
D. Goldin and P. Wegner ,Lecture Notes in Computer Science 3526 (Springer-Verlag, Berlin, 2005) pp. 152–168. Google ScholarC. E. Hewitt , P. Bishop and R. Steiger , A universal modular actor formalism for artificial intelligence, Proceedings of the Third International Joint Conference on Artificial Intelligence pp. 235–245. Google Scholar-
D. Hillis , The Pattern on the Stone ( Basic Books , New York , 1998 ) . Google Scholar - Hypercomputation, http://encyclopedia.laborlawtalk.com/Hypercomputation . Google Scholar
- Hypercomputation, http://en.wikipedia.org/wiki/Hypercomputation . Google Scholar
-
G. Johnson , A Shortcut Through Time: The Path to the Quantum Computer ( Random House , New York , 2003 ) . Google Scholar - L'Enseignement Mathématique 28, 191 (1982). Google Scholar
- Minds and Machines 12(4), 541 (2002). Crossref, ISI, Google Scholar
- Contemporary Physics 44(1), 51 (2003). Crossref, ISI, Google Scholar
- Theoretical Computer Science 317(1–3), 93 (2004). Crossref, ISI, Google Scholar
-
S. C. Kleene , Mathematical Logic ( Wiley , New York , 1967 ) . Google Scholar -
H. R. Lewis and C. H. Papadimitriou , Elements of the Theory of Computation ( Prentice Hall , Englewood Cliffs, New Jersey , 1981 ) . Google Scholar -
K. Li , Y. Pan and S.-Q. Zheng (eds.) , Parallel Computing Using Optical Interconnections ( Kluwer Academic Publishers , Dordrecht, The Netherlands , 1998 ) . Crossref, Google Scholar -
Z. Manna and A. Pnueli , The Temporal Logic of Reactive and Concurrent Systems ( Springer-Verlag , New York , 1992 ) . Crossref, Google Scholar - W. Marciszewski, Text commented: B. Jack Copeland's "The Church-Turing Thesis", http://www.calculemus.org/forum/4/CT-thesis.html . Google Scholar
H. Meijer and D. Rappaport , Simultaneous Edge Flips for Convex Subdivisions,16th Canadian Conference on Computational Geometry (2004) pp. 57–59. Google Scholar- Communications of the ACM 31(1), 78 (1993). ISI, Google Scholar
-
M. Nielsen and I. Chuang , Quantum Computation and Quantum Information ( Cambridge University Press , Cambridge, England , 2000 ) . Google Scholar M. Nagy and S. G. Akl , On the importance of parallelism for quantum computation and the concept of a universal computer, Proceedings of the Fourth International Conference on Unconventional Computation pp. 176–190. Google Scholar- International Journal of Unconventional Computing 2(1), 73 (2006). ISI, Google Scholar
- The British Journal for the Philosophy of Science 56(1), 147 (2005). Crossref, ISI, Google Scholar
- Parallel and Distributed Computing Practices 5(3), 289 (2004). Google Scholar
- Applied Optics 35, 1827 (1996). Crossref, ISI, Google Scholar
-
R. Penrose , The Emperor's New Mind ( Oxford University Press , Oxford, England , 1989 ) . Crossref, Google Scholar - J. Raskin, Computers are not Turing machines, http://humane.sourceforge.net/unpublished/turing_machines.html . Google Scholar
-
J. E. Savage , Models of Computation ( Addison-Wesley , Reading, Massachusetts , 1998 ) . Google Scholar - Minds and Machines 12, 221 (2002). Crossref, ISI, Google Scholar
- Science 268(5210), 545 (1995). Crossref, ISI, Google Scholar
-
H. T. Siegelmann , Neural Networks and Analog Computation: Beyond the Turing limit ( Birkhäuser , Boston , 1999 ) . Crossref, Google Scholar - Nanotechnology 10, 464 (1999). Crossref, ISI, Google Scholar
- Formal Aspects of Computing 2(4), 331 (1990). Crossref, Google Scholar
- Nature 352, 664 (1991). Crossref, ISI, Google Scholar
- Nonlinear Science Today 1, 8 (1991). Google Scholar
- Super-Turing computation, http://en.wikipedia.org/wiki/Super-Turing_computation . Google Scholar
-
C. Teuscher (ed.) , Alan Turing: Life and Legacy of a Great Thinker ( Springer-Verlag , New York , 2004 ) . Crossref, Google Scholar - Communications of the ACM 45(8), 23 (2002). Crossref, Google Scholar
- A. M. Turing, On computable numbers with an application to the entscheidungsproblem, Proceedings of the London mathematical Society, Ser. 2, Vol. 42, 1936, pp. 230–265; Vol. 43, 1937, pp. 544–546 . Google Scholar
A. M. Turing , Systems of logic based on ordinals, Proceedings of the London Mathematical Society45 (1939) pp. 161–228. Google Scholar- A. M. Turing, Intelligent machinery, Report, National Physics Laboratory, 1948. Reprinted in: B. Meltzer and D. Michie, Eds., Machine Intelligence 5, Edinburgh University Press, Edinburgh, Scotland, 1969, pp. 3–23 . Google Scholar
- Communications of the ACM 40(5), 80 (1997). Crossref, ISI, Google Scholar
- P. Wegner and D. Goldin, Interaction, computability, and Church's thesis, Brown University, 1999. http://www.cs.brown.du/people/pw/papers/bcj1.pdf . Google Scholar
- Communications of the ACM 46(4), 100 (1997). Crossref, ISI, Google Scholar
-
C. P. Williams and S. H. Clearwater , Explorations in Quantum Computing ( Springer-Verlag , Heidelberg , 1998 ) . Google Scholar -
C. P. Williams and S. H. Clearwater , Ultimate Zero and One: Computing at the Quantum Frontier ( Springer-Verlag , Heidelberg , 2000 ) . Crossref, Google Scholar -
D. Wood , Theory of Computation ( Harper & Row , New York , 1987 ) . Google Scholar


