{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,9]],"date-time":"2025-12-09T11:26:39Z","timestamp":1765279599328},"reference-count":71,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Parallel Process. Lett."],"published-print":{"date-parts":[[2006,9]]},"abstract":"<jats:p>It is shown that the concept of a Universal Computer cannot be realized. Specifically, instances of a computable function [Formula: see text] are exhibited that cannot be computed on any machine [Formula: see text] that is capable of only a finite and fixed number of operations per step. This remains true even if the machine [Formula: see text] is endowed with an infinite memory and the ability to communicate with the outside world while it is attempting to compute [Formula: see text]. It also remains true if, in addition, [Formula: see text] is given an indefinite amount of time to compute [Formula: see text]. 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.<\/jats:p>","DOI":"10.1142\/s012962640600271x","type":"journal-article","created":{"date-parts":[[2006,9,28]],"date-time":"2006-09-28T01:41:20Z","timestamp":1159407680000},"page":"381-403","source":"Crossref","is-referenced-by-count":15,"title":["THREE COUNTEREXAMPLES TO DISPEL THE MYTH OF THE UNIVERSAL COMPUTER"],"prefix":"10.1142","volume":"16","author":[{"given":"SELIM G.","family":"AKL","sequence":"first","affiliation":[{"name":"School of Computing, Queen's University, Kingston, Ontario, K7L 3N6, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1126\/science.7973651"},{"key":"rf2","volume-title":"Parallel Computation: Models And Methods","author":"Akl S. G.","year":"1997"},{"key":"rf3","first-page":"301","volume":"4","author":"Akl S. G.","journal-title":"Parallel and Distributed Computing Practices"},{"key":"rf4","first-page":"193","volume":"5","author":"Akl S. G.","journal-title":"Parallel and Distributed Computing Practices"},{"key":"rf5","first-page":"455","volume":"21","author":"Akl S. G.","journal-title":"Computing and Informatics"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1142\/S012962640300115X"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1023\/B:SUPE.0000022574.59906.20"},{"key":"rf9","volume":"16","author":"Akl S. G.","journal-title":"Parallel Processing Letters"},{"key":"rf10","volume":"4","author":"Akl S. G.","journal-title":"International Journal of High Performance Computing and Networking"},{"key":"rf11","volume-title":"Parallel Computing: Models, Algorithms, and Applications","author":"Akl S. G.","year":"2006"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626499000463"},{"key":"rf13","first-page":"31","volume":"7","author":"Akl S. G.","journal-title":"International Journal of Computers and their Applications, Special Issue on High Performance Computing Systems"},{"key":"rf14","first-page":"219","volume":"19","author":"Akl S. G.","journal-title":"The Journal of Supercomputing"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1080\/17445760500033432"},{"key":"rf17","first-page":"5","volume":"4","author":"Akl S. G.","journal-title":"Journal of Mathematical Modelling and Algorithms, Special Issue on Parallel and Scientific Computations with Applications"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-006-2742-9"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-0313-4"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1016\/S0149-1970(03)00020-9"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0701-6"},{"key":"rf22","volume":"317","author":"Burgin M.","journal-title":"Theoretical Computer Science, Special Issue on: Super-recursive algorithms and hypercomputation"},{"key":"rf23","volume-title":"The Quest for the Quantum Computer","author":"Brown J.","year":"2000"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-001-1037-z"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.2000.1707"},{"key":"rf26","volume-title":"Unconventional Models of Computation","author":"Calude C. S.","year":"1998"},{"key":"rf27","volume-title":"Unconventional Models of Computation","author":"Calude C. S.","year":"2002"},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.1016\/j.biosystems.2004.05.032"},{"key":"rf29","doi-asserted-by":"publisher","DOI":"10.1023\/A:1019623616675"},{"key":"rf30","doi-asserted-by":"publisher","DOI":"10.2307\/2371045"},{"key":"rf32","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1099-0526(199809\/10)4:1<30::AID-CPLX9>3.0.CO;2-8"},{"key":"rf33","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021105915386"},{"key":"rf34","doi-asserted-by":"publisher","DOI":"10.1023\/A:1015607401307"},{"key":"rf35","first-page":"77","volume":"280","author":"Copeland B. J.","journal-title":"Scientific American"},{"key":"rf37","doi-asserted-by":"publisher","DOI":"10.1080\/00048409912348801"},{"key":"rf39","doi-asserted-by":"publisher","DOI":"10.1080\/08948550213852"},{"key":"rf42","volume-title":"The Fabric of Reality","author":"Deutsch D.","year":"1997"},{"key":"rf43","volume-title":"Automata, Languages and Machines","author":"Eilenberg S.","year":"1974"},{"key":"rf44","doi-asserted-by":"publisher","DOI":"10.1080\/09528130210153514"},{"key":"rf45","doi-asserted-by":"publisher","DOI":"10.1023\/A:1014019225365"},{"key":"rf46","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1007\/11494645_20","volume":"3526","author":"Goldin D.","year":"2005"},{"key":"rf48","volume-title":"The Pattern on the Stone","author":"Hillis D.","year":"1998"},{"key":"rf51","volume-title":"A Shortcut Through Time: The Path to the Quantum Computer","author":"Johnson G.","year":"2003"},{"key":"rf52","first-page":"191","volume":"28","author":"Karp R. M.","journal-title":"L'Enseignement Math\u00e9matique"},{"key":"rf53","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021130831101"},{"key":"rf54","doi-asserted-by":"publisher","DOI":"10.1080\/00107510302712"},{"key":"rf55","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2003.12.006"},{"key":"rf56","volume-title":"Mathematical Logic","author":"Kleene S. C.","year":"1967"},{"key":"rf57","volume-title":"Elements of the Theory of Computation","author":"Lewis H. R.","year":"1981"},{"key":"rf58","doi-asserted-by":"publisher","DOI":"10.1007\/b102253"},{"key":"rf59","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0931-7"},{"key":"rf62","first-page":"78","volume":"31","author":"Milner R.","journal-title":"Communications of the ACM"},{"key":"rf63","volume-title":"Quantum Computation and Quantum Information","author":"Nielsen M.","year":"2000"},{"key":"rf65","first-page":"73","volume":"2","author":"Nagy M.","journal-title":"International Journal of Unconventional Computing"},{"key":"rf66","doi-asserted-by":"publisher","DOI":"10.1093\/phisci\/axi108"},{"key":"rf67","first-page":"289","volume":"5","author":"Oksa G.","journal-title":"Parallel and Distributed Computing Practices"},{"key":"rf68","doi-asserted-by":"publisher","DOI":"10.1364\/AO.35.001827"},{"key":"rf69","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198519737.001.0001","volume-title":"The Emperor's New Mind","author":"Penrose R.","year":"1989"},{"key":"rf71","volume-title":"Models of Computation","author":"Savage J. E.","year":"1998"},{"key":"rf72","doi-asserted-by":"publisher","DOI":"10.1023\/A:1015694932257"},{"key":"rf73","doi-asserted-by":"publisher","DOI":"10.1126\/science.268.5210.545"},{"key":"rf74","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0707-8"},{"key":"rf75","doi-asserted-by":"publisher","DOI":"10.1088\/0957-4484\/10\/4\/318"},{"key":"rf76","doi-asserted-by":"publisher","DOI":"10.1007\/BF01888233"},{"key":"rf77","doi-asserted-by":"publisher","DOI":"10.1038\/352664a0"},{"key":"rf78","first-page":"8","volume":"1","author":"Stewart I.","journal-title":"Nonlinear Science Today"},{"key":"rf80","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-05642-4"},{"key":"rf81","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1145\/545151.545170","volume":"45","author":"Teuscher C.","journal-title":"Communications of the ACM"},{"key":"rf85","doi-asserted-by":"publisher","DOI":"10.1145\/253769.253801"},{"key":"rf87","doi-asserted-by":"publisher","DOI":"10.1145\/641205.641235"},{"key":"rf88","volume-title":"Explorations in Quantum Computing","author":"Williams C. P.","year":"1998"},{"key":"rf89","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0495-4"},{"key":"rf90","volume-title":"Theory of Computation","author":"Wood D.","year":"1987"}],"container-title":["Parallel Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S012962640600271X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,1]],"date-time":"2021-08-01T16:27:11Z","timestamp":1627835231000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S012962640600271X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,9]]},"references-count":71,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[2006,9]]}},"alternative-id":["10.1142\/S012962640600271X"],"URL":"https:\/\/doi.org\/10.1142\/s012962640600271x","relation":{},"ISSN":["0129-6264","1793-642X"],"issn-type":[{"value":"0129-6264","type":"print"},{"value":"1793-642X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,9]]}}}