David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Notre Dame Journal of Formal Logic 46 (1):51-64 (2005)
We define a program size complexity function 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 relative to the complexity. We prove that the classes of Martin-Löf random sequences and -random sequences coincide and that the -trivial sequences are exactly the recursive ones. We also study some properties of and compare it with other complexity functions. In particular, is different from , the prefix-free complexity of monotone machines with oracle A
|Keywords||program size complexity Kolmogorov complexity infinite computations|
|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
Verónica Becher & Santiago Figueira (2005). Kolmogorov Complexity for Possibly Infinite Computations. Journal of Logic, Language and Information 14 (2):133-148.
Verónica Becher & Serge Grigorieff (2005). Random Reals and Possibly Infinite Computations Part I: Randomness in ∅'. Journal of Symbolic Logic 70 (3):891-913.
Verónica Becher & Serge Grigorieff (2009). From Index Sets to Randomness in ∅ N : Random Reals and Possibly Infinite Computations. Part II. Journal of Symbolic Logic 74 (1):124-156.
Yaroslav Sergeyev (2009). Numerical Computations and Mathematical Modelling with Infinite and Infinitesimal Numbers. Journal of Applied Mathematics and Computing 29:177-195.
Luca Anderlini & Leonardo Felli (1999). Incomplete Contracts and Complexity Costs. Theory and Decision 46 (1):23-50.
Yaroslav D. Sergeyev (2008). A New Applied Approach for Executing Computations with Infinite and Infinitesimal Quantities. Informatica 19 (4):567-596.
Paolo Mancosu (2009). Measuring the Size of Infinite Collections of Natural Numbers: Was Cantor's Theory of Infinite Number Inevitable? Review of Symbolic Logic 2 (4):612-646.
William C. Calhoun (2006). Degrees of Monotone Complexity. Journal of Symbolic Logic 71 (4):1327 - 1341.
Jan Krajíček (2005). Structured Pigeonhole Principle, Search Problems and Hard Tautologies. Journal of Symbolic Logic 70 (2):619 - 630.
Andris Ambainis, John Case, Sanjay Jain & Mandayam Suraj (2004). Parsimony Hierarchies for Inductive Inference. Journal of Symbolic Logic 69 (1):287-327.
Verónica Becher, Santiago Figueira, Serge Grigorieff & Joseph S. Miller (2006). Randomness and Halting Probabilities. Journal of Symbolic Logic 71 (4):1411 - 1430.
Added to index2010-08-24
Total downloads3 ( #290,439 of 1,098,955 )
Recent downloads (6 months)3 ( #114,620 of 1,098,955 )
How can I increase my downloads?