A variant of Chaitin's Omega function

DOI10.1016/J.APAL.2026.103748MaRDI QIDQ7249405zbMATH OpenFDO

Authors Yuxuan Li, Shuheng Zhang, Xuanheng zhao, Xiaoyan Zhang

Publication date 15 May 2026

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.APAL.2026.103748

zbMATH Keywords

Chaitin's Omegaleft-c.e. realweakly lowness for K

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30) Algorithmic randomness and dimension (03D32) Hausdorff and packing measures (28A78) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Cites work

• A Theory of Program Size Formally Identical to Information Theory
• Algorithmic randomness and complexity.
• Chaitin's as a continuous function
• Coherent randomness tests and computing the \(K\)-trivial sets
• Computability and randomness
• Computational aspects of the hyperimmune-free degrees
• Computing and Combinatorics
• Density, forcing, and the covering problem
• scientific article; zbMATH DE number 4091484 (Why is no real title available?)
• scientific article; zbMATH DE number 739280 (Why is no real title available?)
• Kolmogorov complexity and solovay functions
• Lebesgue density and \(\Pi _1^0\) classes
• Randomness and halting probabilities
• Randomness and recursive enumerability
• RELATIVIZING CHAITIN'S HALTING PROBABILITY
• The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
• Time-Bounded Kolmogorov Complexity and Solovay Functions
• Using almost-everywhere theorems from analysis to study randomness

This page was built for publication: A variant of Chaitin's Omega function

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