{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T06:07:40Z","timestamp":1762322860953,"version":"3.41.0"},"reference-count":94,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2002,11,1]],"date-time":"2002-11-01T00:00:00Z","timestamp":1036108800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2002,11,1]],"date-time":"2002-11-01T00:00:00Z","timestamp":1036108800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Minds and Machines"],"published-print":{"date-parts":[[2002,11]]},"DOI":"10.1023\/a:1021132605507","type":"journal-article","created":{"date-parts":[[2003,3,21]],"date-time":"2003-03-21T00:40:25Z","timestamp":1048207225000},"page":"503-517","source":"Crossref","is-referenced-by-count":7,"title":["Incompleteness, Complexity, Randomness and Beyond"],"prefix":"10.1007","volume":"12","author":[{"given":"Cristian S.","family":"Calude","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"5102098_CR1","volume-title":"Proof.A Play","author":"D. Auburn","year":"2001","unstructured":"Auburn, D. (2001), Proof.A Play, New York: Faber & Faber."},{"key":"5102098_CR2","volume-title":"Impossibility: The Limits of Science and the Science of Limits","author":"J.D. Barrow","year":"1998","unstructured":"Barrow, J.D. (1998), Impossibility: The Limits of Science and the Science of Limits, Oxford: Oxford University Press."},{"key":"5102098_CR3","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1002\/1099-0526(200005\/06)5:5<28::AID-CPLX5>3.0.CO;2-S","volume":"5","author":"J.D. Barrow","year":"2000","unstructured":"Barrow, J.D. (2000), \u2018Mathematical Jujitsu: Some Informal Thoughts About G\u00f6del and Physics\u2019, Complexity 5, pp. 28\u201334.","journal-title":"Complexity"},{"key":"5102098_CR4","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/978-1-4471-0717-0_6","volume-title":"Combinatorics, Computability and Logic, Proceedings of DMTCS'01","author":"V. Becher","year":"2001","unstructured":"Becher, V., Daicz, S. and Chaitin, G.J. (2001), \u2018A Highly Random Number\u2019, in C.S. Calude, M. J. Dinneen and S. Sburlan, eds., Combinatorics, Computability and Logic, Proceedings of DMTCS'01, London: Springer, pp. 55\u201368."},{"key":"5102098_CR5","volume-title":"What is Random? Chance and Order in Mathematics and Life","author":"E. Beltrami","year":"1999","unstructured":"Beltrami, E. (1999), What is Random? Chance and Order in Mathematics and Life, New York: Springer."},{"key":"5102098_CR6","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1038\/scientificamerican1179-20","volume":"241","author":"C.H. Bennett","year":"1979","unstructured":"Bennett, C.H. and Gardner, M. (1979), \u2018The Random Number Omega Bids Fair to Hold the Mysteries of the Universe\u2019, Scientific American 241, pp. 20\u201334.","journal-title":"Scientific American"},{"key":"5102098_CR7","volume-title":"Puissance et Limites de la Raison","author":"L. Brisson","year":"1995","unstructured":"Brisson, L. and Meyerstein, L.F. (1995), Puissance et Limites de la Raison, Paris: Les Belles Lettres."},{"key":"5102098_CR8","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. (2002), Information and Randomness.An Algorithmic Perspective, Berlin: Springer."},{"key":"5102098_CR9","series-title":"CSLI Series","first-page":"65","volume-title":"Logic, Language and Computation","author":"C.S. Calude","year":"2000","unstructured":"Calude, C.S. (2000), \u2018A Glimpse into Algorithmic Information Theory\u2019, in P. Blackburn, N. Braisby, L. Cavedon and A. Shimojima, eds., Logic, Language and Computation, Volume 3, CSLI Series, Cambridge: Cambridge University Press, pp. 65\u201381."},{"key":"5102098_CR10","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1016\/S0304-3975(01)00068-8","volume":"28","author":"C.S. Calude","year":"2002","unstructured":"Calude, C.S. (2002), \u2018Chaitin \u03a9 \u03a9Numbers, SolovayMachines and Incompleteness\u2019, Theoret.Comput.Sci. 28, pp. 269\u2013277.","journal-title":"Theoret. Comput. Sci."},{"key":"5102098_CR11","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1038\/22435","volume":"400","author":"C.S. Calude","year":"1999","unstructured":"Calude, C.S. and Chaitin, G.J. (1999), \u2018Randomness Everywhere\u2019, Nature 400, pp. 319\u2013320.","journal-title":"Nature"},{"key":"#cr-split#-5102098_CR12.1","doi-asserted-by":"crossref","unstructured":"Calude, C.S., Dinneen, M.J. and C.-K. Shu, C.-K. (2002), 'Computing a Glimpse of Randomness', Experimental Mathematics","DOI":"10.1080\/10586458.2002.10504481"},{"key":"#cr-split#-5102098_CR12.2","doi-asserted-by":"crossref","unstructured":"see also CDMTCS Research Report 167, 2001, 12 pp.","DOI":"10.1080\/09571260120095094"},{"key":"5102098_CR13","unstructured":"Calude, C.S., Dinneen, M.J. and Svozil, K. (1999), \u2018Counterfactual Effect, the Halting Problem, and the Busy Beaver Function\u2019 (Preliminary Version), CDMTCS Research Report 107, 8 pp."},{"key":"5102098_CR14","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1002\/1099-0526(200009\/10)6:1<35::AID-CPLX1005>3.0.CO;2-T","volume":"6","author":"C.S. Calude","year":"2000","unstructured":"Calude, C.S., Dinneen, M.J. and Svozil, K. (2000), \u2018Reflections on Quantum Computing\u2019, Complexity 6, pp. 35\u201337.","journal-title":"Complexity"},{"key":"5102098_CR15","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/S0304-3975(99)00159-0","volume":"255","author":"C.S. Calude","year":"2001","unstructured":"Calude, C.S., Hertling, P., Khoussainov, B. and Wang, Y. (2001), 'Recursively Enumerable Reals and Chaitin \u03a9 \u03a9Numbers\u2019, Theoret.Comput.Sci. 255 pp. 125\u2013149.","journal-title":"Theoret. Comput. Sci."},{"key":"5102098_CR16","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1007\/3-540-58131-6_37","volume-title":"Results and Trends in Theoretical Computer Science","author":"C. Calude","year":"1994","unstructured":"Calude, C. and J\u00fcrgensen, H. (1994), \u2018Randomness as an Invariant for Number Representations\u2019, in H. Maurer, J. Karhum\u00e4ki and G. Rozenberg, eds. Results and Trends in Theoretical Computer Science, Berlin: Springer, pp. 44\u201366."},{"key":"5102098_CR17","first-page":"63","volume":"66","author":"C. Calude","year":"1994","unstructured":"Calude, C., J\u00fcrgensen, H. and Zimand, M. (1994), \u2018Is Independence an Exception ?\u2019, Appl.Math.Comput. 66, pp. 63\u201376.","journal-title":"Appl. Math. Comput."},{"key":"5102098_CR18","doi-asserted-by":"crossref","first-page":"1075","DOI":"10.1016\/S0960-0779(98)00145-3","volume":"10","author":"C.S. Calude","year":"1999","unstructured":"Calude, C.S. and Meyerstein, F.W. (1999), \u2018Is the Universe Lawful ?\u2019, Chaos, Solitons & Fractals 10, pp. 1075\u20131084.","journal-title":"Chaos, Solitons & Fractals"},{"key":"5102098_CR19","first-page":"1161","volume":"3","author":"C. Calude","year":"1997","unstructured":"Calude, C. and Nies, A. (1997), \u2018Chaitin \u03a9 \u03a9Numbers and Strong Reducibilities\u2019, J.Univ.Comput.Sci. 3, pp. 1161\u20131166.","journal-title":"J. Univ. Comput. Sci."},{"issue":"1-2","key":"5102098_CR20","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1023\/A:1019623616675","volume":"1","author":"C.S. Calude","year":"2002","unstructured":"Calude, C.S. and Pavlov, B. (2002), \u2018Coins, QuantumMeasurements, and Turing's Barrier\u2019, Quantum Information Processing 1(1-2), pp. 107\u2013127.","journal-title":"Quantum Information Processing"},{"key":"5102098_CR21","volume-title":"Computing with Cells and Atoms","author":"C.S. Calude","year":"2001","unstructured":"Calude, C.S. and P\u0103un, G. (2001), Computing with Cells and Atoms, London: Taylor & Francis Publishers."},{"key":"5102098_CR22","first-page":"472","volume-title":"Developments in Language Theory","author":"C. Calude","year":"1994","unstructured":"Calude, C. and Salomaa, A. (1994), \u2018Algorithmically Coding the Universe\u2019, in G. Rozenberg and A. Salomaa, eds. Developments in Language Theory, Singapore: World Scientific, pp. 472\u2013492."},{"key":"5102098_CR23","first-page":"34","volume":"154\/2082","author":"J. Casti","year":"1997","unstructured":"Casti, J. (1997), \u2018Computing the Uncomputable\u2019, The New Scientist, 154\/2082, p. 34.","journal-title":"The New Scientist"},{"key":"5102098_CR24","volume-title":"Five More Golden Rules: Knots, Codes, Chaos, and Other Great Theories of 20th-Century Mathematics","author":"J. Casti","year":"2000","unstructured":"Casti, J. (2000), Five More Golden Rules: Knots, Codes, Chaos, and Other Great Theories of 20th-Century Mathematics, New York: Wiley."},{"key":"5102098_CR25","volume-title":"G\u00f6del.A Life in Logic","author":"J. Casti","year":"2000","unstructured":"Casti, J. and DePauli, W. (2000), G\u00f6del.A Life in Logic, Cambridge: Perseus."},{"key":"5102098_CR26","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1145\/321356.321363","volume":"13","author":"G.J. Chaitin","year":"1966","unstructured":"Chaitin, G.J. (1966), \u2018On the Length of Programs for Computing Finite Binary Sequences\u2019, J.Assoc.Comput.Mach. 13, pp. 547\u2013569. (Reprinted in: Chaitin (1990), pp. 219\u2013244.)","journal-title":"J. Assoc. Comput. Mach."},{"key":"5102098_CR27","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1145\/321892.321894","volume":"22","author":"G.J. Chaitin","year":"1975","unstructured":"Chaitin, G.J. (1975), \u2018A Theory of Program Size Formally Identical to Information Theory\u2019, J.Assoc.Comput.Mach. 22, pp. 329\u2013340. (Reprinted in: Chaitin (1990), pp. 113\u2013128)","journal-title":"J. Assoc. Comput. Mach."},{"key":"5102098_CR28","doi-asserted-by":"crossref","first-page":"941","DOI":"10.1007\/BF02084159","volume":"22","author":"G.J. Chaitin","year":"1982","unstructured":"Chaitin, G.J. (1982), \u2018G\u00f6del's Theorem & Information\u2019, International Journal of Theoretical Physics 22, pp. 941\u2013954.","journal-title":"International Journal of Theoretical Physics"},{"key":"5102098_CR29","volume-title":"Algorithmic Information Theory","author":"G.J. Chaitin","year":"1990","unstructured":"Chaitin, G.J. (1990), Algorithmic Information Theory, Cambridge: Cambridge University Press (Third printing)."},{"key":"5102098_CR30","doi-asserted-by":"crossref","DOI":"10.1142\/1048","volume-title":"Information, Randomness and Incompleteness, Papers on Algorithmic Information Theory","author":"G.J. Chaitin","year":"1990","unstructured":"Chaitin, G.J. (1990), Information, Randomness and Incompleteness, Papers on Algorithmic Information Theory, Singapore: World Scientific, Singapore (Second edition).","edition":"Second edition"},{"key":"5102098_CR31","doi-asserted-by":"crossref","DOI":"10.1142\/1861","volume-title":"Information-Theoretic Incompleteness","author":"G.J. Chaitin","year":"1992","unstructured":"Chaitin, G.J. (1992), Information-Theoretic Incompleteness, Singapore: World Scientific, Singapore."},{"key":"5102098_CR32","volume-title":"The Limits of Mathematics","author":"G.J. Chaitin","year":"1997","unstructured":"Chaitin, G.J. (1997), The Limits of Mathematics, Singapore: Springer."},{"key":"5102098_CR33","volume-title":"The Unknowable","author":"G.J. Chaitin","year":"1999","unstructured":"Chaitin, G.J. (1999), The Unknowable, Singapore: Springer."},{"key":"5102098_CR34","volume-title":"Exploring Randomness","author":"G.J. Chaitin","year":"2000","unstructured":"Chaitin, G.J. (2000), Exploring Randomness, London: Springer."},{"key":"5102098_CR35","volume-title":"Conversations with a Mathematician","author":"G.J. Chaitin","year":"2001","unstructured":"Chaitin, G.J. (2001), Conversations with a Mathematician, London: Springer."},{"key":"5102098_CR36","unstructured":"Chown, M. (2001), \u2018The Omega Man\u2019, New Scientist 10 March, pp. 29\u201331."},{"key":"5102098_CR37","unstructured":"Chown, M. (2002), \u2018Smash and Grab\u2019, New Scientist 6 April, pp. 24\u201328."},{"key":"5102098_CR38","unstructured":"Collins, G. P. (2001), \u2018Computing with Light\u2019, Scientific American, Aug. p. 12."},{"key":"5102098_CR39","unstructured":"Copeland, J. (1999), \u2018The Modern History of Computing\u2019, in E.N. Zalta, ed. The Stanford Encyclopedia of Philosophy http:\/\/plato.stanford.edu\/entries\/ computing-history\/."},{"issue":"1","key":"5102098_CR40","first-page":"5","volume":"XCVI","author":"J. Copeland","year":"2000","unstructured":"Copeland, J. (2000), \u2018Narrow Versus Wide Mechanism: Including a Re-examination of Turing's Views on the Mind-machine Issue\u2019, Journal of Philosophy XCVI1, pp. 5\u201332.","journal-title":"Journal of Philosophy"},{"key":"5102098_CR41","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1007\/BF03026730","volume":"6","author":"J.W. Dawson Jr.","year":"1984","unstructured":"Dawson, J.W. Jr. (1984), \u2018Kurt G\u00f6del in Sharper Focus\u2019, The Mathematical Intelligencer6, pp. 9\u201317.","journal-title":"The Mathematical Intelligencer"},{"key":"5102098_CR42","volume-title":"Logical Dilemmas.The Life and Work of Kurt G\u00f6del","author":"J.W. Dawson Jr.","year":"1997","unstructured":"Dawson, J.W. Jr. (1997), Logical Dilemmas.The Life and Work of Kurt G\u00f6del, Massachusetts: A K Peters."},{"key":"5102098_CR43","first-page":"56","volume-title":"Routledge Encyclopedia of Philosophy","author":"W. A. Dembski","year":"1998","unstructured":"Dembski, W. A. (1998), \u2018Randomness\u2019, in E. Craig, ed., Routledge Encyclopedia of Philosophy, Routledge, London, Vol. 8, pp. 56\u201359."},{"key":"5102098_CR44","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-2028-2","volume-title":"Introductory Statistics and Random Phenomena: Uncertainty, Complexity, and Chaotic Behavior in Engineering and Science","author":"M. Denker","year":"1998","unstructured":"Denker, M., Woyczy\u0144ski, M. W. and Ycart, B. (1998), Introductory Statistics and Random Phenomena: Uncertainty, Complexity, and Chaotic Behavior in Engineering and Science, Boston: Birkh\u00e4user."},{"key":"5102098_CR45","first-page":"106","volume-title":"Routledge Encyclopedia of Philosophy","author":"M. Detlefsen","year":"1998","unstructured":"Detlefsen, M. (1998), \u2018G\u00f6del's Theorems\u2019, in E. Craig, ed., Routledge Encyclopedia of Philosophy, Routledge, London, Vol. 4, pp. 106\u2013119."},{"key":"5102098_CR46","first-page":"97","volume":"400","author":"D. Deutsch","year":"1985","unstructured":"Deutsch, D. (1985), \u2018Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer\u2019, Proceedings of the Royal Society London A 400, pp. 97\u2013119.","journal-title":"Proceedings of the Royal Society London A"},{"key":"5102098_CR47","volume-title":"Uncle Petros & Goldback's Conjecture.A Novel about Mathematical Obsession","author":"A. Doxiadis","year":"2000","unstructured":"Doxiadis, A. (2000), Uncle Petros & Goldback's Conjecture.A Novel about Mathematical Obsession, New York: Bloomsbury."},{"key":"5102098_CR48","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1023\/A:1014019225365","volume":"41","author":"G. Etesi","year":"2002","unstructured":"Etesi, G. and N\u00e9meti, I. (2002)., \u2018Non-Turing Computations via Malament-Hogarth Space-times\u2019, International Journal of Theoretical Physics 41, pp. 341\u2013370.","journal-title":"International Journal of Theoretical Physics"},{"key":"5102098_CR49","first-page":"546","volume":"21","author":"S. Feferman","year":"1984","unstructured":"Feferman, S. (1984), \u2018Kurt G\u00f6del: Conviction and Caution\u2019, Philos.Natur. 21, pp. 546\u2013562.","journal-title":"Philos. Natur."},{"volume-title":"Kurt G\u00f6del Collected Works","year":"1990","key":"5102098_CR50","unstructured":"Feferman, S., Dawson, J., Jr., Kleene S.C., Moore, G.H., Solovay, R.M. and van Heijenoort, J., eds. (1990), Kurt G\u00f6del Collected Works, Volume II, Oxford: Oxford University Press."},{"key":"5102098_CR51","first-page":"11","volume":"11","author":"R.P. Feynman","year":"1985","unstructured":"Feynman, R.P. (1985), \u2018Simulating Physics with Computers\u2019, International Journal of Theoretical Physics 11, pp. 11\u201320.","journal-title":"International Journal of Theoretical Physics"},{"key":"5102098_CR52","unstructured":"Hey, J.G., ed. (1999), Feynman and Computation.Exploring the Limits of Computers, Reading: Perseus Books."},{"key":"5102098_CR53","first-page":"211","volume-title":"Philosophy of Mathematics","author":"K. G\u00f6del","year":"1964","unstructured":"G\u00f6del, K. (1964), \u2018Russell's Mathematical Logic\u2019, in P. Benacerref and H. Putnam, eds. Philosophy of Mathematics, Englewood Cliffs, NJ: Prentice-Hall, pp. 211\u2013232."},{"key":"5102098_CR54","volume-title":"Quantum Computing","author":"J. Gruska","year":"1999","unstructured":"Gruska, J. (1999), Quantum Computing, London: McGraw-Hill."},{"key":"5102098_CR55","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1511\/2001.28.300","volume":"89","author":"B. Hayes","year":"2001","unstructured":"Hayes, B. (2001), \u2018Randomness as a Resource\u2019, American Scientist 89, 4 July\u2013August, pp. 300-304.","journal-title":"American Scientist"},{"key":"5102098_CR56","first-page":"796","volume-title":"Automata, Languages and Programming, Proceedings of the 25th International Colloquium, ICALP'98 (Aalborg, Denmark)","author":"P. Hertling","year":"1998","unstructured":"Hertling, P. and Weihrauch, K. (1998), \u2018Randomness Spaces\u2019, in K.G. Larsen, S. Skyum, and G. Winskel, eds. Automata, Languages and Programming, Proceedings of the 25th International Colloquium, ICALP'98 (Aalborg, Denmark), Berlin: Springer, pp. 796\u2013807."},{"key":"5102098_CR57","first-page":"405","volume":"71","author":"M. Kac","year":"1983","unstructured":"Kac, M. (1983), \u2018What is Random ?\u2019, American Scientist 71, pp. 405\u2013406.","journal-title":"American Scientist"},{"key":"5102098_CR58","unstructured":"Kieu, T.D. (2001a), \u2018Hilbert's Incompleteness, Chaitin's \u03a9\u03a9 Number and Quantum Physics\u2019, Los Alamos preprint archive http:\/\/arXiv:quant-ph\/0111062, v1, 10 November."},{"key":"5102098_CR59","unstructured":"Kieu, T. D. (2001b), \u2018Quantum Algorithm for the Hilbert's Tenth Problem\u2019, Los Alamos preprint archive http:\/\/arXiv:quant-ph\/0110136, v2, 9 November."},{"key":"5102098_CR60","doi-asserted-by":"crossref","first-page":"761","DOI":"10.2307\/2272394","volume":"41","author":"S.C. Kleene","year":"1976","unstructured":"Kleene, S.C. (1976), \u2018The Work of Kurt G\u00f6del\u2019, J.Symbolic Logic 41, pp, 761\u2013778; addendum J.Symbolic Logic 43, p. 613.","journal-title":"J. Symbolic Logic"},{"key":"5102098_CR61","doi-asserted-by":"crossref","first-page":"1068","DOI":"10.1126\/science.231.4742.1068","volume":"7","author":"G. Kolata","year":"1986","unstructured":"Kolata, G. (1986), \u2018What Does it Mean to be Random ?\u2019, Science 7, pp. 1068\u20131070.","journal-title":"Science"},{"key":"5102098_CR62","first-page":"3","volume":"1","author":"A. N. Kolmogorov","year":"1965","unstructured":"Kolmogorov, A. N. (1965), \u2018Three Approaches for Defining the Concept of \u201cInformation Quantity\u201d\u2019, Problems Inform.Transmission 1, pp. 3\u201311.","journal-title":"Problems Inform. Transmission"},{"key":"5102098_CR63","first-page":"149","volume":"26","author":"G. Kreisel","year":"1980","unstructured":"Kreisel, G. (1980), \u2018Kurt G\u00f6del\u2019, Biographical Memoirs of Fellows of the Royal Society of London 26, pp. 149\u2013224; corrigenda 27, p. 697, 28, p. 718.","journal-title":"Biographical Memoirs of Fellows of the Royal Society of London"},{"key":"5102098_CR64","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1137\/S0097539799357441","volume":"31","author":"A. Ku\u010dera","year":"2001","unstructured":"Ku\u010dera, A. and Slaman, T.A. (2001), \u2018Randomness and Recursive Enumerability\u2019, SIAM J.Comput. 31, pp. 199\u2013211.","journal-title":"SIAM J. Comput."},{"key":"5102098_CR65","doi-asserted-by":"crossref","first-page":"1389","DOI":"10.2307\/2274821","volume":"54","author":"M. van Lambalgen","year":"1989","unstructured":"van Lambalgen, M. (1989), \u2018Algorithmic Information Theory\u2019, J.Symbolic Logic 54, pp. 1389\u20131400.","journal-title":"J. Symbolic Logic"},{"key":"5102098_CR66","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1088\/0031-8949\/35\/1\/021","volume":"35","author":"R. Landauer","year":"1987","unstructured":"Landauer, R. (1987), \u2018Computation: A Fundamental Physical View\u2019, Physica Scripta 35, pp. 88\u201395.","journal-title":"Physica Scripta"},{"key":"5102098_CR67","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2606-0","volume-title":"An Introduction to Kolmogorov Complexity and Its Applications","author":"M. Li","year":"1997","unstructured":"Li, M. and Vit\u00e1nyi, P. M. (1997), An Introduction to Kolmogorov Complexity and Its Applications, Berlin: Springer (Second edition).","edition":"Second edition"},{"key":"5102098_CR68","volume-title":"Algorithms and Random Sequences","author":"P. Martin-L\u00f6f","year":"1966","unstructured":"Martin-L\u00f6f, P. (1966), Algorithms and Random Sequences, N\u00fcrnberg: Erlangen University."},{"key":"5102098_CR69","doi-asserted-by":"crossref","first-page":"602","DOI":"10.1016\/S0019-9958(66)80018-9","volume":"9","author":"P. Martin-L\u00f6f","year":"1966","unstructured":"Martin-L\u00f6f, P. (1966), \u2018The Definition of Random Sequences\u2019, Inform.and Control 9, pp. 602\u2013619.","journal-title":"Inform. and Control"},{"key":"5102098_CR70","first-page":"247","volume":"40","author":"H. Marxen","year":"1990","unstructured":"Marxen, H. and Buntrock, J. (1990), \u2018Attaching the Busy Beaver 5\u2019, Bull EATCS 40, pp. 247\u2013251.","journal-title":"Bull EATCS"},{"key":"5102098_CR71","volume-title":"G\u00f6del's Proof","author":"E. Nagel","year":"1986","unstructured":"Nagel, E. and Newman, J. R. (1986), G\u00f6del's Proof, New York: University Press (Second printing)."},{"key":"5102098_CR72","first-page":"340","volume-title":"The Undecidable","author":"E. Post","year":"1965","unstructured":"Post, E. ( 1965), \u2018Absolutely Unsolvable Problems and Relatively Undecidable Propositions: Account of an Anticipation\u2019, in M. Davis, ed., The Undecidable, New York: Raven Press, pp. 340\u2013433."},{"key":"5102098_CR73","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1023\/A:1004305315546","volume":"27","author":"P. Raatikainen","year":"1998","unstructured":"Raatikainen, P. (1998), \u2018On Interpreting Chaitin's Incompleteness Theorem\u2019, J.Philos.Logic 27, pp. 569\u2013586.","journal-title":"J. Philos. Logic"},{"key":"5102098_CR74","doi-asserted-by":"crossref","first-page":"784","DOI":"10.1090\/S0002-9939-1954-0063328-5","volume":"5","author":"H. Rice","year":"1954","unstructured":"Rice, H. (1954), \u2018Recursive Reals\u2019, Proc.Amer.Math.Soc. 5, pp. 784\u2013791.","journal-title":"Proc. Amer. Math. Soc."},{"key":"5102098_CR75","volume-title":"Cornerstones of Undecidability","author":"G. Rozenberg","year":"1994","unstructured":"Rozenberg, G. and Salomaa, A. (1994), Cornerstones of Undecidability, Englewood Cliffs, NJ: Prentice Hall."},{"key":"5102098_CR76","volume-title":"Infinity and the Mind","author":"R. Rucker","year":"1982","unstructured":"Rucker, R. (1982), Infinity and the Mind, New York: Bantam."},{"key":"5102098_CR77","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1126\/science.268.5210.545","volume":"268","author":"H. Siegelmann","year":"1995","unstructured":"Siegelmann, H. (1995), \u2018Computation Beyond the Turing Limit\u2019, Science 268, pp. 545\u2013548.","journal-title":"Science"},{"key":"5102098_CR78","first-page":"271","volume":"140","author":"R. I. Soare","year":"1969","unstructured":"Soare, R. I. (1969), \u2018Recursion Theory and Dedekind Cuts\u2019, Trans.Amer.Math.Soc. 140, pp. 271\u2013294.","journal-title":"Trans. Amer. Math. Soc."},{"key":"5102098_CR79","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0019-9958(64)90223-2","volume":"7","author":"R. J. Solomonoff","year":"1964","unstructured":"Solomonoff, R. J. (1964), \u2018A Formal Theory of Inductive Inference\u2019, Part 1 and Part 2, Inform.and Control 7, pp. 1\u201322, 224\u2013254.","journal-title":"Inform. and Control"},{"key":"5102098_CR80","volume-title":"Draft of a paper (or series of papers) on Chaitin's work...done for the most part during the period of Sept.\u2013Dec.1974","author":"R. M. Solovay","year":"1975","unstructured":"Solovay, R. M. (1975), Draft of a paper (or series of papers) on Chaitin's work...done for the most part during the period of Sept.\u2013Dec.1974, New York: IBM Thomas J. Watson Research Center, 215, pp."},{"key":"5102098_CR81","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. (2000), \u2018A Version of \u03a9 for Which Z F C Cannot Predict a Single Bit\u2019, in C.S. Calude and G. P\u0103aun, eds., Finite Versus Infinite.Contributions to an Eternal Dilemma, London: Springer, pp. 323\u2013334."},{"key":"5102098_CR82","doi-asserted-by":"crossref","first-page":"145","DOI":"10.2307\/2267043","volume":"14","author":"E. Specker","year":"1949","unstructured":"Specker, E. (1949), Nicht konstruktiv beweisbare 's\u00e4tze der Analysis\u2019, J.Symbolic Logic 14, pp. 145\u2013158.","journal-title":"J. Symbolic Logic"},{"key":"5102098_CR83","doi-asserted-by":"crossref","DOI":"10.1142\/1524","volume-title":"Randomness & Undecidability in Physics","author":"K. Svozil","year":"1993","unstructured":"Svozil, K. (1993), Randomness & Undecidability in Physics, Singapore: World Scientific."},{"key":"5102098_CR84","first-page":"201","volume":"1","author":"K. Svozil","year":"1995","unstructured":"Svozil, K. (1995), \u2018Halting Probability Amplitude of Quantum Computers\u2019, J.UCS 1, pp. 201\u2013203.","journal-title":"J. UCS"},{"key":"5102098_CR85","series-title":"Lecture Notes in Comput. Sci.","doi-asserted-by":"crossref","first-page":"536","DOI":"10.1007\/3-540-48321-7_45","volume-title":"Proc.Fundamentals of Computation Theory","author":"L. Staiger","year":"1999","unstructured":"Staiger, L. (1999), \u2018The Kolmogorov Complexity of Real Numbers\u2019, in G. Ciobanu and Gh. P\u0103un, eds. Proc.Fundamentals of Computation Theory, Lecture Notes in Comput. Sci. No. 1684, Berlin: Springer, pp. 536-546."},{"key":"5102098_CR86","doi-asserted-by":"crossref","first-page":"664","DOI":"10.1038\/352664a0","volume":"352","author":"I. Stewart","year":"1991","unstructured":"Stewart, I. (1991), \u2018Deciding the Undecidable\u2019, Nature 352, pp. 664\u2013665.","journal-title":"Nature"},{"key":"5102098_CR87","first-page":"230","volume":"42","author":"A. M. Turing","year":"1936","unstructured":"Turing, A. M. (1936\/7), \u2018On Computable Numbers with an Application to the Entscheidungsproblem\u2019, Proc.Amer.Math.Soc. 42, pp. 230\u2013265; a correction, 43, pp. 544\u2013546.","journal-title":"Proc. Amer. Math. Soc."},{"key":"5102098_CR88","volume-title":"Les Limites de la Connaissance","author":"H. Zwirn","year":"2000","unstructured":"Zwirn, H. (2000), Les Limites de la Connaissance, Paris: Odile Jacob."},{"key":"5102098_CR89","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1070\/RM1990v045n01ABEH002321","volume":"45","author":"V.A. Uspensky","year":"1990","unstructured":"Uspensky, V.A., Semenov, A. L. and Shen, A. Kh. (1990), \u2018Can an Individual Sequence of Zeros and Ones be Random ?\u2019, Russian Math.Surveys 45, pp. 121\u2013189.","journal-title":"Russian Math. Surveys"},{"key":"5102098_CR90","doi-asserted-by":"crossref","first-page":"2464","DOI":"10.1109\/18.945258","volume":"47","author":"P.M. Vit\u00e1nyi","year":"2001","unstructured":"Vit\u00e1nyi, P.M. (2001), \u2018Quantum Kolmogorov Complexity Based on Classical Descriptions\u2019, IEEE Trans.Inform.Theory 47, pp. 2464\u20132479.","journal-title":"IEEE Trans. Inform. Theory"},{"key":"5102098_CR91","volume-title":"A Logical Journey: From G\u00f6del to Philosophy","author":"H. Wang","year":"1996","unstructured":"Wang, H. (1996), A Logical Journey: From G\u00f6del to Philosophy, Cambridge: MIT Press."},{"key":"5102098_CR92","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0495-4","volume-title":"Ultimate Zero and One","author":"C. P. Williams","year":"2000","unstructured":"Williams, C. P. and Clearwater, S. H. (2000), Ultimate Zero and One, New York: Copernicus."},{"key":"5102098_CR93","first-page":"421","volume-title":"Philosophy of Mathematics: Selected Readings","author":"L. Wittgenstein","year":"1964","unstructured":"Wittgenstein, L. (1964), \u2018Selections from \u201cRemarks on the Foundations of Mathematics\u201d\u2019, in P. Benacerref and H. Putnam (eds). Philosophy of Mathematics: Selected Readings, Princeton, NJ: Prentice-Hall, pp. 421\u2013480."}],"container-title":["Minds and Machines"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1021132605507.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1021132605507\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1021132605507.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,22]],"date-time":"2025-05-22T05:33:56Z","timestamp":1747892036000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1021132605507"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,11]]},"references-count":94,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2002,11]]}},"alternative-id":["5102098"],"URL":"https:\/\/doi.org\/10.1023\/a:1021132605507","relation":{},"ISSN":["0924-6495","1572-8641"],"issn-type":[{"type":"print","value":"0924-6495"},{"type":"electronic","value":"1572-8641"}],"subject":[],"published":{"date-parts":[[2002,11]]}}}