Please use this identifier to cite or link to this item: https://doi.org/10.1017/jsl.2019.60
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. https://doi.org/10.1017/jsl.2019.60
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
URI: https://scholarbank.nus.edu.sg/handle/10635/177517
ISSN: 0022-4812
DOI: 10.1017/jsl.2019.60
Appears in Collections:Staff Publications
Elements

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

OPEN

Post-printView/Download

Page view(s)

136
checked on May 12, 2022

Download(s)

1
checked on May 12, 2022

Google ScholarTM

Check

Altmetric


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