License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.06051.10
URN: urn:nbn:de:0030-drops-6319
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2006/631/
Go to the corresponding Portal

Calude, Christian S. ; Stay, Michael A.

Natural Halting Probabilities, Partial Randomness, and Zeta Functions

pdf-format:
06051.CaludeCristian.ExtAbstract.631.pdf (0.08 MB)

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.

BibTeX - Entry

@InProceedings{calude_et_al:DagSemProc.06051.10,
  author =	{Calude, Christian S. and Stay, Michael A.},
  title =	{{Natural Halting Probabilities, Partial Randomness, and Zeta Functions}},
  booktitle =	{Kolmogorov Complexity and Applications},
  pages =	{1--1},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6051},
  editor =	{Marcus Hutter and Wolfgang Merkle and Paul M.B. Vitanyi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2006/631},
  URN =		{urn:nbn:de:0030-drops-6319},
  doi =		{10.4230/DagSemProc.06051.10},
  annote =	{Keywords: Natural halting probability, natural complexity}
}

Keywords: Natural halting probability, natural complexity
Collection: 06051 - Kolmogorov Complexity and Applications
Issue Date: 2006
Date of publication: 31.07.2006

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI