Inherent enumerability of strong jump-traceability
HTML articles powered by AMS MathViewer
- by David Diamondstone, Noam Greenberg and Daniel D. Turetsky PDF
- Trans. Amer. Math. Soc. 367 (2015), 1771-1796 Request permission
Abstract:
We show that every strongly jump-traceable set obeys every benign cost function. Moreover, we show that every strongly jump-traceable set is computable from a computably enumerable strongly jump-traceable set. This allows us to generalise properties of c.e. strongly jump-traceable sets to all such sets. For example, the strongly jump-traceable sets induce an ideal in the Turing degrees; the strongly jump-traceable sets are precisely those that are computable from all superlow Martin-Löf random sets; the strongly jump-traceable sets are precisely those that are a base for $\mathrm {Demuth}_{\mathrm {BLR}}$ randomness; and strong jump-traceability is equivalent to strong superlowness.References
- George Barmpalias, Rod Downey, and Noam Greenberg, $K$-trivial degrees and the jump-traceability hierarchy, Proc. Amer. Math. Soc. 137 (2009), no. 6, 2099–2109. MR 2480292, DOI 10.1090/S0002-9939-09-09761-5
- Laurent Bienvenu, Adam R. Day, Noam Greenberg, Antonín Kučera, Joseph S. Miller, André Nies, and Dan Turetsky, Computing $K$-trivial sets by incomplete random sets, Bull. Symb. Log. 20 (2014), no. 1, 80–90. MR 3230826, DOI 10.1017/bsl.2013.3
- Laurent Bienvenu, Rod Downey, Noam Greenberg, André Nies, and Dan Turetsky, Characterizing lowness for Demuth randomness, J. Symb. Log. 79 (2014), no. 2, 526–560. MR 3224979, DOI 10.1017/jsl.2013.21
- Gregory J. Chaitin, Information-theoretic characterizations of recursive infinite strings, Theoret. Comput. Sci. 2 (1976), no. 1, 45–48. MR 413595, DOI 10.1016/0304-3975(76)90005-0
- Gregory J. Chaitin, Nonrecursive infinite strings with simple initial segments, IBM Journal of Research and Development 21 (1977), 350–359.
- Peter Cholak, Rod Downey, and Noam Greenberg, Strong jump-traceabilty. I. The computably enumerable case, Adv. Math. 217 (2008), no. 5, 2045–2074. MR 2388085, DOI 10.1016/j.aim.2007.09.008
- Rod Downey and Noam Greenberg, Strong jump-traceability II: $K$-triviality, Israel J. Math. 191 (2012), no. 2, 647–665. MR 3011490, DOI 10.1007/s11856-011-0217-z
- Rodney G. Downey and Denis R. Hirschfeldt, Algorithmic randomness and complexity, Theory and Applications of Computability, Springer, New York, 2010. MR 2732288, DOI 10.1007/978-0-387-68441-3
- Rod G. Downey, Denis R. Hirschfeldt, André Nies, and Frank Stephan, Trivial reals, Proceedings of the 7th and 8th Asian Logic Conferences, Singapore Univ. Press, Singapore, 2003, pp. 103–131. MR 2051976, DOI 10.1142/9789812705815_{0}005
- Rod Downey, Denis R. Hirschfeldt, André Nies, and Sebastiaan A. Terwijn, Calibrating randomness, Bull. Symbolic Logic 12 (2006), no. 3, 411–491. MR 2248591
- Santiago Figueira, André Nies, and Frank Stephan, Lowness properties and approximations of the jump, Ann. Pure Appl. Logic 152 (2008), no. 1-3, 51–66. MR 2397489, DOI 10.1016/j.apal.2007.11.002
- Noam Greenberg, Denis R. Hirschfeldt, and André Nies, Characterizing the strongly jump-traceable sets via randomness, Adv. Math. 231 (2012), no. 3-4, 2252–2293. MR 2964638, DOI 10.1016/j.aim.2012.06.005
- Noam Greenberg and André Nies, Benign cost functions and lowness properties, J. Symbolic Logic 76 (2011), no. 1, 289–312. MR 2791349, DOI 10.2178/jsl/1294171001
- Noam Greenberg and Daniel D. Turetsky, Strong jump-traceability and Demuth randomness, Proc. Lond. Math. Soc. (3) 108 (2014), no. 3, 738–779. MR 3180595, DOI 10.1112/plms/pdt040
- Denis R. Hirschfeldt, André Nies, and Frank Stephan, Using random sets as oracles, J. Lond. Math. Soc. (2) 75 (2007), no. 3, 610–622. MR 2352724, DOI 10.1112/jlms/jdm041
- Rupert Hölzl, Thorsten Kräling, and Wolfgang Merkle, Time-bounded Kolmogorov complexity and Solovay functions, Mathematical foundations of computer science 2009, Lecture Notes in Comput. Sci., vol. 5734, Springer, Berlin, 2009, pp. 392–402. MR 2539508, DOI 10.1007/978-3-642-03816-7_{3}4
- Antonín Kučera and André Nies, Demuth randomness and computational complexity, Ann. Pure Appl. Logic 162 (2011), no. 7, 504–513. MR 2781092, DOI 10.1016/j.apal.2011.01.004
- Joseph S. Miller and André Nies, Randomness and computability: open questions, Bull. Symbolic Logic 12 (2006), no. 3, 390–410. MR 2248590
- Webb Miller and D. A. Martin, The degrees of hyperimmune sets, Z. Math. Logik Grundlagen Math. 14 (1968), 159–166. MR 228341, DOI 10.1002/malq.19680140704
- Keng Meng Ng, On strongly jump traceable reals, Ann. Pure Appl. Logic 154 (2008), no. 1, 51–69. MR 2413929, DOI 10.1016/j.apal.2007.11.014
- André Nies, Lowness properties and randomness, Adv. Math. 197 (2005), no. 1, 274–305. MR 2166184, DOI 10.1016/j.aim.2004.10.006
- André Nies, Eliminating concepts, Computational prospects of infinity. Part II. Presented talks, Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap., vol. 15, World Sci. Publ., Hackensack, NJ, 2008, pp. 225–247. MR 2449467, DOI 10.1142/9789812796554_{0}012
- André Nies, Computability and randomness, Oxford Logic Guides, vol. 51, Oxford University Press, Oxford, 2009. MR 2548883, DOI 10.1093/acprof:oso/9780199230761.001.0001
- André Nies, Computably enumerable sets below random sets, Ann. Pure Appl. Logic 163 (2012), no. 11, 1596–1610. MR 2959662, DOI 10.1016/j.apal.2011.12.011
- André Nies, Calculus of cost functions. In preparation.
- Jean Raisonnier, A mathematical proof of S. Shelah’s theorem on the measure problem and related results, Israel J. Math. 48 (1984), no. 1, 48–56. MR 768265, DOI 10.1007/BF02760523
- Robert M. Solovay, Draft of paper (or series of papers) related to Chaitin’s work. IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 215 pages, 1975.
- Sebastiaan A. Terwijn, Computability and Measure. PhD thesis, University of Amsterdam, 1998.
- Sebastiaan A. Terwijn and Domenico Zambella, Computational randomness and lowness, J. Symbolic Logic 66 (2001), no. 3, 1199–1205. MR 1856736, DOI 10.2307/2695101
Additional Information
- David Diamondstone
- Affiliation: Department of Mathematics, University of Wisconsin, Madison, Wisconsin 53706
- Email: ddiamondstone@gmail.com
- Noam Greenberg
- Affiliation: School of Mathematics, Statistics and Operations Research, Victoria University of Wellington, Wellington, New Zealand
- MR Author ID: 757288
- ORCID: 0000-0003-2917-3848
- Email: greenberg@msor.vuw.ac.nz
- Daniel D. Turetsky
- Affiliation: Kurt Gödel Research Center, University of Vienna, 1090 Vienna, Austria
- MR Author ID: 894314
- Email: turetsd4@univie.ac.at
- Received by editor(s): October 25, 2011
- Received by editor(s) in revised form: January 27, 2013
- Published electronically: November 12, 2014
- Additional Notes: All authors were supported by the Marsden Fund of New Zealand, the first and the third as postdoctoral fellows. The second author was also supported by a Rutherford Discovery Fellowship.
- © Copyright 2014
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Trans. Amer. Math. Soc. 367 (2015), 1771-1796
- MSC (2010): Primary 03D25, 03D28, 03D32
- DOI: https://doi.org/10.1090/S0002-9947-2014-06089-3
- MathSciNet review: 3286498