Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-26T09:09:40.940Z Has data issue: false hasContentIssue false
  • English
  • Français

EXACT PAIRS FOR THE IDEAL OF THE K-TRIVIAL SEQUENCES IN THE TURING DEGREES

Published online by Cambridge University Press:  18 August 2014

GEORGE BARMPALIAS  and
ROD G. DOWNEY
GEORGE BARMPALIAS
Affiliation:
STATE KEY LAB OF COMPUTER SCIENCE, INSTITUTE OF SOFTWARE, CHINESE ACADEMY OF SCIENCES, BEIJING 100190, CHINA SCHOOL OF MATHEMATICS, STATISTICS AND OPERATIONS RESEARCH, VICTORIA UNIVERSITY, WELLINGTON, NEW ZEALAND, E-mail: [email protected], URL: http://www.barmpalias.net
ROD G. DOWNEY
Affiliation:
SCHOOL OF MATHEMATICS, STATISTICS AND OPERATIONS RESEARCH, VICTORIA UNIVERSITY, P.O. BOX 600, WELLINGTON, NEW ZEALAND, E-mail: [email protected], URL: http://homepages.ecs.vuw.ac.nz/~downey
Get access Rights & Permissions [Opens in a new window]

Abstract

The K-trivial sets form an ideal in the Turing degrees, which is generated by its computably enumerable (c.e.) members and has an exact pair below the degree of the halting problem. The question of whether it has an exact pair in the c.e. degrees was first raised in [22, Question 4.2] and later in [25, Problem 5.5.8].

We give a negative answer to this question. In fact, we show the following stronger statement in the c.e. degrees. There exists a K-trivial degree d such that for all degrees a, b which are not K-trivial and a > d, b > d there exists a degree v which is not K-trivial and a > v, b > v. This work sheds light to the question of the definability of the K-trivial degrees in the c.e. degrees.

Keywords

