{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T00:04:09Z","timestamp":1772237049684,"version":"3.50.1"},"reference-count":1,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2016,4,5]],"date-time":"2016-04-05T00:00:00Z","timestamp":1459814400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"funder":[{"DOI":"10.13039\/501100001665","name":"French National Research Agency","doi-asserted-by":"crossref","award":["ANR-15-CE40-0016"],"award-info":[{"award-number":["ANR-15-CE40-0016"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>The halting problem is undecidable --- but can it be solved for \"most\"\ninputs? This natural question was considered in a number of papers, in\ndifferent settings. We revisit their results and show that most of them can be\neasily proven in a natural framework of optimal machines (considered in\nalgorithmic information theory) using the notion of Kolmogorov complexity. We\nalso consider some related questions about this framework and about asymptotic\nproperties of the halting problem. In particular, we show that the fraction of\nterminating programs cannot have a limit, and all limit points are Martin-L\\\"of\nrandom reals. We then consider mass problems of finding an approximate solution\nof halting problem and probabilistic algorithms for them, proving both positive\nand negative results. We consider the fraction of terminating programs that\nrequire a long time for termination, and describe this fraction using the busy\nbeaver function. We also consider approximate versions of separation problems,\nand revisit Schnorr's results about optimal numberings showing how they can be\ngeneralized.<\/jats:p>","DOI":"10.2168\/lmcs-12(2:1)2016","type":"journal-article","created":{"date-parts":[[2016,11,21]],"date-time":"2016-11-21T08:47:33Z","timestamp":1479718053000},"source":"Crossref","is-referenced-by-count":1,"title":["Generic algorithms for halting problem and optimal machines revisited"],"prefix":"10.46298","volume":"Volume 12, Issue 2","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"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8605-7734","authenticated-orcid":false,"given":"Alexander","family":"Shen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2016,4,5]]},"reference":[{"key":"1168:not-found"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/1633\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/1633\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T16:08:35Z","timestamp":1681229315000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/1633"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,4,5]]},"references-count":1,"URL":"https:\/\/doi.org\/10.2168\/lmcs-12(2:1)2016","relation":{"is-same-as":[{"id-type":"arxiv","id":"1505.00731","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1505.00731","asserted-by":"subject"}],"has-preprint":[{"id-type":"doi","id":"10.31219\/osf.io\/yf6kj","asserted-by":"object"}]},"ISSN":["1860-5974"],"issn-type":[{"value":"1860-5974","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,4,5]]},"article-number":"1633"}}