Kolmogorov complexity for possibly infinite computations

Journal of Logic, Language and Information 14 (2):133-148 (2005)
  Copy   BIBTEX

Abstract

In this paper we study the Kolmogorov complexity for non-effective computations, that is, either halting or non-halting computations on Turing machines. This complexity function is defined as the length of the shortest input that produce a desired output via a possibly non-halting computation. Clearly this function gives a lower bound of the classical Kolmogorov complexity. In particular, if the machine is allowed to overwrite its output, this complexity coincides with the classical Kolmogorov complexity for halting computations relative to the first jump of the halting problem. However, on machines that cannot erase their output –called monotone machines–, we prove that our complexity for non effective computations and the classical Kolmogorov complexity separate as much as we want. We also consider the prefix-free complexity for possibly infinite computations. We study several properties of the graph of these complexity functions and specially their oscillations with respect to the complexities for effective computations

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 98,169

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 and Noncomputability.George Davie - 2002 - Mathematical Logic Quarterly 48 (4):574-581.
Relative Kolmogorov complexity and geometry.Stephen Binns - 2011 - Journal of Symbolic Logic 76 (4):1211-1239.

Analytics

Added to PP
2009-01-28

Downloads
125 (#153,570)

6 months
12 (#236,181)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Add more citations

References found in this work

On Degrees of Unsolvability.J. R. Shoenfield - 1964 - Journal of Symbolic Logic 29 (4):203-204.

Add more references