Chaitin's Ω as a Continuous Function

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.