Difference randomness
Authors:
Johanna N. Y. Franklin and Keng Meng Ng
Journal:
Proc. Amer. Math. Soc. 139 (2011), 345360
MSC (2010):
Primary 03D32
Published electronically:
July 30, 2010
MathSciNet review:
2729096
Fulltext PDF
Abstract 
References 
Similar Articles 
Additional Information
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 r.e. sets for some given . In each case, the r.e. randomness hierarchy collapses for . 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 MartinLöf random reals and a proper superclass of both the Demuth random and weakly 2random reals. In particular, we are able to characterize the difference random reals as the Turing incomplete MartinLöf random reals. We also provide a martingale characterization for difference randomness.
 1.
Osvald
Demuth, Remarks on the structure of ttdegrees based on
constructive measure theory, Comment. Math. Univ. Carolin.
29 (1988), no. 2, 233–247. MR 957390
(89k:03049)
 2.
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
(2007e:68031), 10.1142/S0219061305000468
 3.
Rod Downey and Denis R. Hirschfeldt, Algorithmic Randomness and Complexity, to appear.
 4.
Rod
Downey, Andre
Nies, Rebecca
Weber, and Liang
Yu, Lowness and Π⁰₂ nullsets, J. Symbolic
Logic 71 (2006), no. 3, 1044–1052. MR 2251554
(2007h:03084), 10.2178/jsl/1154698590
 5.
