Abstract
For given real α ∈ {0,1} ∞ , a presentation V of α is a prefix-free and recursively enumerable subset of {0,1}* such that \(\alpha = \Sigma_{\sigma\epsilon\nu}2^{-|\sigma|}\). So, α has a presentation iff α is a left-r.e. real.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ambos-Spies, K., Jockusch, C., Shore, R., Soare, R.: An algebraic decomposition of the recursively enumerable degrees and classes equal to the promptly simple degrees. Transactions of the American Mathematical Society 281, 109–128 (1984)
Arslanov, M.M.: On some generalizations of the Fixed-Point Theorem. Soviet Mathematics (Iz. VUZ), Russian 25(5), 9–16 (1981); English translation 25(5), 1–10 (1981)
Arslanov, M.M.: M-reducibility and fixed points. Complexity problems of mathematical logic, Collection of scientific Works, Russian, Kalinin, pp. 11-18 (1985)
Calude, C., Hertling, P., Khoussainov, B., Wang, Y.: Recursively enumerable reals and Chaitin’s Ω number. In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol. 1373, pp. 596–606. Springer, Heidelberg (1998)
Chaitin, G.: A theory of program size formally identical to information theory. Journal of the Association for Computing Machinery 22, 329–340 (1975) (reprinted in [6])
Chaitin, G.: Information, Randomness & Incompleteness, 2nd edn. Series in Computer Science, vol. 8. World Scientific, River Edge (1990)
Cutland, N.: Computability, an introduction to recursive function theory. Cambridge University Press, Cambridge (1980)
Downey, R., Hirschfeldt, D.: Algorithmic Randomness and Complexity. Springer, Heidelberg (in preparation)
Downey, R., Hirschfeldt, D., Nies, A., Stephan, F.: Trivial reals. In: Proceedings of the 7th and 8th Asian Logic Conferences, pp. 103–131. World Scientific, River Edge (2003)
Downey, R., LaForte, G.: Presentations of computably enumerable reals. Theoretical Computer Science (to appear)
Kjos-Hanssen, B., Merkle, W., Stephan, F.: Kolmogorov complexity and the Recursion theorem (2005) (manuscript)
Nies, A.: Lowness properties and randomness. Advances in Mathematics (to appear)
Odifreddi, P.: Classical recursion theory, vol. 1. North-Holland, Amsterdam (1989); vol. 2. Elsevier, Amsterdam (1999)
Soare, R.: Recursively enumerable sets and degrees. Springer, Heidelberg (1987)
Solovay, R.: Draft of a paper (or series of papers) on Chaitin’s work, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, p. 215 (1975) (unpublished manuscript)
Wang, Y.: Randomness and Complexity. PhD Dissertation, University of Heidelberg (1996)
Wu, G.: Prefix-free languages and initial segments of computably enumerable degrees. In: Wang, J. (ed.) COCOON 2001. LNCS, vol. 2108, pp. 576–585. Springer, Heidelberg (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Stephan, F., Wu, G. (2005). Presentations of K-Trivial Reals and Kolmogorov Complexity. In: Cooper, S.B., Löwe, B., Torenvliet, L. (eds) New Computational Paradigms. CiE 2005. Lecture Notes in Computer Science, vol 3526. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11494645_57
Download citation
DOI: https://doi.org/10.1007/11494645_57
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-26179-7
Online ISBN: 978-3-540-32266-5
eBook Packages: Computer ScienceComputer Science (R0)