Time-Bounded Kolmogorov Complexity and Solovay Functions

DOI10.1007/978-3-642-03816-7_34MaRDI QIDQ3182941zbMATH OpenOpenAlexFDO

Authors Rupert Hölzl, Thorsten Kräling, Wolfgang Merkle

Publication date 16 October 2009

Published in Mathematical Foundations of Computer Science 2009 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-03816-7_34

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Time-bounded Kolmogorov complexity and Solovay functions
• Kolmogorov complexity and solovay functions
• Solovay functions and K-triviality
• Kolmogorov complexity
• Solovay functions and their applications in algorithmic randomness

Cites work

• Algorithmic randomness and complexity.
• An introduction to Kolmogorov complexity and its applications
• Computability and Randomness
• Computational depth and reducibility
• scientific article; zbMATH DE number 3307567 (Why is no real title available?)
• Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets
• Kolmogorov complexity and solovay functions
• Randomness and recursive enumerability
• The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
• 𝐾-trivial degrees and the jump-traceability hierarchy

Cited in

(14)

• Time-bounded Kolmogorov complexity and Solovay functions
• Random semicomputable reals revisited
• Randomness, computation and mathematics
• Kolmogorov complexity
• Solovay functions and K-triviality
• A \(K\)-trivial set which is not jump traceable at certain orders
• Strong jump-traceability
• Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts
• Kolmogorov complexity and solovay functions
• Inherent enumerability of strong jump-traceability
• Kolmogorov complexity of initial segments of sequences and arithmetical definability
• A variant of Chaitin's Omega function
• Compression of enumerations and gain
• Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega

This page was built for publication: Time-Bounded Kolmogorov Complexity and Solovay Functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3182941)