{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T02:39:24Z","timestamp":1777516764538,"version":"3.51.4"},"reference-count":31,"publisher":"SAGE Publications","issue":"2-3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["COM"],"published-print":{"date-parts":[[2018,6,7]]},"DOI":"10.3233\/com-170073","type":"journal-article","created":{"date-parts":[[2017,5,16]],"date-time":"2017-05-16T12:55:20Z","timestamp":1494939320000},"page":"259-271","source":"Crossref","is-referenced-by-count":7,"title":["A probabilistic anytime algorithm for the halting problem"],"prefix":"10.1177","volume":"7","author":[{"given":"Cristian S.","family":"Calude","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Auckland, Auckland, New Zealand. cristian@cs.auckland.ac.nz."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Monica","family":"Dumitrescu","sequence":"additional","affiliation":[{"name":"Faculty of Mathematics and Computer Science, Bucharest University, Romania. mdumi@fmi.unibuc.ro."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","reference":[{"key":"10.3233\/COM-170073_ref1","doi-asserted-by":"crossref","unstructured":"B.C. Arnold, N. Balakrishnan and N.N. Nagaraja, A First Course in Order Statistics, John Wiley, New York, 2008.","DOI":"10.1137\/1.9780898719062"},{"key":"10.3233\/COM-170073_ref2","unstructured":"L. Bienvenu, D. Desfontaines and A. Shen, What percentage of programs halt?, in: Automata, Languages, and Programming I, M.M. Halld\u00f3rsson, K. Iwama, N. Kobayashi and B. Speckmann, eds, LNCS, Vol. 9134, Springer, 2015, pp. 219\u2013230."},{"key":"10.3233\/COM-170073_ref3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-016-0205-0","article-title":"Efficient sampling methods for discrete distributions","author":"Bringmann","year":"2016","journal-title":"Algorithmica"},{"key":"10.3233\/COM-170073_ref4","unstructured":"C.S. Calude, Information and Randomness: An Algorithmic Perspective, 2nd edn, Springer, Berlin, 2002."},{"issue":"1\u20132","key":"10.3233\/COM-170073_ref5","doi-asserted-by":"crossref","first-page":"77","DOI":"10.3233\/FI-2015-1199","article-title":"Universality and almost decidability","volume":"138","author":"Calude","year":"2015","journal-title":"Fundamenta Informaticae"},{"issue":"4","key":"10.3233\/COM-170073_ref6","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1142\/S0129054115500252","article-title":"Anytime algorithms for non-ending computations","volume":"26","author":"Calude","year":"2015","journal-title":"International Journal of Foundations of Computer Science"},{"key":"10.3233\/COM-170073_ref7","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/j.aam.2007.01.001","article-title":"Most programs stop quickly or never halt","volume":"40","author":"Calude","year":"2008","journal-title":"Advances in Applied Mathematics"},{"key":"10.3233\/COM-170073_ref8","unstructured":"W.J. Conover, Practical Nonparametric Statistics, John Wiley, New York, 1971."},{"issue":"5","key":"10.3233\/COM-170073_ref9","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1145\/1941487.1941509","article-title":"Proving program termination","volume":"54","author":"Cook","year":"2011","journal-title":"Communications ACM"},{"key":"10.3233\/COM-170073_ref10","doi-asserted-by":"crossref","unstructured":"A. DasGupta, Probability for Statistics and Machine Learning, Springer, New York, 2011.","DOI":"10.1007\/978-1-4419-9634-3"},{"key":"10.3233\/COM-170073_ref11","doi-asserted-by":"crossref","unstructured":"R. Downey and D. Hirschfeldt, Algorithmic Randomness and Complexity, Springer, Heidelberg, 2010.","DOI":"10.1007\/978-0-387-68441-3"},{"key":"10.3233\/COM-170073_ref12","doi-asserted-by":"crossref","unstructured":"C.A. Furia, D. Mandrioli, A. Morzenti and M. Rossi, Modeling Time in Computing, Springer, Berlin, 2012.","DOI":"10.1007\/978-3-642-32332-4"},{"issue":"1","key":"10.3233\/COM-170073_ref13","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1145\/332148.332154","article-title":"Reasoning about computational resource allocation. An introduction to anytime algorithms","volume":"3","author":"Grass","year":"1996","journal-title":"Magazine Crossroads"},{"issue":"4","key":"10.3233\/COM-170073_ref14","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1305\/ndjfl\/1168352664","article-title":"The halting problem is decidable on a set of asymptotic probability one","volume":"47","author":"Hamkins","year":"2006","journal-title":"Notre Dame Journal of Formal Logic"},{"key":"10.3233\/COM-170073_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/11537311_40"},{"key":"10.3233\/COM-170073_ref16","unstructured":"R.H. Lathrop, On the learnability of the uncomputable, in: Proceedings International Conference on Machine Learning, L. Saitta, ed., Morgan Kaufmann, 1996, pp. 302\u2013309."},{"key":"10.3233\/COM-170073_ref17","unstructured":"P.S. Levy and S. Lemeshow, Sampling of Populations. Methods and Applications, 3rd edn, John Wiley, NJ, 1999."},{"key":"10.3233\/COM-170073_ref18","doi-asserted-by":"crossref","unstructured":"M. Li and P.M.B. Vit\u00e1nyi, An Introduction to Kolmogorov Complexity and Its Applications, 3rd edn, Springer Verlag, New York, 2008.","DOI":"10.1007\/978-0-387-49820-1"},{"key":"10.3233\/COM-170073_ref19","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/S0022-0000(74)80003-6","article-title":"Approximations to the halting problem","volume":"9","author":"Lynch","year":"1974","journal-title":"Journal of Computer and System Sciences"},{"key":"10.3233\/COM-170073_ref20","doi-asserted-by":"crossref","unstructured":"Y.I. Manin, A Course in Mathematical Logic for Mathematicians, 2nd edn, Springer, Berlin, 2010.","DOI":"10.1007\/978-1-4419-0615-1"},{"key":"10.3233\/COM-170073_ref21","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1017\/S0960129511000508","article-title":"Renormalisation and computation II: Time cut-off and the halting problem","volume":"22","author":"Manin","year":"2012","journal-title":"Mathematical Structures in Computer Science"},{"issue":"2","key":"10.3233\/COM-170073_ref22","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/s10688-014-0052-1","article-title":"Zipf\u2019s law and L. Levin probability distributions","volume":"48","author":"Manin","year":"2014","journal-title":"Functional Analysis and Its Applications"},{"key":"10.3233\/COM-170073_ref23","unstructured":"M. Minsky, Computation: Finite and Infinite Machines, Prentice-Hall, Inc., Englewood Cliffs, NJ, 1967."},{"key":"10.3233\/COM-170073_ref24","unstructured":"T. Mori, Y. Tsujii and M. Yasugi, Computability of probability distributions and distribution functions, in: 6th International Conference on Computability and Complexity in Analysis, Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, A. Bauer, P. Hertling and K.-I. Ko, eds, Dagstuhl, 2009, pp. 185\u2013196."},{"key":"10.3233\/COM-170073_ref25","doi-asserted-by":"crossref","unstructured":"P. Olofsson, Probability, Statistics, and Stochastic Processes, Wiley-Interscience, New York, 2005.","DOI":"10.1002\/9780471743064"},{"key":"10.3233\/COM-170073_ref26","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1007\/s00224-016-9698-9","article-title":"On the generic undecidability of the halting problem for normalized Turing machines","volume":"60","author":"Rybalov","year":"2017","journal-title":"Theory of Computing Systems"},{"key":"10.3233\/COM-170073_ref27","doi-asserted-by":"crossref","unstructured":"F. Soler-Toscano, H. Zenil, J.-P. Delahaye and N. Gauvrit, Calculating Kolmogorov complexity from the output frequency distributions of small Turing machines, PLoS ONE 9(5) (2014), e96223.","DOI":"10.1371\/journal.pone.0096223"},{"key":"10.3233\/COM-170073_ref28","doi-asserted-by":"publisher","first-page":"145","DOI":"10.2307\/2267043","article-title":"Nicht konstruktiv beweisbare S\u00e4tze der Analysis","volume":"14","author":"Specker","year":"1949","journal-title":"The Journal of Symbolic Logic"},{"key":"10.3233\/COM-170073_ref29","doi-asserted-by":"crossref","unstructured":"K. Weihrauch, Computable Analysis. An Introduction, Springer, Berlin, 2000.","DOI":"10.1007\/978-3-642-56999-9"},{"key":"10.3233\/COM-170073_ref30","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-27654-5_17"},{"key":"10.3233\/COM-170073_ref31","doi-asserted-by":"crossref","unstructured":"H. Zenil and J.-P. Delahaye, On the algorithmic nature of the world, in: Information and Computation. Essays on Scientific and Philosophical Understanding of Foundations of Information and Computation, G. Dodig-Crnkovic and M. Burgin, eds, World Scientific, Singapore, 2010, pp. 477\u2013499.","DOI":"10.1142\/9789814295482_0017"}],"container-title":["Computability"],"original-title":[],"link":[{"URL":"https:\/\/content.iospress.com\/download?id=10.3233\/COM-170073","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T15:59:56Z","timestamp":1777391996000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/COM-170073"}},"subtitle":[],"editor":[{"given":"Benedikt","family":"L\u00f6we","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2018,6,7]]},"references-count":31,"journal-issue":{"issue":"2-3"},"URL":"https:\/\/doi.org\/10.3233\/com-170073","relation":{},"ISSN":["2211-3576","2211-3568"],"issn-type":[{"value":"2211-3576","type":"electronic"},{"value":"2211-3568","type":"print"}],"subject":[],"published":{"date-parts":[[2018,6,7]]}}}