Chaitin's Ω as a continuous function

We prove that the continuous function - - - that is defined via - - - for all - - - is differentiable exactly at the Martin-Löf random reals with the derivative having value 0; that it is nowhere monotonic; and that - -...

Full description

Saved in:

Bibliographic Details
Main Authors:	Hölzl, Rupert (Author) , Merkle, Wolfgang (Author) , Miller, Joseph (Author) , Stephan, Frank (Author) , Yu, Liang (Author)
Format:	Article (Journal)
Language:	English
Published:	09 September 2019
In:	The journal of symbolic logic Year: 2020, Volume: 85, Issue: 1, Pages: 486-510
ISSN:	1943-5886
DOI:	10.1017/jsl.2019.60
Online Access:	Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1017/jsl.2019.60 Verlag, lizenzpflichtig, Volltext: https://www.cambridge.org/core/journals/journal-of-symbolic-logic/article/chaitins-as-a-continuous-function/B0ECE220CCAE3BD9C9E27FB92105CF3E
Author Notes:	Rupert Hölzl, Wolfgang Merkle, Joseph Miller, Frank Stephan, and Liang Yu

Description
Summary:	We prove that the continuous function - - - that is defined via - - - for all - - - is differentiable exactly at the Martin-Lö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 - - - , 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 - - - is rational.
Item Description:	Gesehen am 12.01.2021
Physical Description:	Online Resource
ISSN:	1943-5886
DOI:	10.1017/jsl.2019.60