Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-17T17:57:00.119Z Has data issue: false hasContentIssue false
  • English
  • Français

Non-cupping, measure and computably enumerable splittings

Published online by Cambridge University Press:  01 February 2009

GEORGE BARMPALIAS  and
ANTHONY MORPHETT
GEORGE BARMPALIAS
Affiliation:
School of Mathematics, University of Leeds, LS2 9JT, United Kingdom
ANTHONY MORPHETT
Affiliation:
School of Mathematics, University of Leeds, LS2 9JT, United Kingdom Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We show that there is a computably enumerable function f (that is, computably approximable from below) that dominates almost all functions, and f ⊕ W is incomplete for all incomplete computably enumerable sets W. Our main methodology is the LR equivalence relation on reals: A ≡LRB if and only if the notions of A-randomness and B-randomness coincide. We also show that there are c.e. sets that cannot be split into two c.e. sets of the same LR degree. Moreover, a c.e. set is low for random if and only if it computes no c.e. set with this property.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 19 , Special Issue 1: Theory and Applications of Models of Computation (TAMC) , February 2009 , pp. 25 - 43
Copyright
Copyright © Cambridge University Press 2009

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

Barmpalias, G., Lewis, A. E. M. and Soskova, M. (2008) Randomness, lowness and degrees. J. Symbolic Logic 73 (2)559–577.CrossRefGoogle Scholar
Barmpalias, G., Lewis, A. E. M. and Stephan, F. (to appear) Π01 classes, LR degrees and Turing degrees. To appear in Annals of Pure and Applied Logic.Google Scholar
Barmpalias, G. and Montalbán, A. (2007) A cappable almost everywhere dominating computably enumerable degree. Electronic Notes in Theoretical Computer Science 167.CrossRefGoogle Scholar
Binns, S., Kjos-Hanssen, B., Lerman, M. and Solomon, R. (2006) On a conjecture of Dobrinen and Simpson concerning almost everywhere domination. J. Symbolic Logic 71 (1)119–136.CrossRefGoogle Scholar
Cholak, P., Greenberg, N. and Miller, J. S. (2006) Uniform almost everywhere domination. Journal of Symbolic Logic 71.CrossRefGoogle Scholar
Cooper, S. B., Lempp, S. and Watson, P. (1989) Weak density and cupping in the d-r.e. degrees. Israel Journal of Mathematics 67 137–152.CrossRefGoogle Scholar
de Leeuw, K., Moore, E. F., Shannon, C. E. and Shapiro, N. (1956) Computability by probabilistic machines. Automata studies, Annals of mathematics studies 34, Princeton University Press 183–212.Google Scholar
Dobrinen, N. L. and Simpson, S. G. (2004) Almost everywhere domination. J. Symbolic Logic 69 (3)914–922.CrossRefGoogle Scholar
Downey, R. G. and Hirschfeldt, D. (to appear) Algorithmic Randomness and Complexity, Springer-Verlag (in preparation).Google Scholar
Downey, R. G. and Slaman, T. A. (1989) Completely mitotic r.e. degrees. Ann. Pure Appl. Logic 41 (2)119–152.CrossRefGoogle Scholar
Downey, R. G. and Stob, M. (1993) Splitting theorems in recursion theory. Ann. Pure Appl. Logic 65 (1)1–106.CrossRefGoogle Scholar
Kjos-Hanssen, B. (2007) Low for random reals and positive-measure domination. Proceedings of the American Mathematical Society 135 3703–3709.CrossRefGoogle Scholar
Kjos-Hanssen, B., Miller, J. S. and Solomon, D. R. (unpublished) Lowness notions, measure and domination (unpublished draft).Google Scholar
Lachlan, A. H. (1967) The priority method I. Z. Math. Logik Grundlagen Math. 13 1–10.CrossRefGoogle Scholar
Ladner, R. E. (1973a) Mitotic Recursively Enumerable Sets. Journal of Symbolic Logic 38 (2)199–211.CrossRefGoogle Scholar
Ladner, R. E. (1973b) A Completely Mitotic Nonrecursive R. E. Degree. Transactions of the AMS 184 479–507.CrossRefGoogle Scholar
Li, A., Slaman, T. A. and Yang, Y. (unpublished) A nonlow2 c.e. degree which bounds no diamond bases (unpublished draft).Google Scholar
Martin, D. (unpublished) Measure, Category, and Degrees of Unsolvability (unpublished manuscript, dating from the late 60's).Google Scholar
Miller, D. P. (1981) High recursively enumerable degrees and the anti-cupping property. In: Lerman, M. et al. (eds.) Logic Year 1979-80. Springer-Verlag Lecture Notes in Mathematics 859.CrossRefGoogle Scholar
Nies, A. (2005) Lowness properties and randomness. Advances in Mathematics 197 274–305.CrossRefGoogle Scholar
Nies, A. (to appear) Computability and Randomness, Oxford University Press (in preparation).CrossRefGoogle Scholar
Sacks, G. (1963) Degrees of Unsolvability, Princeton University Press.Google Scholar
Simpson, S. G. (2007) Almost everywhere domination and superhighness. Mathematical Logic Quarterly 53 462–482.CrossRefGoogle Scholar
Soare, R. I. (1987) Recursively Enumerable Sets and Degrees, Springer-Verlag.CrossRefGoogle Scholar
Yu, L. and Yang, Y. (2005) On the definable ideal generated by nonbounding c.e. degrees. Journal of Symbolic Logic 20.Google Scholar