{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,13]],"date-time":"2025-12-13T06:44:19Z","timestamp":1765608259278},"publisher-location":"Berlin, Heidelberg","reference-count":57,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540252610"},{"type":"electronic","value":"9783540318347"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/978-3-540-31834-7_1","type":"book-chapter","created":{"date-parts":[[2010,7,2]],"date-time":"2010-07-02T14:23:40Z","timestamp":1278080620000},"page":"1-17","source":"Crossref","is-referenced-by-count":11,"title":["Algorithmic Randomness, Quantum Physics, and Incompleteness"],"prefix":"10.1007","author":[{"given":"Cristian S.","family":"Calude","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"1_CR1","unstructured":"Agrawal, M., Kayal, N., Saxena, N.: PRIMES is in P (August 6, 2002), http:\/\/www.cse.iitk.ac.in\/primality.pdf"},{"key":"1_CR2","first-page":"19","volume":"44","author":"E. Allender","year":"2004","unstructured":"Allender, E., Buhrman, H., Kouck\u00fd, M.: What can be efficiently reduced to the Kolmogorov-random strings? Electronic Colloquium on Computational Complexity, Report\u00a044, 19 (2004)","journal-title":"Electronic Colloquium on Computational Complexity, Report"},{"issue":"1","key":"1_CR3","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1137\/0210008","volume":"10","author":"C.H. Bennett","year":"1981","unstructured":"Bennett, C.H., Gill, J.: Relative to a random oracle A, P A \u2260 N P A \u2260 co-N P A with probability 1. SIAM Journal on Computing\u00a010(1), 96\u2013113 (1981)","journal-title":"SIAM Journal on Computing"},{"key":"1_CR4","doi-asserted-by":"crossref","unstructured":"Berkeland, D.J., Raymondson, D.A., Tassin, V.M.: Tests for non-randomness in quantum jumps, Los Alamos preprint archive (April 2, 2004), http:\/\/arxiv.org\/abs\/physics\/0304013","DOI":"10.1103\/PhysRevA.69.052103"},{"key":"1_CR5","series-title":"Revised and Extended","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04978-5","volume-title":"Information and Randomness. An Algorithmic Perspective","author":"C.S. Calude","year":"2002","unstructured":"Calude, C.S.: Information and Randomness. An Algorithmic Perspective, 2nd edn. Revised and Extended. Springer, Berlin (2002)","edition":"2"},{"key":"1_CR6","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/S0304-3975(01)00068-8","volume":"284","author":"C.S. Calude","year":"2002","unstructured":"Calude, C.S.: Chaitin \u03a9 numbers, Solovay machines and incompleteness. Theoret. Comput. Sci.\u00a0284, 269\u2013277 (2002)","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR7","unstructured":"Calude, C.S., J\u00fcrgensen, H.: Is Complexity a Source of Incompleteness? CDMTCS Research Report,\u00a0241(15) (2004) Los Alamos preprint archive 12 pp (August 11, 2004), http:\/\/arxiv.org\/abs\/math.LO\/0408144"},{"key":"1_CR8","first-page":"199","volume":"62","author":"C. Calude","year":"1997","unstructured":"Calude, C., Hertling, P., Khoussainov, B.: Do the zeros of Riemann\u2019s zeta\u2013function form a random sequence? Bull. Eur. Assoc. Theor. Comput. Sci. EATCS\u00a062, 199\u2013207 (1997)","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci. EATCS"},{"key":"1_CR9","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0096-3003(94)90158-9","volume":"66","author":"C. Calude","year":"1994","unstructured":"Calude, C., J\u00fcrgensen, H., Zimand, M.: Is independence an exception? Appl. Math. Comput.\u00a066, 63\u201376 (1994)","journal-title":"Appl. Math. Comput."},{"issue":"1-2","key":"1_CR10","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1023\/A:1019623616675","volume":"1","author":"C.S. Calude","year":"2002","unstructured":"Calude, C.S., Pavlov, B.: Coins, quantum measurements, and Turing\u2019s barrier. Quantum Information Processing\u00a01(1-2), 107\u2013127 (2002)","journal-title":"Quantum Information Processing"},{"key":"1_CR11","unstructured":"Calude, C.S., Stay, M.A.: From Heinsenberg to G\u00f6del via Chaitin. International Journal of Theoretical Physics, accepted. E-print as CDMTCS Research Report 235, 2004, 15 pp. and Los Alamos preprint archive (February 26, 2004), http:\/\/arXiv:quant-ph\/0402197"},{"key":"1_CR12","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1080\/00207168408803423","volume":"16","author":"C. Calude","year":"1984","unstructured":"Calude, C., Zimand, M.: A relation between correctness and randomness in the computation of probabilistic algorithms. Internat. J. Comput. Math.\u00a016, 47\u201353 (1984)","journal-title":"Internat. J. Comput. Math."},{"key":"1_CR13","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1145\/321892.321894","volume":"22","author":"G.J. Chaitin","year":"1975","unstructured":"Chaitin, G.J.: A theory of program size formally identical to information theory. J. Assoc. Comput. Mach.\u00a022, 329\u2013340 (1975)","journal-title":"J. Assoc. Comput. Mach."},{"key":"1_CR14","doi-asserted-by":"crossref","DOI":"10.1142\/1861","volume-title":"Information\u2013Theoretic Incompleteness","author":"G.J. Chaitin","year":"1992","unstructured":"Chaitin, G.J.: Information\u2013Theoretic Incompleteness. World Scientific, Singapore (1992)"},{"key":"1_CR15","unstructured":"Chaitin, G.J.: Leibniz, Information, Math and Physics, http:\/\/www.cs.auckland.ac.nz\/CDMTCS\/chaitin\/kirchberg.html"},{"key":"1_CR16","volume-title":"META MATH! The Quest for Omega","author":"G.J. Chaitin","year":"2005","unstructured":"Chaitin, G.J.: META MATH! The Quest for Omega. Pantheon Books, New York (2005) (to appear)"},{"key":"1_CR17","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1002\/cpa.3160310407","volume":"31","author":"G.J. Chaitin","year":"1978","unstructured":"Chaitin, G.J., Schwartz, J.T.: A note on Monte-Carlo primality tests and algorithmic information theory. Comm. Pure Appl. Math.\u00a031, 521\u2013527 (1978)","journal-title":"Comm. Pure Appl. Math."},{"issue":"1","key":"1_CR18","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1016\/S0022-0000(05)80084-4","volume":"49","author":"R. Chang","year":"1994","unstructured":"Chang, R., Chor, B., Goldreich, O., Hartmanis, J., Hastad, J., Ranjan, D., Rohatgi, P.: The random oracle hypothesis is false. J. Comput. System Sci.\u00a049(1), 24\u201339 (1994)","journal-title":"J. Comput. System Sci."},{"key":"1_CR19","unstructured":"http:\/\/www.claymath.org\/millennium\/Riemann_Hypothesis\/"},{"key":"1_CR20","unstructured":"Davis, M.: The Universal Computer: The Road from Leibniz to Turing, Norton, New York (2000)"},{"key":"1_CR21","first-page":"195","volume-title":"Alan Turing: Life and Legacy of a Great Thinker","author":"M. Davis","year":"2003","unstructured":"Davis, M.: The myth of hypercomputation. In: Teuscher, C. (ed.) Alan Turing: Life and Legacy of a Great Thinker, pp. 195\u2013211. Springer, Heidelberg (2003)"},{"key":"1_CR22","volume-title":"L\u2019Intelligence and le Calcul, BELIN","author":"J.-P. Delahaye","year":"2002","unstructured":"Delahaye, J.-P.: L\u2019Intelligence and le Calcul, BELIN. Pour la Science, Paris (2002)"},{"key":"1_CR23","volume-title":"Algorithmic Randomness and Complexity","author":"R. Downey","year":"2005","unstructured":"Downey, R., Hirschfeldt, D.: Algorithmic Randomness and Complexity. Springer, Heidelberg (2005) (to appear)"},{"key":"1_CR24","doi-asserted-by":"crossref","unstructured":"Eastlake 3rd, D.E., Crocker, S., Schiller, J.: Randomness Recommendations for Security. RFC 1750, 30 (December 1994)","DOI":"10.17487\/rfc1750"},{"key":"1_CR25","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1023\/A:1014019225365","volume":"41","author":"G. Etesi","year":"2002","unstructured":"Etesi, G., N\u00e9meti, I.: Non-Turing computations via Malament-Hogarth space-times. International Journal of Theoretical Physics\u00a041, 341\u2013370 (2002)","journal-title":"International Journal of Theoretical Physics"},{"key":"1_CR26","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/BF02650179","volume":"21","author":"R.P. Feynman","year":"1982","unstructured":"Feynman, R.P.: Simulating physics with computers. International Journal of Theoretical Physics\u00a021, 467\u2013488 (1982)","journal-title":"International Journal of Theoretical Physics"},{"key":"1_CR27","unstructured":"http:\/\/www.fourmilab.ch\/hotbits\/"},{"key":"1_CR28","first-page":"257","volume-title":"The Monte Carlo Method: The Method Statistical Trials","author":"D.I. Golenko","year":"1966","unstructured":"Golenko, D.I.: Generation of uniformly distributed random variables on electronic computers. In: Shreider, Y.A. (ed.) The Monte Carlo Method: The Method Statistical Trials, pp. 257\u2013305. Pergamon Press, Oxford (1966) (translated from Russian by G. J. Tee)"},{"key":"1_CR29","first-page":"62","volume-title":"Quantum Theory and Measurement","year":"1983","unstructured":"Heisenberg, W.: \u00dcber den Anschaulichen Inhalt der Quantentheoretischen Kinematik und Mechanik. Zeitschrift f\u00fcr Physik\u00a043, 172\u2013198 (1927) English translation In Wheeler, J.A., Zurek, H. (eds.): Quantum Theory and Measurement, pp. 62\u201384. Princeton Univ. Press, Princeton (1983)"},{"key":"1_CR30","unstructured":"http:\/\/www.idquantique.com\/"},{"key":"1_CR31","unstructured":"http:\/\/www.idquantique.com\/img\/QuantisBoth.jpg"},{"key":"1_CR32","doi-asserted-by":"publisher","first-page":"1675","DOI":"10.1063\/1.1150518","volume":"71","author":"T. Jennewein","year":"2000","unstructured":"Jennewein, T., Achleitner, U., Weihs, G., Weinfurter, H., Zeilinger, A.: A fast and compact quantum random number generator. Rev. Sci. Instr.\u00a071, 1675\u20131680 (2000)","journal-title":"Rev. Sci. Instr."},{"key":"1_CR33","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1007\/BF01391200","volume":"44","author":"E.H. Kennard","year":"1927","unstructured":"Kennard, E.H.: Zur Quantenmechanik einfacher Bewegungstypen. Zeitschrift f\u00fcr Physik\u00a044, 326\u2013352 (1927)","journal-title":"Zeitschrift f\u00fcr Physik"},{"issue":"1","key":"1_CR34","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1080\/00107510302712","volume":"44","author":"T.D. Kieu","year":"2003","unstructured":"Kieu, T.D.: Computing the non-computable. Contemporary Physics\u00a044(1), 51\u201371 (2003)","journal-title":"Contemporary Physics"},{"issue":"1","key":"1_CR35","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/S0019-9958(83)80023-0","volume":"57","author":"S.A. Kurtz","year":"1983","unstructured":"Kurtz, S.A.: On the random oracle hypothesis. Information and Control\u00a057(1), 40\u201347 (1983)","journal-title":"Information and Control"},{"key":"1_CR36","unstructured":"Leibniz, G.W.: Discours de m\u00e9taphysique, Gallimard, Paris (1995)"},{"key":"1_CR37","unstructured":"http:\/\/www.mathstat.dal.ca\/~joerg\/pic\/g-letter.jpg"},{"key":"1_CR38","unstructured":"Matiyasevich, Y.V.: Hilbert\u2019s Tenth Problem. MIT Press, Cambridge (1993)"},{"key":"1_CR39","unstructured":"Milburn, G.: The Feynman Processor. An Introduction to Quantum Computation, Allen & Unwin, St. Leonards (1998)"},{"key":"1_CR40","first-page":"36","volume":"12","author":"J. Neumann von","year":"1951","unstructured":"von Neumann, J.: Various techniques used in connection with random digits. National Bureau of Standards Applied Mathematics Series\u00a012, 36\u201338 (1951)","journal-title":"National Bureau of Standards Applied Mathematics Series"},{"key":"1_CR41","doi-asserted-by":"crossref","unstructured":"Oliver, D.: Email to C. Calude, (August 20, 2004)","DOI":"10.1016\/S1361-3723(04)00068-5"},{"key":"1_CR42","unstructured":"http:\/\/www.randomnumbers.info"},{"key":"1_CR43","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1016\/S0022-0000(76)80043-8","volume":"13","author":"G.L. Miller","year":"1976","unstructured":"Miller, G.L.: Riemann\u2019s hypothesis and tests of primality. J. Comput. System Sci.\u00a013, 300\u2013317 (1976)","journal-title":"J. Comput. System Sci."},{"key":"1_CR44","volume-title":"Quantum Theory: Concepts and Methods","author":"A. Peres","year":"1993","unstructured":"Peres, A.: Quantum Theory: Concepts and Methods. Kluwer Academic Publishers, Dordrecht (1993)"},{"key":"1_CR45","doi-asserted-by":"publisher","first-page":"590","DOI":"10.1214\/aos\/1176348543","volume":"20","author":"Y. Peres","year":"1992","unstructured":"Peres, Y.: Iterating von Neumann\u2019s procedure for extracting random bits. Ann. Stat.\u00a020, 590\u2013597 (1992)","journal-title":"Ann. Stat."},{"key":"1_CR46","first-page":"21","volume-title":"Algorithms and Complexity, New Directions and Recent Results","author":"M.O. Rabin","year":"1976","unstructured":"Rabin, M.O.: Probabilistic algorithms. In: Traub, J.F. (ed.) Algorithms and Complexity, New Directions and Recent Results, pp. 21\u201339. Academic Press, New York (1976)"},{"key":"1_CR47","unstructured":"A Million Random Digits with 100,000 Normal Deviates, The RAND Corporation, The Free Press, Glencoe, IL (1955), online edition http:\/\/www.rand.org\/publications\/classics\/randomdigits\/"},{"key":"1_CR48","volume-title":"The Music of the Primes","author":"M. Sautoy du","year":"2003","unstructured":"du Sautoy, M.: The Music of the Primes. HarperCollins, New York (2003)"},{"issue":"10","key":"1_CR49","doi-asserted-by":"publisher","first-page":"2156","DOI":"10.1103\/PhysRevLett.81.2156","volume":"81","author":"S. Sinha","year":"1998","unstructured":"Sinha, S., Ditto, W.L.: Dynamics based computation. Physical Letters Review\u00a081(10), 2156\u20132159 (1998)","journal-title":"Physical Letters Review"},{"issue":"1","key":"1_CR50","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1103\/PhysRevE.60.363","volume":"60","author":"S. Sinha","year":"1999","unstructured":"Sinha, S., Ditto, W.L.: Computing with distributed chaos. Physical Review E\u00a060(1), 363\u2013377 (1999)","journal-title":"Physical Review E"},{"key":"1_CR51","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1007\/978-1-4471-0751-4_21","volume-title":"Finite Versus Infinite. Contributions to an Eternal Dilemma","author":"R.M. Solovay","year":"2000","unstructured":"Solovay, R.M.: A version of \u03a9 for which ZFC can not predict a single bit. In: Calude, C.S., P\u0103un, G. (eds.) Finite Versus Infinite. Contributions to an Eternal Dilemma, pp. 323\u2013334. Springer, London (2000)"},{"key":"1_CR52","doi-asserted-by":"crossref","unstructured":"Svozil, K.: The quantum coin toss-testing microphysical undecidability. Physics Letters\u00a0A143, 433\u2013437","DOI":"10.1016\/0375-9601(90)90408-G"},{"key":"1_CR53","doi-asserted-by":"crossref","DOI":"10.1142\/1524","volume-title":"Randomness & Undecidability in Physics","author":"K. Svozil","year":"1993","unstructured":"Svozil, K.: Randomness & Undecidability in Physics. World Scientific, Singapore (1993)"},{"key":"1_CR54","unstructured":"Tadaki, K.: Upper bound by Kolmogorov complexity for the probability in computable POVM measurement, Los Alamos preprint archive (December 11, 2002), http:\/\/www.arXiv:quantph\/0212071"},{"key":"1_CR55","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1103\/RevModPhys.55.601","volume":"55","author":"S. Wolfram","year":"1983","unstructured":"Wolfram, S.: Statistical mechanics of cellular automata. Reviews of Modern Physics\u00a055, 601\u2013644 (1983)","journal-title":"Reviews of Modern Physics"},{"key":"1_CR56","unstructured":"Wolfram, S.: A New Kind of Science. Wolfram Media, Champaign (2002)"},{"issue":"1","key":"1_CR57","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1002\/1099-0526(200009\/10)6:1<27::AID-CPLX1004>3.0.CO;2-R","volume":"6","author":"U. Yurtsever","year":"2002","unstructured":"Yurtsever, U.: Quantum mechanics and algorithmic randomness. Complexity\u00a06(1), 27\u201331 (2002)","journal-title":"Complexity"}],"container-title":["Lecture Notes in Computer Science","Machines, Computations, and Universality"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-31834-7_1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T23:27:43Z","timestamp":1605742063000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-31834-7_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540252610","9783540318347"],"references-count":57,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-31834-7_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}