2026-10-12T10:30:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:631 2024-03-06T10:06:42Z ddc:004 open_access

Natural Halting Probabilities, Partial Randomness, and Zeta Functions Calude, Christian S. Stay, Michael A. Natural halting probability natural complexity We introduce the {it natural halting probability} and the {it natural complexity} of a Turing machine and we relate them to program-size complexity and Chaitin's halting probability. A classification of Turing machines according to their natural (Omega) halting probabilities is proposed: divergent, convergent and tuatara. We prove the existence of universal convergent and tuatara machines. Various results on randomness and partial randomness are proved. For example, we show that the natural halting probability of a universal tuatara machine is c.e. and random. A new type of partial randomness, asymptotic randomness, is introduced. Finally we show that in contrast to classical (algorithmic) randomness---which cannot be characterised in terms of plain complexity---various types of partial randomness admit such characterisations. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Christian S. Calude and Michael A. Stay 2006 Is Part Of Dagstuhl Seminar Proceedings, Volume 6051, Kolmogorov Complexity and Applications (2006) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.06051.10 urn:nbn:de:0030-drops-6319 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06051.10 eng https://creativecommons.org/licenses/by/4.0/legalcode