Hostname: page-component-78c5997874-j824f Total loading time: 0 Render date: 2024-11-13T15:03:31.504Z Has data issue: false hasContentIssue false
  • English
  • Français

On very high degrees

Published online by Cambridge University Press:  12 March 2014

Keng Meng Ng
Keng Meng Ng*
Affiliation:
School of Mathematics, Statistics and Computer Science, Victoria University of Wellington, PO BOX 600, Wellington, New Zealand, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper we show that there is a pair of superhigh r.e. degree that forms a minimal pair. An analysis of the proof shows that a critical ingredient is the growth rates of certain order functions. This leads us to investigate certain high r.e. degrees, which resemble ∅′ very closely in terms of ∅′-jump traceability. In particular, we will construct an ultrahigh degree which is cappable.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 73 , Issue 1 , March 2008 , pp. 309 - 342
Copyright
Copyright © Association for Symbolic Logic 2008

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]Barmpalias, G. and Montalbán, A., A cappable almost everywhere dominating computably enumerable degree, Electronic Notes in Theoretical Computer Science, vol. 167 (2007), pp. 17–21.CrossRefGoogle Scholar
[2]Bickford, M. and Mills, C., Lowness properties of r.e. sets, Theoretical Computer Science, type-written unpublished manuscript.Google Scholar
[3]Chaitin, G., Information-theoretical characterizations of recursive infinite strings, Theoretical Computer Science, vol. 2 (1976), pp. 45–48.CrossRefGoogle Scholar
[4]Cholak, P., Downey, R., and Greenberg, N., Triviality and jump traceability, to appear.Google Scholar
[5]Cholak, P., Greenberg, N., and Miller, J., Uniform almost everywhere domination, this Journal, vol. 71 (2006), no. 3, pp. 1057–1072.Google Scholar
[6]Coles, R., Downey, R., Jockusch, C., and Laforte, G., Completing pseudojump operators, Annals of Pure and Applied Logic, vol. 136 (2005), pp. 297–333.CrossRefGoogle Scholar
[7]Dobrinen, N. and Simpson, S., Almost everywhere domination, this Journal, vol. 69 (2004), pp. 914–922.Google Scholar
[8]Downey, R., Hirschfeldt, D., Nibs, A., and Stephan, F., Trivial reals, Proceedings of the 7th and 8th Asian Logic Conferences, World Scientific, Singapore, (2003), pp. 103–131.Google Scholar
[9]Figueira, S., Nies, A., and Stephan, F., Lowness properties and approximations of the jump, Proceedings of the Twelfth Workshop of Logic, Language, Information and Computation (WoLLIC 2005), Electronic Lecture Notes in Theoretical Computer Science, vol. 143 (2006), pp. 45–57.Google Scholar
[10]Hirschfeldt, D., Nies, A., and Stephan, F., Using random sets as oracles, Journal of the London Mathematical Society, vol. 75 (2007), pp. 610–622.CrossRefGoogle Scholar
[11]Ishmukhametov, S., Weak recursive degrees and a problem of spector, Recursion theory and complexity (Arslanov, M. M. and Lempp, S., editors), de Gruyter Series in Logic and Its Applications, vol. 2, de Gruyter, 1997, pp. 81–87.Google Scholar
[12]Jockusch, C. and Shore, R., Pseudojump operators. I. The r.e. case, Transactions of the American Mathematical Society, vol. 275 (1983), no. 2, pp. 599–609.Google Scholar
[13]Kjös-Hanssen, B., Low for random reals and positive-measure domination, Proceedings of the American Mathematical Society, vol. 135 (2007), no. 11, pp. 3703–3709.CrossRefGoogle Scholar
[14]Kjös-Hanssen, B., Miller, J., and Solomon, R., Lowness notions, measure and domination, 2006, to appear.Google Scholar
[15]Kurtz, S., Randomness and genericity in the degrees of unsolvability, Ph.D. thesis, University of Illinois at Urbana-Champaign, 1981.Google Scholar
[16]Martin, D., Classes of recursively enumerable sets and degrees of unsolvability, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 12 (1966), pp. 295–310.CrossRefGoogle Scholar
[17]Nies, A., Reals which compute little, Technical Report 202, CDMTCS Research Report, The University of Auckland, 2002.Google Scholar
[18]Nies, A., Lowness properties and randomness, Advances in Mathematics, vol. 197 (2005), pp. 274–305.CrossRefGoogle Scholar
[19]Nies, A., Computability and randomness, Oxford University Press, 2006, to appear.Google Scholar
[20]Simpson, S., Almost everywhere domination and superhighness, Mathematical Logic Quarterly, vol. 53 (2007), pp. 462–482.CrossRefGoogle Scholar
[21]Solovay, R., Draft of paper (or series of papers) on Chaitin's work, unpublished notes, 215 pages, 1975.Google Scholar
[22]Terwijn, S. and Zambella, D., Algorithmic randomness and lowness, this Journal, vol. 66 (2001), pp. 1199–1205.Google Scholar