Please use this identifier to cite or link to this item:
Title: Chaitin's Ω as a Continuous Function
Authors: Hölzl R. 
Merkle W.
Miller J.
Stephan F. 
Yu L.
Keywords: Chaitin's number
computable analysis
Kolmogorov complexity
Issue Date: 2020
Publisher: Cambridge University Press
Citation: Hölzl R., Merkle W., Miller J., Stephan F., Yu L. (2020). Chaitin's Ω as a Continuous Function. Journal of Symbolic Logic 85 (1) : 486-510. ScholarBank@NUS Repository.
Abstract: We prove that the continuous function Ω: 2ω → R that is defined via for all is differentiable exactly at the Martin-Löf random reals with the derivative having value 0; that it is nowhere monotonic; and that is a left-c.e.-complete real having effective Hausdorff dimension. We further investigate the algorithmic properties of Ω. For example, we show that the maximal value of must be random, the minimal value must be Turing complete, and that for every X. We also obtain some machine-dependent results, including that for every ϵ > 0, there is a universal machine V such that maps every real X having effective Hausdorff dimension greater than ϵ to a real of effective Hausdorff dimension 0 with the property that ; and that there is a real X and a universal machine V such that Ωv(x) is rational. © 2019 The Association for Symbolic Logic.
Source Title: Journal of Symbolic Logic
ISSN: 0022-4812
DOI: 10.1017/jsl.2019.60
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
omega23.pdf418.59 kBAdobe PDF



Page view(s)

checked on May 12, 2022


checked on May 12, 2022

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.