Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-19T02:52:58.299Z Has data issue: false hasContentIssue false
  • English
  • Français

A random set which only computes strongly jump-traceable c.e. sets

Published online by Cambridge University Press:  12 March 2014

Noam Greenberg
Noam Greenberg*
Affiliation:
School of Mathematics, Statistics and Operations Research, Victoria University of Wellington, Wellington, New Zealand, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We prove that there is a , 1-random set Y such that every computably enumerable set which is computable from Y is strongly jump-traceable.

We also show that for every order function h there is an ω-c.e. random set Y such that every computably enumerable set which is computable from Y is h-jump-traceable. This establishes a correspondence between rates of jump-traceability and computability from ω-c.e. random sets.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 76 , Issue 2 , June 2011 , pp. 700 - 718
Copyright
Copyright © Association for Symbolic Logic 2011

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

[1]Cholak, Peter, Downey, Rod, and Greenberg, Noam, Strong jump-traceabilty I: The computably enumerable case, Advances in Mathematics, vol. 217 (2008), no. 5, pp. 2045–2074.CrossRefGoogle Scholar
[2]Diamondstone, David, Promptness does not imply superlow cuppability, this Journal, vol. 74 (2009), no. 4, pp. 1264–1272.Google Scholar
[3]Figueira, Santiago, Nies, André, and Stephan, Frank, Lowness properties and approximations of the jump, Annals of Pure and Applied Logic, vol. 152 (2008), no. 1–3, pp. 51–66.CrossRefGoogle Scholar
[4]Greenberg, Noam, Hirschfeldt, Denis R., and Nies, André, Chracterizing the strongly jump-traceable sets via randomness, in preparation.Google Scholar
[5]Greenberg, Noam and Nies, André, Benign cost functions and lowness properties, this Journal, vol. 76 (2011), no. 1, pp. 289–312.Google Scholar
[6]Hirschfeldt, Denis R., Nies, André, and Stephan, Frank, Using random sets as oracles, Journal of the London Mathematical Society (2), vol. 75 (2007), no. 3, pp. 610–622.CrossRefGoogle Scholar
[7]Kučera, A., An alternative, priority-free, solution to Post's problem, Mathematical foundations of computer science, 1986 (Bratislava, 1986), Lecture Notes in Computer Science, vol. 233, Springer, Berlin, 1986, pp. 493–500.Google Scholar
[8]Miller, Joseph S. and Nies, André, Randomness and computability: open questions, The Bulletin of Symbolic Logic, vol. 12 (2006), no. 3, pp. 390–410.CrossRefGoogle Scholar
[9]Nies, André, Lowness properties and randomness, Advances in Mathematics, vol. 197 (2005), no. 1, pp. 274–305.CrossRefGoogle Scholar
[10]Solovay, R., draft of paper (or series of papers) related to Chaitin's work. IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 215 pages, 1975.Google Scholar