Hostname: page-component-78c5997874-8bhkd Total loading time: 0 Render date: 2024-11-16T16:11:14.197Z Has data issue: false hasContentIssue false
  • English
  • Français

The importance of Π1 0 classes in effective randomness

Published online by Cambridge University Press:  12 March 2014

George Barmpalias ,
Andrew E.M. Lewis  and
Keng Meng Ng
George Barmpalias
Affiliation:
School of Mathematics, Statistics, and Computer Science, Victoria University, Po Box 600 Wellington, New Zealand, E-mail: [email protected], URL: http.//www.mcs.vuw.ac.nz/~georgeb/
Andrew E.M. Lewis
Affiliation:
School of Mathematics, University of Leeds, Leeds LS2 9JT, UK, E-mail: [email protected], URL: http://www.aemlewis.co.uk
Keng Meng Ng
Affiliation:
School of Mathematics, Statistics, and Computer Science, Victoria University, Po Box 600 Wellington, New Zealand, E-mail: [email protected], URL: http://www.mcs.vuw.ac.nz/~selwyn/
Get access Rights & Permissions [Opens in a new window]

Abstract

We prove a number of results in effective randomness, using methods in which Π1 0 classes play an essential role. The results proved include the fact that every PA Turing degree is the join of two random Turing degrees, and the existence of a minimal pair of LR degrees below the LR degree of the halting problem.

Keywords

Π1 0 classesMartin-Löf randomnessPeano ArithmeticK-trivialsTuring degreesLR degrees
Type
Research Article
Information
The Journal of Symbolic Logic , Volume 75 , Issue 1 , March 2010 , pp. 387 - 400
Copyright
Copyright © Association for Symbolic Logic 2010

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

[AK00] Ash, C. J. and Knight, J., Computable structures and the hyperarithmetical hierarchy, Studies' in Logic and the Foundations of Mathematics, vol. 144, North-Holland Publishing Co., Amsterdam, 2000.Google Scholar
[Bar06] Barmpalias, George, Random non-cupping revisited, Journal of Complexity, vol. 22 (2006), no. 6, pp. 850–857.Google Scholar
[BLS08a] Barmpalias, George, Lewis, Andrew E. M., and Soskova, Mariya, Randomness, lowness and degrees, this Journal, vol. 73 (2008), no. 2, pp. 559–577.Google Scholar
[BLS08b] Barmpalias, George, Lewis, Andrew E. M., and Stephan, Frank, Π1 0 classes, LR degrees and Turing degrees, Annals of Pure and Applied Logic, vol. 156, Issuel (2008), pp. 21–38.Google Scholar
[JS72a] Jr.Jockusch, Carl G. and Soare, Robert I., Degrees of members of Π1 0 classes, Pacific Journal of Mathematics, vol. 40 (1972), pp. 605–616.Google Scholar
[JS72b] Jr.Jockusch, Carl G. and Soare, Robert I., Π1 0 classes and degrees of theories, Transactions of the American Mathematical Society, vol. 173 (1972), pp. 33–56.Google Scholar
[Cen99] Cenzer, Douglas, Π1 0 classes in computability theory, Handbook of computability theory, Studies in Logic and the Foundations of Mathematics, vol. 140, North-Holland, Amsterdam, 1999, pp. 37–85.Google Scholar
[CS07] Cole, Joshua A. and Simpson, Stephen G., Mass problems and hyperarithmeticity, Journal of Mathematical Logic, vol. 7 (2007), no. 2, pp. 125–143.Google Scholar
[DHMN05] Downey, Rod, Hirschfeldt, Denis R., Miller, Joseph S., and Nies, André, Relativizing Chaitins halting probability, Journal of Mathematical Logic, vol. 5 (2005), no. 2, pp. 167–192.Google Scholar
[DHNT06] Downey, Rod, Hirschfeldt, Denis R., Nies, André, and Terwijn, Sebastiaan A., Calibrating randomness, Bullin of Symbolic Logic, vol. 12 (2006), no. 3, pp. 411–491.Google Scholar
[DH09] Downey, Rod and Hirshfeldt, Denis R., Algorithmic randomness and complexity, Springer-Verlag, 2009, in preparation.Google Scholar
[FMN] Figueira, Santiago, Miller, Joseph, and Nies, André, Indifferent sets, to appear.Google Scholar
[KH07] Kjos-Hanssen, Bjørn, Low for random reals and positive-measure domination, Proceedings of the American Mathematical Society, vol. 135 (2007), no. 11, pp. 3703–3709, electronic.Google Scholar
[Kuč85] Kučera, Antonín, Measure, Π1 0-classes and complete extensions of PA, Recursion theory week (Oberwolfach, 1984), Lecture Notes in Mathematics, vol. 1141, Springer, Berlin, 1985, pp. 245–259.Google Scholar
[Kuč86] Kučera, Antonín, 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
[KS07] Kučera, Antonín and Slaman, Theodore, Low upper bounds of ideals, Preprint, 2007.Google Scholar
[Kur81] Kurtz, S., Randomness andgenericity in the degrees of unsolvability, Ph.D. thesis, University of Illinois, Urbana, 1981.Google Scholar
[ML66] Martin-Löf, Per, The definition of random sequences, Information and Control, vol. 9 (1966), pp. 602–619.Google Scholar
[Mil] Miller, Joseph S., The K-degrees, low for K degrees, and weakly low for K sets, preprint.Google Scholar
[Nie05a] Nies, André, Eliminating concepts, Proceedings of the IMS workshop on computational aspects of infinity, Singapore, 2005, in press.Google Scholar
[Nie05b] Nies, André, Lowness properties and randomness, Advances in Mathematics, vol. 197 (2005), no. 1, pp. 274–305.Google Scholar
[Nie07] Nies, André, Non-cupping and randomness, Proceedings of the American Mathematical Society, vol. 135 (2007), no. 3, pp. 837–844, electronic.Google Scholar
[Nie09] Nies, André, Computability and randomness, Oxford University Press, 2009.Google Scholar
[Odi89] Odifreddi, P. G., Classical recursion theory, vol. I, North-Holland Publishing Co., Amsterdam, 1989.Google Scholar
[Sac63] Sacks, Gerald E., Degrees of unsolvability, Princeton University Press, Princeton, N.J., 1963.Google Scholar
[Sim07] Simpson, Stephen G., Almost everywhere domination and superhighness, Mathematical Logic Quarterly, vol. 53 (2007), no. 4–5, pp. 462–482.Google Scholar
[Ste06] Stephan, Frank, Martin-Löf random and PA-complete sets, Logic colloquium '02, Lecture Notes in Logic, vol. 27, Association for Symbolic Logic, La Jolla, CA, 2006, pp. 342–348.Google Scholar
[Sti72] Stillwell, John, Decidability of the “almost all” theory of degrees, this Journal, vol. 37 (1972), pp. 501–506.Google Scholar