{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:18:09Z","timestamp":1772119089587,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662476710","type":"print"},{"value":"9783662476727","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-47672-7_18","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T06:07:39Z","timestamp":1434694059000},"page":"219-230","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["What Percentage of Programs Halt?"],"prefix":"10.1007","author":[{"given":"Laurent","family":"Bienvenu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Damien","family":"Desfontaines","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Shen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"key":"18_CR1","unstructured":"Bienvenu, L., Muchnik, A., Shen, A., Vereshchagin, N.: Limit complexities revisited [once more]. Technical report (2012). arxiv:1204.0201"},{"key":"18_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/978-3-642-27654-5_3","volume-title":"Computation, Physics and Beyond","author":"L Bienvenu","year":"2012","unstructured":"Bienvenu, L., Shen, A.: Random semicomputable reals revisited. In: Dinneen, M.J., Khoussainov, B., Nies, A. (eds.) Computation, Physics and Beyond. LNCS, vol. 7160, pp. 31\u201345. Springer, Heidelberg (2012)"},{"key":"18_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1007\/BFb0028594","volume-title":"STACS 98","author":"CS Calude","year":"1998","unstructured":"Calude, C.S., Hertling, P.H., Khoussainov, B., Wang, Y.: Recursively enumerable reals and chaitin omega numbers. In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol. 1373, pp. 596\u2013606. Springer, Heidelberg (1998)"},{"issue":"22","key":"18_CR4","doi-asserted-by":"publisher","first-page":"2253","DOI":"10.1016\/j.tcs.2011.01.002","volume":"412","author":"C Calude","year":"2011","unstructured":"Calude, C., Nies, A., Staiger, L., Stephan, F.: Universal recursively enumerable sets of strings. Theoretical Computer Science 412(22), 2253\u20132261 (2011)","journal-title":"Theoretical Computer Science"},{"key":"18_CR5","series-title":"Theory and Applications of Computability","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-68441-3","volume-title":"Algorithmic randomness and complexity","author":"R Downey","year":"2010","unstructured":"Downey, R., Hirschfeldt, D.: Algorithmic randomness and complexity. Theory and Applications of Computability. Springer, New York (2010)"},{"key":"18_CR6","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Jockusch Jr., C.G., Schupp, P.E.: Asymptotic density and computably enumerable sets. Journal of Mathematical Logic 13(02) (2013)","DOI":"10.1142\/S0219061313500050"},{"key":"18_CR7","doi-asserted-by":"crossref","unstructured":"Hamkins, J.D., Miasnikov, A.: The halting problem is decidable on a set of asymptotic probability one. Notre Dame Journal of Formal Logic 47(4) (2006)","DOI":"10.1305\/ndjfl\/1168352664"},{"key":"18_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"454","DOI":"10.1007\/11537311_40","volume-title":"Fundamentals of Computation Theory","author":"S K\u00f6hler","year":"2005","unstructured":"K\u00f6hler, S., Schindelhauer, C., Ziegler, M.: On approximating real-world halting problems. In: Li\u015bkiewicz, M., Reischuk, R. (eds.) FCT 2005. LNCS, vol. 3623, pp. 454\u2013466. Springer, Heidelberg (2005)"},{"key":"18_CR9","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1137\/S0097539799357441","volume":"31","author":"A Ku\u010dera","year":"2001","unstructured":"Ku\u010dera, A., Slaman, T.: Randomness and recursive enumerability. SIAM Journal on Computing 31, 199\u2013211 (2001)","journal-title":"SIAM Journal on Computing"},{"key":"18_CR10","volume-title":"An Introduction to Kolmogorov Complexity and Its Applications","author":"M Li","year":"2007","unstructured":"Li, M., Vit\u00e1nyi, P.: An Introduction to Kolmogorov Complexity and Its Applications, 3rd edn. Springer, New York (2007)","edition":"3"},{"key":"18_CR11","doi-asserted-by":"crossref","unstructured":"Lynch, N.: Approximations to the halting problem. Journal of Computer and System Sciences, 9\u2013143 (1974)","DOI":"10.1016\/S0022-0000(74)80003-6"},{"issue":"3","key":"18_CR12","doi-asserted-by":"publisher","first-page":"907","DOI":"10.2178\/jsl\/1096901774","volume":"69","author":"JS Miller","year":"2004","unstructured":"Miller, J.S.: Every 2-random real is Kolmogorov random. Journal of Symbolic Logic 69(3), 907\u2013913 (2004)","journal-title":"Journal of Symbolic Logic"},{"key":"18_CR13","doi-asserted-by":"crossref","unstructured":"Nies, A.: Computability and randomness. Oxford University Press, Oxford Logic Guides (2009)","DOI":"10.1093\/acprof:oso\/9780199230761.001.0001"},{"key":"18_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1007\/3-540-46691-6_32","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"C Schindelhauer","year":"1999","unstructured":"Schindelhauer, C., Jakoby, A.: The non-recursive power of erroneous computation. In: Pandu Rangan, C., Raman, V., Sarukkai, S. (eds.) FST TCS 1999. LNCS, vol. 1738, p. 394. Springer, Heidelberg (1999)"},{"issue":"2","key":"18_CR15","first-page":"181","volume":"8","author":"Claus Peter Schnorr","year":"1974","unstructured":"Claus Peter Schnorr: Optimal enumerations and optimal G\u00f6del numberings. Mathematical Systems Theory 8(2), 181\u2013191 (1974)","journal-title":"Mathematical Systems Theory"},{"key":"18_CR16","unstructured":"Valmari, A.: The asymptotic proportion of hard instances of the halting problem. Technical report, November 2014. arxiv:1307.7066v2"},{"key":"18_CR17","unstructured":"Vereshchagin, N., Uspensky, V., Shen. A.: Kolmogorov complexity and algorithmic randomness (In Russian. See www.lirmm.fr\/~ashen for the draft translation.). MCCME (2013)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47672-7_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,20]],"date-time":"2023-02-20T21:12:30Z","timestamp":1676927550000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-47672-7_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476710","9783662476727"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47672-7_18","relation":{"has-preprint":[{"id-type":"doi","id":"10.31219\/osf.io\/dfmbk","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"20 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}