{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:17:36Z","timestamp":1759637856878,"version":"3.44.0"},"reference-count":30,"publisher":"SAGE Publications","issue":"2","license":[{"start":{"date-parts":[[2020,4,14]],"date-time":"2020-04-14T00:00:00Z","timestamp":1586822400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Computability"],"published-print":{"date-parts":[[2020,5,13]]},"abstract":"<jats:p> In a previous paper we used computer running times to define a class of computable probability distributions on the set of halting programs and developed a probabilistic anytime algorithm for the Halting Problem. The choice of a computable probability distribution\u00a0\u2013 essential for the algorithm\u00a0\u2013 can be rather subjective and hard to substantiate. <\/jats:p><jats:p> In this paper we propose and study an efficient statistical anytime algorithm for the Halting Problem. The main advantage of the statistical algorithm is that it can be implemented without any prior information about the running times on the specific model of computation and the cut-off temporal bound is reasonably small. The algorithm has two parts: the pre-processing which is done only once (when the parameters of the quality of solutions are fixed) and the main part which is run for any input program. With a confidence level as large as required, the algorithm produces correct decisions with a probability as large as required. Three implementations of the algorithm are presented and numerically illustrated. <\/jats:p>","DOI":"10.3233\/com-190250","type":"journal-article","created":{"date-parts":[[2020,4,14]],"date-time":"2020-04-14T13:29:49Z","timestamp":1586870989000},"page":"155-166","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":4,"title":["A\u00a0statistical anytime algorithm for the Halting Problem"],"prefix":"10.1177","volume":"9","author":[{"given":"Cristian S.","family":"Calude","sequence":"first","affiliation":[{"name":"Department of Computer, Science, University of Auckland, Auckland, New Zealand. \u00a0"}]},{"given":"Monica","family":"Dumitrescu","sequence":"additional","affiliation":[{"name":"Faculty of Mathematics and Computer Science, Bucharest University, Romania. \u00a0"}]}],"member":"179","published-online":{"date-parts":[[2020,4,14]]},"reference":[{"key":"ref001","doi-asserted-by":"crossref","unstructured":"B.C.\u00a0Arnold, N.\u00a0Balakrishnan and H.N.\u00a0Nagaraja, A\u00a0First Course in Order Statistics, John Wiley, New York, 2008.","DOI":"10.1137\/1.9780898719062"},{"key":"ref002","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_18"},{"key":"ref003","first-page":"1","author":"Bringmann K.","year":"2016","journal-title":"Algorithmica"},{"key":"ref004","unstructured":"C.\u00a0Calude, Theories of Computational Complexity, North Holland, Amsterdam, 1988."},{"key":"ref005","unstructured":"C.S.\u00a0Calude, Information and Randomness: An Algorithmic Perspective, 2nd edn, Springer, Berlin, 2002."},{"key":"ref006","doi-asserted-by":"publisher","DOI":"10.3233\/FI-2015-1199"},{"key":"ref007","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054115500252"},{"key":"ref008","doi-asserted-by":"publisher","DOI":"10.3233\/COM-170073"},{"key":"ref009","doi-asserted-by":"publisher","DOI":"10.1016\/j.aam.2007.01.001"},{"key":"ref010","doi-asserted-by":"publisher","DOI":"10.1145\/1941487.1941509"},{"key":"ref011","doi-asserted-by":"crossref","unstructured":"A.\u00a0DasGupta, Probability for Statistics and Machine Learning, Springer, New York, 2011.","DOI":"10.1007\/978-1-4419-9634-3"},{"key":"ref012","doi-asserted-by":"crossref","unstructured":"R.\u00a0Downey and D.\u00a0Hirschfeldt, Algorithmic Randomness and Complexity, Springer, Heidelberg, 2010.","DOI":"10.1007\/978-0-387-68441-3"},{"key":"ref013","doi-asserted-by":"publisher","DOI":"10.1145\/332148.332154"},{"key":"ref014","doi-asserted-by":"publisher","DOI":"10.1305\/ndjfl\/1168352664"},{"key":"ref015","doi-asserted-by":"publisher","DOI":"10.1007\/11537311_40"},{"key":"ref016","doi-asserted-by":"publisher","DOI":"10.25088\/ComplexSystems.27.1.85"},{"key":"ref017","unstructured":"R.H.\u00a0Lathrop, On the learnability of the uncomputable, in: Proceedings International Conference on Machine Learning, L.\u00a0Saitta, ed. Morgan Kaufmann, 1996, pp.\u00a0302\u2013309."},{"key":"ref018","unstructured":"P.S.\u00a0Levy and S.\u00a0Lemeshow, Sampling of Populations. Methods and Applications, 3rd edn, John Wiley, 1999."},{"key":"ref019","doi-asserted-by":"crossref","unstructured":"M.\u00a0Li and P.M.B.\u00a0Vit\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":"ref020","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80003-6"},{"key":"ref021","doi-asserted-by":"crossref","unstructured":"Yu.I.\u00a0Manin, A\u00a0Course in Mathematical Logic for Mathematicians, 2nd edn, Springer, Berlin, 2010.","DOI":"10.1007\/978-1-4419-0615-1"},{"key":"ref022","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129511000508"},{"key":"ref023","unstructured":"T.\u00a0Mori, Y.\u00a0Tsujii and M.\u00a0Yasugi, 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.\u00a0Bauer, P.\u00a0Hertling and K.I\u00a0Ko, eds, Dagstuhl, 2009, pp.\u00a0185\u2013196."},{"key":"ref024","doi-asserted-by":"crossref","unstructured":"P.\u00a0Olofsson, Probability, Statistics, and Stochastic Processes, Wiley-Interscience, New York, 2005.","DOI":"10.1002\/9780471743064"},{"key":"ref025","first-page":"1","author":"Rybalov A.","year":"2016","journal-title":"Theory of Computing Systems"},{"key":"ref026","unstructured":"C.\u00a0Scott, Statistical learning theory, topic 3: Hoeffding\u2019s inequality, University of Toronto, 2014, https:\/\/www.coursehero.com\/file\/18068309\/03-hoeffding, retrieved 4 June 2019."},{"key":"ref027","doi-asserted-by":"crossref","unstructured":"F.\u00a0Soler-Toscano, H.\u00a0Zenil, J.P.\u00a0Delahaye and N.\u00a0Gauvrit, 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":"ref028","doi-asserted-by":"crossref","unstructured":"K.\u00a0Weihrauch, Computable Analysis. An Introduction, Springer, Berlin, 2000.","DOI":"10.1007\/978-3-642-56999-9"},{"key":"ref029","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-27654-5_17"},{"key":"ref030","doi-asserted-by":"crossref","unstructured":"H.\u00a0Zenil and J.P.\u00a0Delahaye, On the algorithmic nature of the world, in: Information and Computation. Essays on Scientific and Philosophical Understanding of Foundations of Information and Computation, G.\u00a0Dodig-Crnkovic and M.\u00a0Burgin, eds, World Scientific, Singapore, 2010, pp.\u00a0477\u2013499.","DOI":"10.1142\/9789814295482_0017"}],"container-title":["Computability"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-190250","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.3233\/COM-190250","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-190250","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T12:22:37Z","timestamp":1757420557000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/COM-190250"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,14]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,5,13]]}},"alternative-id":["10.3233\/COM-190250"],"URL":"https:\/\/doi.org\/10.3233\/com-190250","relation":{},"ISSN":["2211-3568","2211-3576"],"issn-type":[{"type":"print","value":"2211-3568"},{"type":"electronic","value":"2211-3576"}],"subject":[],"published":{"date-parts":[[2020,4,14]]}}}