Natural Halting Probabilities, Partial Randomness, and Zeta Functions

Authors Christian S. Calude, Michael A. Stay



PDF
Thumbnail PDF

File

DagSemProc.06051.10.pdf
  • Filesize: 81 kB
  • 1 pages

Document Identifiers

Author Details

Christian S. Calude
Michael A. Stay

Cite AsGet BibTex

Christian S. Calude and Michael A. Stay. Natural Halting Probabilities, Partial Randomness, and Zeta Functions. In Kolmogorov Complexity and Applications. Dagstuhl Seminar Proceedings, Volume 6051, p. 1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)
https://doi.org/10.4230/DagSemProc.06051.10

Abstract

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.
Keywords
  • Natural halting probability
  • natural complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail