World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

THREE COUNTEREXAMPLES TO DISPEL THE MYTH OF THE UNIVERSAL COMPUTER

    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

    • L. A. Adleman, Science 266, 1021 (1994). Crossref, ISIGoogle 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). ISIGoogle Scholar
    • S. G. Akl, Computing and Informatics 21(5), 455 (2002). ISIGoogle Scholar
    • S. G. Akl, Parallel Processing Letters 13(1), 65 (2003). Link, ISIGoogle 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, ISIGoogle 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). LinkGoogle 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). ISIGoogle Scholar
    • S. G. Akl and S. D. Bruda, The Journal of Supercomputing 19(2), 219 (2001). ISIGoogle Scholar
    • S. G. Akl, B. J. Cordy and W. Yao, International Journal of Parallel, Emergent and Distributed Systems 20(2), 147 (2005). Crossref, ISIGoogle 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, ISIGoogle Scholar
    • I.   Antoniou , C. S.   Calude and M. J.   Dinneen (eds.) , Unconventional Models of Computation ( Springer-Verlag , London , 2001 ) . CrossrefGoogle Scholar
    • B. Barutçuet al., Progress in Nuclear Energy 43(1 - 4), 137 (2003). Crossref, ISIGoogle Scholar
    • L.   Blum et al. , Complexity and Real Computation ( Springer-Verlag , New York , 1998 ) . CrossrefGoogle 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, ISIGoogle Scholar
    • S. D. Bruda and S. G. Akl, Journal of Parallel and Distributed Computing 61(5), 688 (2001). Crossref, ISIGoogle 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, ISIGoogle Scholar
    • C. S. Calude and B. Pavlov, Quantum Information Processing 1(1–2), 107 (2002). Crossref, ISIGoogle Scholar
    • A. Church, American Journal of Mathematics 58, 345 (1936). Crossref, ISIGoogle Scholar
    • B. J. Copeland, The Church-Turing thesis, http://plato.stanford.edu/entries/church-turing/ . Google Scholar
    • B. J. Copeland, Complexity 4, 30 (1998). CrossrefGoogle Scholar
    • B. J. Copeland, Minds and Machines 12(4), 461 (2002). Crossref, ISIGoogle Scholar
    • B. J. Copeland, Mind and Machines 12(2), 281 (2002). Crossref, ISIGoogle Scholar
    • B. J. Copeland and D. Proudfoot, Scientific American 280(4), 77 (1999). ISIGoogle 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, ISIGoogle Scholar
    • B. J. Cordy, private communication . Google Scholar
    • M. Daley and L. Kari, Comments on Theoretical Biology 7(3), 177 (2002). CrossrefGoogle 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, ISIGoogle Scholar
    • G. Etesi and I. Németi, International Journal of Theoretical Physics 41(2), 341 (2002). Crossref, ISIGoogle 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, ISIGoogle Scholar
    • T. D. Kieu, Contemporary Physics 44(1), 51 (2003). Crossref, ISIGoogle Scholar
    • T. D. Kieu, Theoretical Computer Science 317(1–3), 93 (2004). Crossref, ISIGoogle 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 ) . CrossrefGoogle Scholar
    • Z.   Manna and A.   Pnueli , The Temporal Logic of Reactive and Concurrent Systems ( Springer-Verlag , New York , 1992 ) . CrossrefGoogle 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). ISIGoogle 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). ISIGoogle Scholar
    • T. Ord and T. D. Kieu, The British Journal for the Philosophy of Science 56(1), 147 (2005). Crossref, ISIGoogle 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, ISIGoogle Scholar
    • R.   Penrose , The Emperor's New Mind ( Oxford University Press , Oxford, England , 1989 ) . CrossrefGoogle 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, ISIGoogle Scholar
    • H. T. Siegelmann, Science 268(5210), 545 (1995). Crossref, ISIGoogle Scholar
    • H. T.   Siegelmann , Neural Networks and Analog Computation: Beyond the Turing limit ( Birkhäuser , Boston , 1999 ) . CrossrefGoogle Scholar
    • C. Siehs and B. Mayer, Nanotechnology 10, 464 (1999). Crossref, ISIGoogle Scholar
    • M. Stannett, Formal Aspects of Computing 2(4), 331 (1990). CrossrefGoogle Scholar
    • I. Stewart, Nature 352, 664 (1991). Crossref, ISIGoogle 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 ) . CrossrefGoogle Scholar
    • C. Teuscher and M. Sipper, Communications of the ACM 45(8), 23 (2002). CrossrefGoogle 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, ISIGoogle 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, ISIGoogle 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 ) . CrossrefGoogle Scholar
    • D.   Wood , Theory of Computation ( Harper & Row , New York , 1987 ) . Google Scholar