No Access

THREE COUNTEREXAMPLES TO DISPEL THE MYTH OF THE UNIVERSAL COMPUTER

SELIM G. AKL

School of Computing, Queen's University, Kingston, Ontario, K7L 3N6, Canada

https://doi.org/10.1142/S012962640600271XCited by:14 (Source: Crossref)

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.

Keywords:

References

L. A. Adleman, Science 266, 1021 (1994). Crossref, Web of Science, Google Scholar
S. G. Akl , Parallel Computation: Models And Methods ( Prentice Hall , Upper Saddle River, New Jersey , 1997 ) . Google Scholar
S. G. Akl, Parallel and Distributed Computing Practices 4(3), 301 (2001). Google Scholar
S. G. Akl, Parallel and Distributed Computing Practices 5(2), 193 (2002). Web of Science, Google Scholar
S. G. Akl, Computing and Informatics 21(5), 455 (2002). Web of Science, Google Scholar
S. G. Akl, Parallel Processing Letters 13(1), 65 (2003). Link, Web of Science, 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
S. G. Akl, The Journal of Supercomputing 29(1), 89 (2004). Crossref, Web of Science, Google Scholar
S. G. Akl, Parallel Processing Letters 16(1), (2006). Google Scholar
S. G. Akl, International Journal of High Performance Computing and Networking 4(2), (2006). Google Scholar
S. G. Akl , Parallel Computing: Models, Algorithms, and Applications , eds. S. Rajasekaran and J. H. Reif ( Taylor and Francis, CRC Press , Boca Raton, Florida , 2006 ) . Google Scholar
S. G. Akl and S. D. Bruda, Parallel Processing Letters 9(4), 499 (1999). Link, Google Scholar
S. G. Akl and S. D. Bruda, International Journal of Computers and their Applications, Special Issue on High Performance Computing Systems 7(1), 31 (2000). Web of Science, Google Scholar
S. G. Akl and S. D. Bruda, The Journal of Supercomputing 19(2), 219 (2001). Web of Science, Google Scholar
S. G. Akl, B. J. Cordy and W. Yao, International Journal of Parallel, Emergent and Distributed Systems 20(2), 147 (2005). Crossref, Web of Science, 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
S. G. Akl and W. Yao, Journal of Mathematical Modelling and Algorithms, Special Issue on Parallel and Scientific Computations with Applications 4, 5 (2005). Google Scholar
S. G. Akl and W. Yao, Journal of Supercomputing 35(2), 155 (2006). Crossref, Web of Science, Google Scholar
I. Antoniou , C. S. Calude and M. J. Dinneen (eds.) , Unconventional Models of Computation ( Springer-Verlag , London , 2001 ) . Crossref, Google Scholar
B. Barutçuet al., Progress in Nuclear Energy 43(1 - 4), 137 (2003). Crossref, Web of Science, Google Scholar
L. Blum et al. , Complexity and Real Computation ( Springer-Verlag , New York , 1998 ) . Crossref, Google Scholar
M. Burgin and A. Klinger (eds.), 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
S. D. Bruda and S. G. Akl, Theory of Computing Systems 34(6), 565 (2001). Crossref, Web of Science, Google Scholar
S. D. Bruda and S. G. Akl, Journal of Parallel and Distributed Computing 61(5), 688 (2001). Crossref, Web of Science, 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
C. S. Calude and G. Păun, BioSystems 77, 175 (2004). Crossref, Web of Science, Google Scholar
C. S. Calude and B. Pavlov, Quantum Information Processing 1(1–2), 107 (2002). Crossref, Web of Science, Google Scholar
A. Church, American Journal of Mathematics 58, 345 (1936). Crossref, Web of Science, Google Scholar
B. J. Copeland, The Church-Turing thesis, http://plato.stanford.edu/entries/church-turing/ . Google Scholar
B. J. Copeland, Complexity 4, 30 (1998). Crossref, Google Scholar
B. J. Copeland, Minds and Machines 12(4), 461 (2002). Crossref, Web of Science, Google Scholar
B. J. Copeland, Mind and Machines 12(2), 281 (2002). Crossref, Web of Science, Google Scholar
B. J. Copeland and D. Proudfoot, Scientific American 280(4), 77 (1999). Web of Science, 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
B. J. Copeland and R. Sylvan, Australasian Journal of Philosophy 77(1), 46 (1999). Crossref, Web of Science, Google Scholar
B. J. Cordy, private communication . Google Scholar
M. Daley and L. Kari, 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
C. Eliasmith, Journal of Experimental and Theoretical Artificial Intelligence 14, 1 (2002). Crossref, Web of Science, Google Scholar
G. Etesi and I. Németi, International Journal of Theoretical Physics 41(2), 341 (2002). Crossref, Web of Science, Google Scholar
D. Goldin and P. Wegner, Lecture Notes in Computer Science 3526 (Springer-Verlag, Berlin, 2005) pp. 152–168. Google Scholar
C. 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
R. M. Karp and R. Lipton, L'Enseignement Mathématique 28, 191 (1982). Google Scholar
T. D. Kieu, Minds and Machines 12(4), 541 (2002). Crossref, Web of Science, Google Scholar
T. D. Kieu, Contemporary Physics 44(1), 51 (2003). Crossref, Web of Science, Google Scholar
T. D. Kieu, Theoretical Computer Science 317(1–3), 93 (2004). Crossref, Web of Science, 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
R. Milner, Communications of the ACM 31(1), 78 (1993). Web of Science, 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
M. Nagy and S. G. Akl, International Journal of Unconventional Computing 2(1), 73 (2006). Web of Science, Google Scholar
T. Ord and T. D. Kieu, The British Journal for the Philosophy of Science 56(1), 147 (2005). Crossref, Web of Science, Google Scholar
G. Oksa, M. Becka and M. Vajtersic, Parallel and Distributed Computing Practices 5(3), 289 (2004). Google Scholar
S. Pavel and S. G. Akl, Applied Optics 35, 1827 (1996). Crossref, Web of Science, 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
O. Shagrir, Minds and Machines 12, 221 (2002). Crossref, Web of Science, Google Scholar
H. T. Siegelmann, Science 268(5210), 545 (1995). Crossref, Web of Science, Google Scholar
H. T. Siegelmann , Neural Networks and Analog Computation: Beyond the Turing limit ( Birkhäuser , Boston , 1999 ) . Crossref, Google Scholar
C. Siehs and B. Mayer, Nanotechnology 10, 464 (1999). Crossref, Web of Science, Google Scholar
M. Stannett, Formal Aspects of Computing 2(4), 331 (1990). Crossref, Google Scholar
I. Stewart, Nature 352, 664 (1991). Crossref, Web of Science, Google Scholar
I. Stewart, 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
C. Teuscher and M. Sipper, 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
P. Wegner, Communications of the ACM 40(5), 80 (1997). Crossref, Web of Science, 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
P. Wegner and D. Goldin, Communications of the ACM 46(4), 100 (1997). Crossref, Web of Science, 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