Abstract
The present work clarifies the relation between domains of universal machines and r.e. prefix-free supersets of such sets. One such characterisation can be obtained in terms of the spectrum function s W (n) mapping n to the number of all strings of length n in the set W. An r.e. prefix-free set W is the superset of the domain of a universal machine iff there are two constants c,d such that s W (n) + s W (n + 1) + ... + s W (n + c) is between 2n − H(n) − d and 2n − H(n) + d for all n; W is the domain of a universal machine iff there is a constant c such that for each n the pair of n and s W (n) + s W (n + 1) + ... + s W (n + c) has at least the prefix-free Description complexity n. There exists a prefix-free r.e. superset W of a domain of a universal machine which is the not a domain of a universal machine; still, the halting probability Ω W of such a set W is Martin-Löf random. Furthermore, it is investigated to which extend this results can be transferred to plain universal machines.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Calude, C.S.: Information and Randomness: An Algorithmic Perspective, 2nd edn., Revised and Extended. Springer, Berlin (2002)
Calude, C.S., Hertling, P.H., Khoussainov, B., Wang, Y.: Recursively enumerable reals and Chaitin Ω numbers. Theoretical Computer Science 255, 125–149 (2001)
Calude, C.S., Staiger, L.: On universal computably enumerable prefix codes. Mathematical Structures in Computer Science (accepted)
Chaitin, G.J.: A theory of program size formally identical to information theory. Journal of the Association for Computing Machinery 22, 329–340 (1975)
Chaitin, G.J.: Information-theoretic characterizations of recursive infinite strings. Theoretical Computer Science 2, 45–48 (1976)
Chaitin, G.J.: Algorithmic information theory. IBM Journal of Research and Development 21, 350–359+496 (1977)
Downey, R., Hirschfeldt, D., LaForte, G.: Randomness and reducibility. Journal of Computer and System Sciences 68, 96–114 (2004)
Kjos-Hanssen, B., Merkle, W., Stephan, F.: Kolmogorov Complexity and the Recursion Theorem. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 149–161. Springer, Heidelberg (2006)
Kolmogorov, A.N.: Three approaches to the definition of the concept “quantity of information”. Problemy Peredachi Informacii 1, 3–11 (1965)
Li, M., Vitányi, P.: An Introduction to Kolmogorov Complexity and Its Applications, 2nd edn. Springer, Heidelberg (1997)
Kučera, A., Slaman, T.: Randomness and recursive enumerability. SIAM Journal on Computing 31, 199–211 (2001)
Martin-Löf, P.: The definition of random sequences. Information and Control 9, 602–619 (1966)
Nies, A.: Computability and Randomness. Oxford University Press, Oxford (to appear)
Odifreddi, P.: Classical Recursion Theory. North-Holland, Amsterdam (1989)
Schnorr, C.P.: Process complexity and effective random tests. Journal of Computer and System Sciences 7, 376–388 (1973)
Solovay, R.: Draft of paper on Chaitin’s work Unpublished notes, 215 pages (1975)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Calude, C.S., Nies, A., Staiger, L., Stephan, F. (2008). Universal Recursively Enumerable Sets of Strings. In: Ito, M., Toyama, M. (eds) Developments in Language Theory. DLT 2008. Lecture Notes in Computer Science, vol 5257. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85780-8_13
Download citation
DOI: https://doi.org/10.1007/978-3-540-85780-8_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85779-2
Online ISBN: 978-3-540-85780-8
eBook Packages: Computer ScienceComputer Science (R0)