|
Difference randomness
Authors:
Johanna N. Y. Franklin and Keng Meng Ng
Journal:
Proc. Amer. Math. Soc. 139 (2011), 345-360
MSC (2010):
Primary 03D32
Posted:
July 30, 2010
MathSciNet review:
2729096
Full-text 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 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.
- 1.
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
(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), http://dx.doi.org/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), http://dx.doi.org/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), http://dx.doi.org/10.1112/jlms/jdm041
- 7.
Steven M. Kautz, Degrees of random sets, Ph.D. thesis, Cornell University, 1991.
- 8.
Bjørn Kjos-Hanssen, 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
Martin-Lö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), http://dx.doi.org/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), http://dx.doi.org/10.2178/jsl/1120224726
- 15.
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
(90d:03072)
- 16.
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
(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.
Claus-Peter
Schnorr, Zufälligkeit und Wahrscheinlichkeit. Eine
algorithmische Begründung der Wahrscheinlichkeitstheorie, Lecture
Notes in Mathematics, Vol. 218, Springer-Verlag, Berlin, 1971. MR 0414225
(54 #2328)
- 19.
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
(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, Martin-Löf Random and PA-complete 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 tt-degrees based on constructive measure theory, Comment. Math. Univ. Carolin. 29 (1988), no. 2, 233-247. 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, 167-192. 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, 1044-1052. MR 2251554 (2007h:03084)
- 5.
- Yu. L. Ershov, A hierarchy of sets, I, Algebra and Logic 7 (1968), no. 1, 212-232, English translation. Originally appearing in Algebra i Logika, 7(1):47-74, 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, 610-622. MR 2352724 (2008g:68051)
- 7.
- Steven M. Kautz, Degrees of random sets, Ph.D. thesis, Cornell University, 1991.
- 8.
- Bjørn Kjos-Hanssen, 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 Martin-Lö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
- 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, 515-535. MR 2140044 (2006i:68043)
- 15.
- Piergiorgio Odifreddi, Classical recursion theory, Studies in Logic and the Foundations of Mathematics, no. 125, North-Holland, 1989. MR 982269 (90d:03072)
- 16.
- -, Classical recursion theory, volume II, Studies in Logic and the Foundations of Mathematics, no. 143, North-Holland, 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.
- C.-P. Schnorr, Zufälligkeit und Wahrscheinlichkeit, Lecture Notes in Mathematics, vol. 218, Springer-Verlag, Heidelberg, 1971. MR 0414225 (54:2328)
- 19.
- Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, 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, Martin-Löf Random and PA-complete 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/S0002-9939-2010-10513-0
PII:
S 0002-9939(2010)10513-0
Received by editor(s):
March 3, 2010
Received by editor(s) in revised form:
March 26, 2010
Posted:
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.
|
