{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T22:40:17Z","timestamp":1737067217684,"version":"3.33.0"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2007,6,5]],"date-time":"2007-06-05T00:00:00Z","timestamp":1181001600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Minds & Machines"],"published-print":{"date-parts":[[2007,8,7]]},"DOI":"10.1007\/s11023-007-9057-3","type":"journal-article","created":{"date-parts":[[2007,6,4]],"date-time":"2007-06-04T12:52:00Z","timestamp":1180961520000},"page":"233-247","source":"Crossref","is-referenced-by-count":7,"title":["Quantum Algorithms: Philosophical Lessons"],"prefix":"10.1007","volume":"17","author":[{"given":"Amit","family":"Hagar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,6,5]]},"reference":[{"key":"9057_CR1","doi-asserted-by":"crossref","first-page":"1021","DOI":"10.1126\/science.7973651","volume":"266","author":"L. M. Adleman","year":"1994","unstructured":"Adleman, L. M. (1994). Molecular computation of solutions to combinatorial problems. Science, 266, 1021\u20131024","journal-title":"Science"},{"key":"9057_CR2","unstructured":"Aharonov, D. (1998). Quantum computing. In D. Stauffer (Ed.), Annual review of computational physics (vol. VI). Singapore: World Scientific. See also http:\/\/xxx.arxiv.org\/quant-ph\/9812037"},{"key":"9057_CR3","doi-asserted-by":"crossref","unstructured":"Aharonov, D. et\u00a0al. (2004). Adiabatic quantum computation is equivalent to standard quantum computation. http:\/\/xxx.arxiv.org\/quant-ph\/0405098","DOI":"10.1109\/FOCS.2004.8"},{"key":"9057_CR49","doi-asserted-by":"crossref","first-page":"3457","DOI":"10.1103\/PhysRevA.52.3457","volume":"52","author":"A. Barenco","year":"1995","unstructured":"Barenco, A. et al. (1995). Elementary gates for quantum computation. Physics Review A, 52, 3457\u20133467","journal-title":"Physics Review A"},{"key":"9057_CR4","unstructured":"Calude, C. S. et\u00a0al. (2003). Transcending the limits of Turing computability. http:\/\/xxx.arxiv.org\/quant-ph\/0304128"},{"key":"9057_CR5","doi-asserted-by":"crossref","unstructured":"Cook, S. A. (1971). The complexity of theorem proving procedures. Proc. 3rd ACM Symposium on Theory of Computing, pp. 151\u2013158","DOI":"10.1145\/800157.805047"},{"key":"9057_CR6","unstructured":"Copeland, J. (1996). The church-turing thesis, Stanford Encyclopedia of Philosophy"},{"key":"9057_CR7","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1023\/A:1021105915386","volume":"12","author":"J. Copeland","year":"2002","unstructured":"Copeland, J. (2002). Hypercomputation. Minds and Machines, 12, 461\u2013502","journal-title":"Minds and Machines"},{"key":"9057_CR8","volume-title":"The undecidable","author":"M. Davis","year":"1958","unstructured":"Davis, M. (1958). The undecidable. New York: Dover"},{"key":"9057_CR9","unstructured":"Davis, M. (2003). The myth of hypercomputation. In C. Teuscher (Ed.), Alan turing, life and legacy of a great thinker. Springer: New York."},{"key":"9057_CR10","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1098\/rspa.1985.0070","volume":"400","author":"D. Deutsch","year":"1985","unstructured":"Deutsch, D. (1985). Quantum theory, the church turing principle, and the universal quantum computer. Proceedings of the Royal Society of London A, 400, 97\u2013117","journal-title":"Proceedings of the Royal Society of London A"},{"issue":"6","key":"9057_CR12","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1038\/scientificamerican0684-19","volume":"250","author":"A. K. Dewdney","year":"1984","unstructured":"Dewdney, A. K. (1984). On the spaghetti computer and other analog gadgets for problem solving. Scientific American, 250(6), 19\u201326","journal-title":"Scientific American"},{"key":"9057_CR11","doi-asserted-by":"crossref","first-page":"1015","DOI":"10.1103\/PhysRevA.51.1015","volume":"51","author":"D. DiVicenzo","year":"1995","unstructured":"DiVicenzo, D. (1995). Two\u2013bit gates are universal for quantum computation. Physical Review A, 51, 1015\u20131022","journal-title":"Physical Review A"},{"key":"9057_CR13","unstructured":"Farhi, E. et\u00a0al. (2000). Quantum computation by adiabatic evolution. http:\/\/xxx.arxiv.org\/quant-ph\/0001106"},{"key":"9057_CR14","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1007\/BF02650179","volume":"21","author":"R. Feynman","year":"1982","unstructured":"Feynman, R. (1982). Simulating physics with computers. International Journal of Theoretical Physics, 21, 467\u2013488","journal-title":"International Journal of Theoretical Physics"},{"key":"9057_CR15","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/BF00485230","volume":"2","author":"J. Fodor","year":"1974","unstructured":"Fodor, J. (1974). Special sciences. Synthese, 2, 97\u2013115","journal-title":"Synthese"},{"key":"9057_CR16","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0010-0277(88)90031-5","volume":"28","author":"J. Fodor","year":"1988","unstructured":"Fodor, J., & Pylyshyn, Z. (1988). Connectionism and cognitive architecture\u2014a critical analysis. Cognition, 28, 3\u201371","journal-title":"Cognition"},{"key":"9057_CR17","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/S0049-237X(08)71257-6","volume-title":"The kleene symposium","author":"R. Gandy","year":"1980","unstructured":"Gandy, R. (1980). Church\u2019s thesis and principles for mechanisms. In J. Barwise et\u00a0al. (Eds.), The kleene symposium (pp. 123\u2013148). North-Holland: Amsterdam"},{"key":"9057_CR18","volume-title":"Computers and intractability: A guide to the theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. New York: WH Freeman"},{"key":"9057_CR19","volume-title":"Primes and programming","author":"P. Giblin","year":"1993","unstructured":"Giblin, P. (1993). Primes and programming. Cambridge: Cambridge University Press"},{"key":"9057_CR20","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/s11023-005-9006-y","volume":"16","author":"A. Hagar","year":"2006","unstructured":"Hagar, A., & Korolev, A. (2006). Quantum hypercomputability? Minds and Machines, 16, 87\u201398.","journal-title":"Minds and Machines"},{"key":"9057_CR21","unstructured":"Hodges, A. (2005). Can quantum computing solve classically unsolvable problems? http:\/\/xxx.arxiv.org\/quant-ph\/0512248"},{"issue":"1","key":"9057_CR22","first-page":"126","volume":"94","author":"M. Hogarth","year":"1994","unstructured":"Hogarth, M. (1994). Non-turing computers and non-turing computability. PSA, 94(1), 126\u2013138","journal-title":"PSA"},{"key":"9057_CR23","doi-asserted-by":"crossref","first-page":"541","DOI":"10.1023\/A:1021130831101","volume":"12","author":"T. D. Kieu","year":"2002","unstructured":"Kieu, T. D. (2002). Quantum hypercomputability. Minds and Machines, 12, 541\u2013561","journal-title":"Minds and Machines"},{"key":"9057_CR24","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1080\/00107510302712","volume":"44","author":"T. D. Kieu","year":"2003","unstructured":"Kieu, T. D. (2003). Computing the noncomputable. Contemporary Physics, 44, 51\u201371","journal-title":"Contemporary Physics"},{"key":"9057_CR25","doi-asserted-by":"crossref","unstructured":"Kieu, T. D. (2004). A reformulation of Hilbert\u2019s tenth problem through quantum mechanics. Proceedings of the Royal Society A, 460, 1535\u20131545","DOI":"10.1098\/rspa.2003.1266"},{"issue":"1","key":"9057_CR26","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1142\/S0219749905000712","volume":"3","author":"T. D. Kieu","year":"2005","unstructured":"Kieu, T. D. (2005). An anatomy of a quantum adiabatic algorithm that transcends the turing computability. International Journal of Quantum Information, 3(1), 177\u2013183","journal-title":"International Journal of Quantum Information"},{"key":"9057_CR27","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1038\/35006012","volume":"404","author":"E. Knill","year":"2000","unstructured":"Knill, E. et\u00a0al. (2000). An algorithmic benchmark for quantum information processing. Nature, 404, 368\u2013370","journal-title":"Nature"},{"key":"9057_CR28","unstructured":"Linden, N., & Popescu, S. (1998). The Halting problem for quantum computers. http:\/\/xxx.arxiv.org\/quant-ph\/9806054"},{"key":"9057_CR29","doi-asserted-by":"crossref","first-page":"2354","DOI":"10.1103\/PhysRevLett.64.2354","volume":"64","author":"C. Moore","year":"1990","unstructured":"Moore, C. (1990). Unpredictability and undecidability in dynamical systems. Physical Review Letters, 64, 2354\u20132357","journal-title":"Physical Review Letters"},{"issue":"9","key":"9057_CR30","doi-asserted-by":"crossref","first-page":"1823","DOI":"10.1103\/PhysRevLett.78.1823","volume":"78","author":"J. Myers","year":"1997","unstructured":"Myers, J. (1997). Can a universal quantum computer be fully quantum? Physical Review Letters, 78(9), 1823\u20131824","journal-title":"Physical Review Letters"},{"key":"9057_CR31","volume-title":"Quantum computation and quantum information","author":"M. A. Nielsen","year":"2000","unstructured":"Nielsen, M. A., & Chuang, I. L. (2000). Quantum computation and quantum information. Cambridge: Cambridge University Press."},{"key":"9057_CR32","first-page":"81","volume":"39","author":"I. Pitowsky","year":"1990","unstructured":"Pitowsky, I. (1990). The physical church thesis and physical computational complexity. Iyyun, 39, 81\u201399","journal-title":"Iyyun"},{"key":"9057_CR33","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/1355-2198(96)85115-X","volume":"27","author":"I. Pitowsky","year":"1996","unstructured":"Pitowsky, I. (1996). Laplace\u2019s demon consults an oracle: The computational complexity of predictions. Studies in the History and Philosophy of Modern Physics, 27, 161\u2013180","journal-title":"Studies in the History and Philosophy of Modern Physics"},{"key":"9057_CR34","doi-asserted-by":"crossref","first-page":"S168","DOI":"10.1086\/341843","volume":"69","author":"I. Pitowsky","year":"2002","unstructured":"Pitowsky, I. (2002). Quantum speed-up of computations. Philosophy of Science, 69, S168\u2013S177","journal-title":"Philosophy of Science"},{"key":"9057_CR35","doi-asserted-by":"crossref","unstructured":"Pitowsky, I., & Shagrir, O. (2003). Physical hypercomputation and the church-turing thesis. Minds and Machines, 13, 87\u2013101","DOI":"10.1023\/A:1021365222692"},{"key":"9057_CR36","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/0001-8708(81)90001-3","volume":"39","author":"M. Pour-el","year":"1981","unstructured":"Pour-el, M., & Richards, I. (1981). The wave equation with computable initial data such that its unique solution is not computable. Advances in Mathematics, 39, 215\u2013239","journal-title":"Advances in Mathematics"},{"key":"9057_CR37","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/2004.001.0001","volume-title":"Computation and cognition: Toward a foundation for cognitive science","author":"Z. Pylyshyn","year":"1984","unstructured":"Pylyshyn, Z. (1984). Computation and cognition: Toward a foundation for cognitive science. Cambridge: MIT Press."},{"key":"9057_CR38","first-page":"21","volume-title":"Algorithms and complexity: New directions and recent results","author":"M. Rabin","year":"1976","unstructured":"Rabin, M. (1976). Probabilistic algorithms. In J. Traub (Eds.), Algorithms and complexity: New directions and recent results (pp. 21\u201339). New York: Academic Press"},{"key":"9057_CR39","doi-asserted-by":"crossref","unstructured":"Schrader, D. et\u00a0al. (2004). Neutral atoms quantum register. Physical Review Letters, 93(15), 150501","DOI":"10.1103\/PhysRevLett.93.150501"},{"key":"9057_CR41","doi-asserted-by":"crossref","first-page":"131","DOI":"10.5840\/monist19998214","volume":"82","author":"O. Shagrir","year":"1999","unstructured":"Shagrir, O. (1999). What is computer science about? The Monist, 82, 131\u2013149","journal-title":"The Monist"},{"key":"9057_CR42","doi-asserted-by":"crossref","unstructured":"Shor, P. (1994). Algorithms for quantum computation: Discrete logarithms and factoring. In S. Goldwasser (Ed.), Proceedings of 35th annual symposium on foundations of computer science (pp. 124\u2013134). IEEE Computer Society Press","DOI":"10.1109\/SFCS.1994.365700"},{"key":"9057_CR43","doi-asserted-by":"crossref","unstructured":"Shor, P. (2004). Progress in quantum algorithms. Quantum information processing, 3, 5\u201313","DOI":"10.1007\/s11128-004-3878-2"},{"key":"9057_CR40","doi-asserted-by":"crossref","first-page":"150","DOI":"10.5840\/monist19998213","volume":"82","author":"W. Sieg","year":"1999","unstructured":"Sieg, W., & Byrnes, J. (1999). An abstract model for parallel computations. The Monist, 82, 150\u2013164","journal-title":"The Monist"},{"key":"9057_CR45","doi-asserted-by":"crossref","unstructured":"Smith, W. (2005). Three counterexamples refuting Kieu\u2019s plan for \u201cquantum adiabatic hypercomputation\u201d; and some uncomputable quantum mechanical tasks, Forthcoming","DOI":"10.1016\/j.amc.2005.09.078"},{"key":"9057_CR44","unstructured":"Song, D. (2006). Unsolvability of the halting problem in quantum dynamics. http:\/\/xxx.arxiv.org\/quant-ph\/0610047"},{"key":"9057_CR46","unstructured":"Turing, A. (1936). On computable numbers, with an application to the Entscheidungsproblem, reprinted in M. Davis (1958)"},{"key":"9057_CR47","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/0378-4754(86)90105-9","volume":"28","author":"A. Vergis","year":"1986","unstructured":"Vergis, A. et\u00a0al. (1986). The complexity of analog computation. Mathematics and Computers in Simulation, 28, 91\u2013113","journal-title":"Mathematics and Computers in Simulation"},{"key":"9057_CR48","doi-asserted-by":"crossref","first-page":"735","DOI":"10.1103\/PhysRevLett.54.735","volume":"54","author":"S. Wolfram","year":"1985","unstructured":"Wolfram, S. (1985). Undecidability and intractability in theoretical physics. Physical Review Letters, 54, 735\u2013738","journal-title":"Physical Review Letters"}],"container-title":["Minds and Machines"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11023-007-9057-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11023-007-9057-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11023-007-9057-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T22:21:51Z","timestamp":1737066111000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11023-007-9057-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,6,5]]},"references-count":49,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,8,7]]}},"alternative-id":["9057"],"URL":"https:\/\/doi.org\/10.1007\/s11023-007-9057-3","relation":{},"ISSN":["0924-6495","1572-8641"],"issn-type":[{"type":"print","value":"0924-6495"},{"type":"electronic","value":"1572-8641"}],"subject":[],"published":{"date-parts":[[2007,6,5]]}}}