×

zbMATH — the first resource for mathematics

Difference randomness. (English) Zbl 1214.03029
In the paper under review, the authors introduce a new randomness notion called difference randomness. They prove the following results: 5mm
(1)
A real is difference random if and only if it is a Martin-Löf random real and Turing incomplete if and only if no difference martingale succeeds on it.
(2)
A recursively enumerable set \(A\) is a base for difference randomness if and only if it is Martin-Löf coverable;
(3)
Lowness for difference randomness is equivalent to non-weak-Martin-Löf cuppability.
Reviewer: Liang Yu (Nanjing)

MSC:
03D32 Algorithmic randomness and dimension
PDF BibTeX XML Cite
Full Text: DOI
References:
[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. · Zbl 0646.03039
[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. · Zbl 1093.03025 · doi:10.1142/S0219061305000468 · doi.org
[3] Rod Downey and Denis R. Hirschfeldt, Algorithmic Randomness and Complexity, to appear. · Zbl 1221.68005
[4] Rod Downey, Andre Nies, Rebecca Weber, and Liang Yu, Lowness and \Pi \(^{0}\)\(_{2}\) nullsets, J. Symbolic Logic 71 (2006), no. 3, 1044 – 1052. · Zbl 1112.03040 · doi:10.2178/jsl/1154698590 · doi.org
[5] Ju. L. Eršov, A certain hierarchy of sets. I, Algebra i Logika 7 (1968), no. 1, 47 – 74 (Russian).
[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. · Zbl 1128.03036 · doi:10.1112/jlms/jdm041 · doi.org
[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. · Zbl 1262.03068
[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. · Zbl 0244.62008
[11] Joseph S. Miller and André Nies, Randomness and computability: open questions, Bull. Symbolic Logic 12 (2006), no. 3, 390 – 410. · Zbl 1169.03033
[12] André Nies, Lowness properties and randomness, Adv. Math. 197 (2005), no. 1, 274 – 305. · Zbl 1141.03017 · doi:10.1016/j.aim.2004.10.006 · doi.org
[13] André Nies, Computability and randomness, Oxford Logic Guides, vol. 51, Oxford University Press, Oxford, 2009. · Zbl 1169.03034
[14] André Nies, Frank Stephan, and Sebastiaan A. Terwijn, Randomness, relativization and Turing degrees, J. Symbolic Logic 70 (2005), no. 2, 515 – 535. · Zbl 1090.03013 · doi:10.2178/jsl/1120224726 · doi.org
[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. · Zbl 0661.03029
[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. · Zbl 0931.03057
[17] Hilary Putnam, Trial and error predicates and the solution to a problem of Mostowski, J. Symbolic Logic 30 (1965), 49 – 57. · Zbl 0193.30102 · doi:10.2307/2270581 · doi.org
[18] 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. · Zbl 0232.60001
[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. · Zbl 0667.03030
[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. · Zbl 1165.03336
[22] Yongge Wang, Randomness and complexity, Ph.D. thesis, University of Heidelberg, 1996. · Zbl 0858.03041
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.