Hostname: page-component-7b7567c8c-mnklg Total loading time: 0 Render date: 2026-11-12T10:55:25.822Z Has data issue: false hasContentIssue false
  • English
  • Français

CHAITIN’S Ω AS A CONTINUOUS FUNCTION

Published online by Cambridge University Press:  09 September 2019

RUPERT HÖLZL,
WOLFGANG MERKLE,
JOSEPH MILLER,
FRANK STEPHAN and
LIANG YU
RUPERT HÖLZL
Affiliation:
INSTITUTE 1, FACULTY OF COMPUTER SCIENCE BUNDESWEHR UNIVERSITY MUNICH WERNER-HEISENBERG-WEG 39 85579, NEUBIBERG GERMANY E-mail: r@hoelzl.fr
WOLFGANG MERKLE
Affiliation:
INSTITUT FÜR INFORMATIK RUPRECHT-KARLS-UNIVERSITÄT HEIDELBERG69120, GERMANY E-mail: merkle@math.uni-heidelberg.de
JOSEPH MILLER
Affiliation:
DEPARTMENT OF MATHEMATICS UNIVERSITY OF WISCONSIN MADISON, WI53706, USA E-mail: jmiller@math.wisc.edu
FRANK STEPHAN
Affiliation:
DEPARTMENT OF MATHEMATICS NATIONAL UNIVERSITY OF SINGAPORE BLOCK S17, 10 LOWER KENT RIDGE ROAD SINGAPORE 119076, SINGAPORE E-mail: fstephan@comp.nus.edu.sg
LIANG YU
Affiliation:
MATHEMATICAL DEPARTMENT NANJING UNIVERSITY NANJING, JIANGSU PROVINCE210093 CHINA E-mail: yuliang.nju@gmail.com
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We prove that the continuous function${\rm{\hat \Omega }}:2^\omega \to $ that is defined via$X \mapsto \mathop \sum \limits_n 2^{ - K\left( {Xn} \right)} $ for all $X \in {2^\omega }$ is differentiable exactly at the Martin-Löf random reals with the derivative having value 0; that it is nowhere monotonic; and that $\mathop \smallint \nolimits _0^1{\rm{\hat{\Omega }}}\left( X \right)\,{\rm{d}}X$ is a left-c.e. $wtt$-complete real having effective Hausdorff dimension ${1 / 2}$.

We further investigate the algorithmic properties of ${\rm{\hat{\Omega }}}$. For example, we show that the maximal value of ${\rm{\hat{\Omega }}}$ must be random, the minimal value must be Turing complete, and that ${\rm{\hat{\Omega }}}\left( X \right) \oplus X{ \ge _T}\emptyset \prime$ for every X. We also obtain some machine-dependent results, including that for every $\varepsilon > 0$, there is a universal machine V such that ${{\rm{\hat{\Omega }}}_V}$ maps every real X having effective Hausdorff dimension greater than ε to a real of effective Hausdorff dimension 0 with the property that $X{ \le _{tt}}{{\rm{\hat{\Omega }}}_V}\left( X \right)$; and that there is a real X and a universal machine V such that ${{\rm{\Omega }}_V}\left( X \right)$ is rational.

Keywords

03D3268Q3026A2726A30Kolmogorov complexityChaitin’s numbercomputable analysis

Information

Type
Articles
Information
The Journal of Symbolic Logic , Volume 85 , Issue 1 , March 2020, pp. 486 - 510
Copyright
Copyright © The Association for Symbolic Logic 2019 

References

REFERENCES

