Program Size Complexity for Possibly Infinite Computations

Notre Dame Journal of Formal Logic 46 (1):51-64 (2005)
  Copy   BIBTEX

Abstract

We define a program size complexity function $H^\infty$ as a variant of the prefix-free Kolmogorov complexity, based on Turing monotone machines performing possibly unending computations. We consider definitions of randomness and triviality for sequences in ${\{0,1\}}^\omega$ relative to the $H^\infty$ complexity. We prove that the classes of Martin-Löf random sequences and $H^\infty$-random sequences coincide and that the $H^\infty$-trivial sequences are exactly the recursive ones. We also study some properties of $H^\infty$ and compare it with other complexity functions. In particular, $H^\infty$ is different from $H^A$, the prefix-free complexity of monotone machines with oracle A

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,593

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Kolmogorov complexity for possibly infinite computations.Verónica Becher & Santiago Figueira - 2005 - Journal of Logic, Language and Information 14 (2):133-148.
Degrees of Monotone Complexity.William C. Calhoun - 2006 - Journal of Symbolic Logic 71 (4):1327 - 1341.

Analytics

Added to PP
2010-08-24

Downloads
114 (#144,443)

6 months
4 (#319,344)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Degrees of Monotone Complexity.William C. Calhoun - 2006 - Journal of Symbolic Logic 71 (4):1327 - 1341.

Add more citations