Chaitin's Ω as a continuous function
We prove that the continuous function - - - 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 - -...
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Dokumenttyp: | Article (Journal) |
| Sprache: | Englisch |
| Veröffentlicht: |
09 September 2019
|
| In: |
The journal of symbolic logic
Year: 2020, Jahrgang: 85, Heft: 1, Pages: 486-510 |
| ISSN: | 1943-5886 |
| DOI: | 10.1017/jsl.2019.60 |
| Online-Zugang: | 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 
|
| Verfasserangaben: | Rupert Hölzl, Wolfgang Merkle, Joseph Miller, Frank Stephan, and Liang Yu |
| Zusammenfassung: | We prove that the continuous function - - - 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 - - - , 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. |
|---|---|
| Beschreibung: | Gesehen am 12.01.2021 |
| Beschreibung: | Online Resource |
| ISSN: | 1943-5886 |
| DOI: | 10.1017/jsl.2019.60 |