Partial Randomness and Dimension of Recursively Enumerable Reals

DOI10.1007/978-3-642-03816-7_58zbMath1250.03069arXiv0906.2812OpenAlexW1740355831MaRDI QIDQ3182966

Kohtaro Tadaki

Publication date: 16 October 2009

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

Full work available at URL: https://arxiv.org/abs/0906.2812

zbMATH Keywords

dimensionalgorithmic randomnesspartial randomnessChaitin \(\Omega \) numberprogram-size complexityuniversal probabilityrecursively enumerable real

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Computation over the reals, computable analysis (03D78)

Related Items (5)

Phase Transition between Unidirectionality and Bidirectionality ⋮ Algorithmic information theory and its statistical mechanical interpretation ⋮ Solovay reducibility and continuity ⋮ A Chaitin \(\Omega\) number based on compressible strings ⋮ Representation of left-computable \(\varepsilon \)-random reals

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Natural halting probabilities, partial randomness, and zeta functions
• A tight upper bound on Kolmogorov complexity and uniformly optimal prediction
• A generalization of Chaitin's halting probability \(\Omega\) and halting self-similar sets
• Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity
• A Kolmogorov complexity characterization of constructive Hausdorff dimension.
• Process complexity and effective random tests
• Kolmogorov complexity and Hausdorff dimension
• On partial randomness
• Randomness and Recursive Enumerability
• An extension of Chaitin's halting probability Ω to a measurement operator in an infinite dimensional quantum system
• Fixed Point Theorems on Partial Randomness
• Algorithmic Information Theory
• A Theory of Program Size Formally Identical to Information Theory
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• The definition of random sequences
• Recursively enumerable reals and Chaitin \(\Omega\) numbers

This page was built for publication: Partial Randomness and Dimension of Recursively Enumerable Reals