A Chaitin \(\Omega\) number based on compressible strings

DOI10.1007/s11047-011-9272-yzbMath1251.68122OpenAlexW3099150922MaRDI QIDQ1761717

Kohtaro Tadaki

Publication date: 15 November 2012

Published in: Natural Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11047-011-9272-y

zbMATH Keywords

fixed pointalgorithmic information theoryalgorithmic randomnesspartial randomnessprogram-size complexityChaitin \(\Omega\) numbercompressible string

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Natural halting probabilities, partial randomness, and zeta functions
• Statistical physics I. Equilibrium statistical mechanics. Rev. transl. from the Japanese ed. by Morikazu Toda and Nobuhiko Saitô.
• Algorithmic entropy of sets
• A generalization of Chaitin's halting probability \(\Omega\) and halting self-similar sets
• Process complexity and effective random tests
• On partial randomness
• Randomness and Recursive Enumerability
• Algorithmic Randomness and Complexity
• Partial Randomness and Dimension of Recursively Enumerable Reals
• 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