Ju.
L. Eršov, A certain hierarchy of sets. I, Algebra i
Logika 7 (1968), no. 1, 47–74 (Russian). MR 0270911
(42 #5794)
 6.
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
(2008g:68051), 10.1112/jlms/jdm041
 7.
Steven M. Kautz, Degrees of random sets, Ph.D. thesis, Cornell University, 1991.
 8.
Bjørn KjosHanssen, Joseph S. Miller, and Reed Solomon, Lowness notions, measure, and domination, In progress.
 9.
Stuart Alan Kurtz, Randomness and genericity in the degrees of unsolvability, Ph.D. thesis, University of Illinois, 1981.
 10.
Per
MartinLöf, The definition of random sequences,
Information and Control 9 (1966), 602–619. MR 0223179
(36 #6228)
 11.
Joseph
S. Miller and André
Nies, Randomness and computability: open questions, Bull.
Symbolic Logic 12 (2006), no. 3, 390–410. MR 2248590
(2007c:03059)
 12.
André
Nies, Lowness properties and randomness, Adv. Math.
197 (2005), no. 1, 274–305. MR 2166184
(2006j:68052), 10.1016/j.aim.2004.10.006
 13.
André
Nies, Computability and randomness, Oxford Logic Guides,
vol. 51, Oxford University Press, Oxford, 2009. MR 2548883
(2011i:03003)
 14.
André
Nies, Frank
Stephan, and Sebastiaan
A. Terwijn, Randomness, relativization and Turing degrees, J.
Symbolic Logic 70 (2005), no. 2, 515–535. MR 2140044
(2006i:68043), 10.2178/jsl/1120224726
 15.
Piergiorgio
Odifreddi, Classical recursion theory, Studies in Logic and
the Foundations of Mathematics, vol. 125, NorthHolland Publishing
Co., Amsterdam, 1989. The theory of functions and sets of natural numbers;
With a foreword by G. E. Sacks. MR 982269
(90d:03072)
 16.
P.
G. Odifreddi, Classical recursion theory. Vol. II, Studies in
Logic and the Foundations of Mathematics, vol. 143, NorthHolland
Publishing Co., Amsterdam, 1999. MR 1718169
(2001b:03040)
 17.
Hilary
Putnam, Trial and error predicates and the solution to a problem of
Mostowski, J. Symbolic Logic 30 (1965), 49–57.
MR
0195725 (33 #3923)
 18.
ClausPeter
Schnorr, Zufälligkeit und Wahrscheinlichkeit. Eine
algorithmische Begründung der Wahrscheinlichkeitstheorie, Lecture
Notes in Mathematics, Vol. 218, SpringerVerlag, BerlinNew York, 1971. MR 0414225
(54 #2328)
 19.
Robert
I. Soare, Recursively enumerable sets and degrees,
Perspectives in Mathematical Logic, SpringerVerlag, Berlin, 1987. A study
of computable functions and computably generated sets. MR 882921
(88m:03003)
 20.
Robert M. Solovay, Draft of a paper (or series of papers) on Chaitin's work, unpublished manuscript, May 1975.
 21.
Frank Stephan, MartinLöf Random and PAcomplete Sets, Tech. Report 58, Matematisches Institut, Universität Heidelberg, Heidelberg, 2002.
 22.
Yongge Wang, Randomness and complexity, Ph.D. thesis, University of Heidelberg, 1996.
 1.
 Osvald Demuth, Remarks on the structure of ttdegrees based on constructive measure theory, Comment. Math. Univ. Carolin. 29 (1988), no. 2, 233247. MR 957390 (89k:03049)
 2.
 R. Downey, D. Hirschfeldt, J. Miller, and A. Nies, Relativizing Chaitin's halting probability, J. Math. Log. 5 (2005), no. 2, 167192. MR 2188515 (2007e:68031)
 3.
 Rod Downey and Denis R. Hirschfeldt, Algorithmic Randomness and Complexity, to appear.
 4.
 Rod Downey, André Nies, Rebecca Weber, and Liang Yu, Lowness and nullsets, J. Symbolic Logic 71 (2006), no. 3, 10441052. MR 2251554 (2007h:03084)
 5.
 Yu. L. Ershov, A hierarchy of sets, I, Algebra and Logic 7 (1968), no. 1, 212232, English translation. Originally appearing in Algebra i Logika, 7(1):4774, 1968 (Russian). MR 0270911 (42:5794)
 6.
 Denis R. Hirschfeldt, André Nies, and Frank Stephan, Using random sets as oracles, J. Lond. Math. Soc. (2) 75 (2007), no. 3, 610622. MR 2352724 (2008g:68051)
 7.
 Steven M. Kautz, Degrees of random sets, Ph.D. thesis, Cornell University, 1991.
 8.
 Bjørn KjosHanssen, Joseph S. Miller, and Reed Solomon, Lowness notions, measure, and domination, In progress.
 9.
 Stuart Alan Kurtz, Randomness and genericity in the degrees of unsolvability, Ph.D. thesis, University of Illinois, 1981.
 10.
 Per MartinLöf, The definition of random sequences, Information and Control 9 (1966), 602619. MR 0223179 (36:6228)
 11.
 Joseph S. Miller and André Nies, Randomness and computability: Open questions, Bull. Symbolic Logic 12 (2006), no. 3, 390410. MR 2248590 (2007c:03059)
 12.
 André Nies, Lowness properties and randomness, Adv. Math. 197 (2005), no. 1, 274305. MR 2166184
 13.
 , Computability and randomness, Oxford Logic Guides, Vol. 51, Oxford Univ. Press, Oxford, 2009. MR 2548883
 14.
 André Nies, Frank Stephan, and Sebastiaan A. Terwijn, Randomness, relativization and Turing degrees, J. Symbolic Logic 70 (2005), no. 2, 515535. MR 2140044 (2006i:68043)
 15.
 Piergiorgio Odifreddi, Classical recursion theory, Studies in Logic and the Foundations of Mathematics, no. 125, NorthHolland, 1989. MR 982269 (90d:03072)
 16.
 , Classical recursion theory, volume II, Studies in Logic and the Foundations of Mathematics, no. 143, NorthHolland, 1999. MR 1718169 (2001b:03040)
 17.
 Hilary Putnam, Trial and error predicates and the solution to a problem of Mostowski, J. Symbolic Logic 30 (1965), 4957. MR 0195725 (33:3923)
 18.
 C.P. Schnorr, Zufälligkeit und Wahrscheinlichkeit, Lecture Notes in Mathematics, vol. 218, SpringerVerlag, Heidelberg, 1971. MR 0414225 (54:2328)
 19.
 Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, SpringerVerlag, 1987. MR 882921 (88m:03003)
 20.
 Robert M. Solovay, Draft of a paper (or series of papers) on Chaitin's work, unpublished manuscript, May 1975.
 21.
 Frank Stephan, MartinLöf Random and PAcomplete Sets, Tech. Report 58, Matematisches Institut, Universität Heidelberg, Heidelberg, 2002.
 22.
 Yongge Wang, Randomness and complexity, Ph.D. thesis, University of Heidelberg, 1996.
Similar Articles
Retrieve articles in Proceedings of the American Mathematical Society
with MSC (2010):
03D32
Retrieve articles in all journals
with MSC (2010):
03D32
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
Email:
selwynng@math.wisc.edu
DOI:
http://dx.doi.org/10.1090/S000299392010105130
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
Article copyright:
© Copyright 2010
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.