Arslanov, M. M., Some generalizations of a fixed-point theorem. Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika, vol. 5 (1981), pp. 9–16.Google Scholar
Barmpalias, G., Aspects of Chaitin’s Omega, preprint, 2017, arXiv:1707.08109.Google Scholar
Barmpalias, G., Cenzer, D., and Porter, C. P., The probability of a computable output from a random oracle. ACM Transactions on Computational Logic, vol. 18 (2017), no. 3, pp. 18:1–18:15.Google Scholar
Barmpalias, G., Cenzer, D., and Porter, C. P., Random numbers as probabilities of machine behavior. Theoretical Computer Science, vol. 673 (2017), pp. 1–18.CrossRefGoogle Scholar
Barmpalias, G., Hölzl, R., Lewis, A. E. M., and Merkle, W., Analogues of Chaitin’s Omega in the computably enumerable sets. Information Processing Letters, vol. 113 (2013), no. (5–6), pp. 171–178.Google Scholar
Becher, V., Figueira, S., Grigorieff, S., and Miller, J. S., Randomness and halting probabilities, this Journal, vol. 71 (2006), no. 4, pp. 1411–1430.Google Scholar
Becher, V. and Grigorieff, S., Random reals and possibly infinite computations. I. Randomness in $\emptyset \prime$, this Journal, vol. 70 (2005), no. 3, pp. 891–913.Google Scholar
Bienvenu, L., Day, A. R., Greenberg, N., Kučera, A., Miller, J. S., Nies, A., and Turetsky, D., Computing K-trivial sets by incomplete random sets. Bulletin of Symbolic Logic, vol. 20 (2014), no. 1, pp. 80–90.CrossRefGoogle Scholar
Bienvenu, L. and Downey, R., Kolmogorov complexity and Solovay functions, STACS 2009: 26th International Symposium on Theoretical Aspects of Computer Science (Albers, S. and Marion, J.-Y., editors), LIPICS - Leibniz International Proceedings in Informatics, vol. 3, Schloss Dagstuhl. Leibniz-Zentrum für Informatik, Wadern, 2009, pp. 147–158.Google Scholar
Bienvenu, L., Hölzl, R., Miller, J. S., and Nies, A., Denjoy, Demuth and density. Journal of Mathematical Logic, vol. 14 (2014), no. 1-1450004, pp. 1–35.CrossRefGoogle Scholar
Calude, C. S., Hay, N. J., and Stephan, F., Representation of left-computable ε-random reals. Journal of Computer and System Sciences, vol. 77 (2011), no. 4, pp. 812–819.CrossRefGoogle Scholar
Chaitin, G. J., A theory of program size formally identical to information theory. Journal of the ACM, vol. 22 (1975), pp. 329–340.CrossRefGoogle Scholar
Downey, R. G. and Hirschfeldt, D. R., Algorithmic Randomness and Complexity, Theory and Applications of Computability, Springer, New York, 2010.CrossRefGoogle Scholar
Downey, R., Hirschfeldt, D. R., Miller, J. S., and Nies, A., Relativizing Chaitin’s halting probability. Journal of Mathematical Logic, vol. 5 (2005), no. 2, pp. 167–192.Google Scholar
Gács, P., On the symmetry of algorithmic information. Soviet Mathematics Doklady, vol. 150 (1974), pp. 1477–1480.Google Scholar
Hölzl, R., Kräling, T., and Merkle, W., Time-bounded Kolmogorov complexity and Solovay functions. Theory of Computing Systems, vol. 52 (2013), no. 1, pp. 80–94.CrossRefGoogle Scholar
Miller, J. S., The K-degrees, low for K-degrees, and weakly low for K sets. Notre Dame Journal of Formal Logic, vol. 50 (2009), no. 3, pp. 381–391.CrossRefGoogle Scholar
Miller, J. S. and Yu, L., On initial segment complexity and degrees of randomness. Transactions of the American Mathematical Society, vol. 360 (2008), no. 6, pp. 3193–3210.Google Scholar
Miyabe, K., Nies, A., and Zhang, J., Using almost-everywhere theorems from analysis to study randomness. Bulletin of Symbolic Logic, vol. 22 (2016), no. 3, pp. 305–331.CrossRefGoogle Scholar
Nies, A., Computability and Randomness, Oxford Logic Guides, vol. 51, Oxford University Press, Oxford, 2009.CrossRefGoogle Scholar
Rettinger, R. and Zheng, X., Solovay reducibility on d-c.e. real numbers, Computing and Combinatorics (Wang, L., editor), Lecture Notes in Computer Science, vol. 3595, Springer, Berlin, 2005, pp. 359–368.Google Scholar
Soare, R. I., Recursively Enumerable Sets and Degrees, Springer-Verlag, Berlin, 1987.CrossRefGoogle Scholar