03D2503D3268Q30Computably enumerableTuring degreesKolmogorov complexityK-trivial setsexact pairs
Type
Articles
Information
The Journal of Symbolic Logic , Volume 79 , Issue 3 , September 2014 , pp. 676 - 692
Copyright
Copyright © The Association for Symbolic Logic 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Barmpalias, George, Elementary differences between the degrees of unsolvability and the degrees of compressibility. Annals of Pure and Applied Logic, vol. 161 (2010), no. 7, pp. 923–934.Google Scholar
Barmpalias, George, On strings with trivial Kolmogorov complexity. International Journal of Software and Informatics, vol. 5(2011), no. 4, pp. 609–623.Google Scholar
Barmpalias, George, Universal computably enumerable sets and initial segment prefix-free complexity. Information and Computation, vol. 233 (2013), pp. 41–59.Google Scholar
Bienvenu, Laurent and Downey, Rod G., Kolmogorov complexity and Solovay functions, STACS (Albers, Susanne and Marion, Jean-Yves, editors), LIPIcs, vol. 3, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2009, pp. 147–158.Google Scholar
Barmpalias, George and Lewis, Andrew E.M., Chaitin’s halting probability and the compression of strings using oracles. Proceedings of the Royal Society A, vol. 467 (2011), pp. 2912–2926.Google Scholar
Bienvenu, Laurent, Merkle, Wolfgang, and Nies, André, Solovay functions and K-triviality. 28th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2011), Schloss Dagstuhl - LIPIcs 9, pp. 452–463, 2011.Google Scholar
Barmpalias, George and Nies, André, Upper bounds on ideals in the computably enumerable turing degrees. Annals of Pure and Applied Logic, vol. 162 (2011), no. 6, pp. 465–473.Google Scholar
Chaitin, Gregory J., A theory of program size formally identical to information theory. Journal of Association for Computing Machinery, vol. 22 (1975), pp. 329–340.Google Scholar
Calude, Christian, Hertling, Peter, Khoussainov, Bakhadyr, and Wang, Yongge, Recursively enumerable reals and Chaitin Ω numbers, Theoretical Computer Science, vol. 255 (2001), no. (1–2), pp. 125–149.Google Scholar
Downey, Rod G. and Hirshfeldt, Denis, Algorithmic Randomness and Complexity, Springer, Berlin 2010.Google Scholar
Downey, Rod G., Hirschfeldt, Denis R., Nies, André, and Stephan, Frank, Trivial reals, Proceedings of the 7th and 8th Asian Logic Conferences, Singapore University Press, Singapore, 2003, pp. 103–131.Google Scholar
Hölzl, Rupert, Kräling, Thorsten, and Merkle, Wolfgang, Time-bounded Kolmogorov complexity and solovay functions. Mathematical foundations of computer science 2009, vol. 5734, Lecture Notes in Computer Science, Springer, Berlin, 2009, pp. 392–402.Google Scholar
Kolmogorov, Andrey N., Three approaches to the definition of the concept “quantity of information.” Problemy Peredači Informacii, vol. 1 (1965), no. 1, pp. 3–11.Google Scholar
Kleene, Stephen C. and Post, Emil, The upper semi-lattice of degrees of recursive unsolvability. Annals of Mathematics(2), vol. 59 (1954), pp. 379–407.Google Scholar
Antonín Kučera and Theodore Slaman, Randomness and recursive enumerability. SIAM Journal on Computing, vol. 31 (2001), no. 1, pp. 199–211.Google Scholar
Antonín Kučera and Theodore Slaman, Low upper bounds of ideals, this Journal, vol. 74 (2009), no. 2, pp. 517–534.Google Scholar
Lachlan, Alistair H., Lower bounds for pairs of recursively enumerable degrees. Proceedings of the London Mathematical Society, vol. 16 (1966), pp. 537–569.Google Scholar
Levin, Leonid A., The concept of a random sequence. Doklady Akademii Nauk SSSR, vol. 212 (1973), pp. 548–550.Google Scholar
Li, Ming and Vitányi, Paul, An introduction to Kolmogorov complexity and its applications, second ed., Graduate Texts in Computer Science, Springer-Verlag, New York, 1997.Google Scholar
Miller, Joseph S., The K-degrees, low for K degrees, and weakly low for K sets. Notre Dame Journal of Formal Logic, vol. 50 (2010), no. 4, pp. 381–391.Google Scholar
Martin-Löf, Per, The definition of random sequences. Information and Control, vol. 9 (1966), pp. 602–619.Google Scholar
Miller, Joseph S. and Nies, André, Randomness and computability: open questions. Bulletin of Symbolic Logic, vol. 12 (2006), no. 3, pp. 390–410.Google Scholar
Nies, André, Reals which compute little Logic Colloquium ’02, Lecture notes in logic, vol. 27, Association of Symbolic Logic, La Jolla, CA, 2006, pp. 261–275CrossRefGoogle Scholar
Nies, André, Lowness properties and randomness. Advances in Mathematics, vol. 197 (2005), no. 1, pp. 274–305.Google Scholar
Nies, André, Computability and Randomness, Oxford University Press, Oxford, 2009.Google Scholar
Odifreddi, Piergiorgio G., Classical recursion theory, Vol. I, North-Holland, Amsterdam, 1989.Google Scholar
Shore, Richard A., The theory of the degrees below 0′. Journal of the London Mathematical Society, vol. 24 (1981), pp. 1–14.Google Scholar
Solomonoff, Ray J., A formal theory of inductive inference. I and II. Information and Control, vol. 7 (1964), pp. 1–22 and 224–254.Google Scholar
Solovay, Robert, Handwritten manuscript related to Chaitin’s work, IBM Thomas J. Watson Research Center, Yorktown Heights, New York, 1975, p. 215.Google Scholar
Spector, Clifford, On the degrees of recursive unsolvability. Annals of Mathematics (2), vol. 64 (1956), pp. 581–592.Google Scholar
Sterkenburg, Tom, Sequences with trivial initial segment complexity, MSc Dissertation, University of Amsterdam, 2011.Google Scholar
Mike Yates, C.E., A minimal pair of recursively enumerable degrees, this Journal, vol. 31 (1966), pp. 59–168.Google Scholar