Difference randomness
HTML articles powered by AMS MathViewer
- by Johanna N. Y. Franklin and Keng Meng Ng PDF
- Proc. Amer. Math. Soc. 139 (2011), 345-360 Request permission
Abstract:
In this paper, we define new notions of randomness based on the difference hierarchy. We consider various ways in which a real can avoid all effectively given tests consisting of $n$-r.e. sets for some given $n$. In each case, the $n$-r.e. randomness hierarchy collapses for $n\geq 2$. In one case, we call the resulting notion difference randomness and show that it results in a class of random reals that is a strict subclass of the Martin-Löf random reals and a proper superclass of both the Demuth random and weakly 2-random reals. In particular, we are able to characterize the difference random reals as the Turing incomplete Martin-Löf random reals. We also provide a martingale characterization for difference randomness.References
- Osvald Demuth, Remarks on the structure of tt-degrees based on constructive measure theory, Comment. Math. Univ. Carolin. 29 (1988), no. 2, 233–247. MR 957390
- Rod Downey, Denis R. Hirschfeldt, Joseph S. Miller, and André Nies, Relativizing Chaitin’s halting probability, J. Math. Log. 5 (2005), no. 2, 167–192. MR 2188515, DOI 10.1142/S0219061305000468
- Rod Downey and Denis R. Hirschfeldt, Algorithmic Randomness and Complexity, to appear.
- Rod Downey, Andre Nies, Rebecca Weber, and Liang Yu, Lowness and $\Pi ^0_2$ nullsets, J. Symbolic Logic 71 (2006), no. 3, 1044–1052. MR 2251554, DOI 10.2178/jsl/1154698590
- Ju. L. Eršov, A certain hierarchy of sets. I, Algebra i Logika 7 (1968), no. 1, 47–74 (Russian). MR 0270911
- 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
- Steven M. Kautz, Degrees of random sets, Ph.D. thesis, Cornell University, 1991.
- Bjørn Kjos-Hanssen, Joseph S. Miller, and Reed Solomon, Lowness notions, measure, and domination, In progress.
- Stuart Alan Kurtz, Randomness and genericity in the degrees of unsolvability, Ph.D. thesis, University of Illinois, 1981.
- Per Martin-Löf, The definition of random sequences, Information and Control 9 (1966), 602–619. MR 223179
- Joseph S. Miller and André Nies, Randomness and computability: open questions, Bull. Symbolic Logic 12 (2006), no. 3, 390–410. MR 2248590
- 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, 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, Frank Stephan, and Sebastiaan A. Terwijn, Randomness, relativization and Turing degrees, J. Symbolic Logic 70 (2005), no. 2, 515–535. MR 2140044, DOI 10.2178/jsl/1120224726
- Piergiorgio Odifreddi, Classical recursion theory, Studies in Logic and the Foundations of Mathematics, vol. 125, North-Holland Publishing Co., Amsterdam, 1989. The theory of functions and sets of natural numbers; With a foreword by G. E. Sacks. MR 982269
- P. G. Odifreddi, Classical recursion theory. Vol. II, Studies in Logic and the Foundations of Mathematics, vol. 143, North-Holland Publishing Co., Amsterdam, 1999. MR 1718169
- Hilary Putnam, Trial and error predicates and the solution to a problem of Mostowski, J. Symbolic Logic 30 (1965), 49–57. MR 195725, DOI 10.2307/2270581
- Claus-Peter Schnorr, Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie, Lecture Notes in Mathematics, Vol. 218, Springer-Verlag, Berlin-New York, 1971. MR 0414225
- Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR 882921, DOI 10.1007/978-3-662-02460-7
- Robert M. Solovay, Draft of a paper (or series of papers) on Chaitin’s work, unpublished manuscript, May 1975.
- Frank Stephan, Martin-Löf Random and PA-complete Sets, Tech. Report 58, Matematisches Institut, Universität Heidelberg, Heidelberg, 2002.
- Yongge Wang, Randomness and complexity, Ph.D. thesis, University of Heidelberg, 1996.
Additional Information
- Johanna N. Y. Franklin
- Affiliation: Department of Pure Mathematics, University of Waterloo, 200 University Avenue West, Waterloo, Ontario, Canada N2L 3G1
- Address at time of publication: Department of Mathematics, 6188 Kemeny Hall, Dartmouth College, Hano- ver, New Hampshire 03755
- Email: jfranklin@math.uwaterloo.ca, johannaf@gauss.dartmouth.edu
- Keng Meng Ng
- Affiliation: Department of Mathematics, University of Wisconsin, 480 Lincoln Drive, Madison, Wisconsin 53706
- MR Author ID: 833062
- Email: selwynng@math.wisc.edu
- Received by editor(s): March 3, 2010
- Received by editor(s) in revised form: March 26, 2010
- Published electronically: July 30, 2010
- Additional Notes: The authors thank Richard Shore and André Nies for their helpful comments.
- Communicated by: Julia Knight
- © Copyright 2010
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Proc. Amer. Math. Soc. 139 (2011), 345-360
- MSC (2010): Primary 03D32
- DOI: https://doi.org/10.1090/S0002-9939-2010-10513-0
- MathSciNet review: 2729096