Analogues of Chaitin's Omega in the computably enumerable sets

DOI10.1016/j.ipl.2013.01.007zbMath1259.68098OpenAlexW2004906655MaRDI QIDQ1941714

Wolfgang Merkle, Rupert Hölzl, George Barmpalias, Andrew E. M. Lewis

Publication date: 21 March 2013

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2013.01.007

zbMATH Keywords

completenessKolmogorov complexitycomputably enumerable sets

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Applications of computability and recursion theory (03D80)

Related Items

Universal computably enumerable sets and initial segment prefix-free complexity, CHAITIN’S Ω AS A CONTINUOUS FUNCTION, Kobayashi compressibility, Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega