David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Journal of Logic, Language and Information 14 (2):133-148 (2005)
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
|Keywords||infinite computations Kolmogorov complexity monotone machines non-effective computations program-size complexity Turing machines|
|Categories||categorize this paper)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
No references found.
Citations of this work BETA
No citations found.
Similar books and articles
William C. Calhoun (2006). Degrees of Monotone Complexity. Journal of Symbolic Logic 71 (4):1327 - 1341.
Ver�Nica Becher, Santiago Figueira, Andr� Nies & Silvana Picchi (2005). Program Size Complexity for Possibly Infinite Computations. Notre Dame Journal of Formal Logic 46 (1):51-64.
Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan & Leen Torenvliet (2006). Enumerations of the Kolmogorov Function. Journal of Symbolic Logic 71 (2):501 - 528.
Peter D. Grünwald & Paul M. B. Vitányi (2003). Kolmogorov Complexity and Information Theory. With an Interpretation in Terms of Questions and Answers. Journal of Logic, Language and Information 12 (4):497-529.
Joseph S. Miller (2004). Every 2-Random Real is Kolmogorov Random. Journal of Symbolic Logic 69 (3):907-913.
W. L. Fouché & P. H. Potgieter (1998). Kolmogorov Complexity and Symmetric Relational Structures. Journal of Symbolic Logic 63 (3):1083-1094.
Panu Raatikainen (2000). Algorithmic Information Theory and Undecidability. Synthese 123 (2):217-225.
James W. McAllister (2003). Effective Complexity as a Measure of Information Content. Philosophy of Science 70 (2):302-307.
Verónica Becher & Serge Grigorieff (2005). Random Reals and Possibly Infinite Computations Part I: Randomness in ∅'. Journal of Symbolic Logic 70 (3):891-913.
Added to index2009-01-28
Total downloads10 ( #152,182 of 1,099,914 )
Recent downloads (6 months)5 ( #67,010 of 1,099,914 )
How can I increase my downloads?