Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



When van Lambalgen's Theorem fails

Author: Liang Yu
Journal: Proc. Amer. Math. Soc. 135 (2007), 861-864
MSC (2000): Primary 03D28, 68Q30
Published electronically: September 15, 2006
MathSciNet review: 2262883
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We prove that van Lambalgen's Theorem fails for both Schnorr randomness and computable randomness.

References [Enhancements On Off] (What's this?)

  • 1. M. M. Arslanov, Some generalizations of a fixed-point theorem, Izv. Vyssh. Uchebn. Zaved. Mat. 5 (1981), 9–16 (Russian). MR 630478
  • 2. G. J. Chaitin, Information, randomness & incompleteness, 2nd ed., World Scientific Series in Computer Science, vol. 8, World Scientific Publishing Co., Inc., River Edge, NJ, 1990. Papers on algorithmic information theory. MR 1153671
  • 3. R. Downey and D. Hirschfeldt.
    Algorithmic randomness and complexity.
    Springer-Verlag, Berlin.
    To appear.
  • 4. Rodney G. Downey and Evan J. Griffiths, Schnorr randomness, J. Symbolic Logic 69 (2004), no. 2, 533–554. MR 2058188, 10.2178/jsl/1082418542
  • 5. Rodney G. Downey, Denis R. Hirschfeldt, André Nies, and Sebastiaan A. Terwijn.
    Calibrating randomness.
    Bull. Symbolic Logic.
    To appear.
  • 6. Donald A. Martin, Classes of recursively enumerable sets and degrees of unsolvability, Z. Math. Logik Grundlagen Math. 12 (1966), 295–310. MR 0224469
  • 7. Per Martin-Löf, The definition of random sequences, Information and Control 9 (1966), 602–619. MR 0223179
  • 8. André Nies, Frank Stephan, and Sebastiaan A. Terwijn, Randomness, relativization and Turing degrees, J. Symbolic Logic 70 (2005), no. 2, 515–535. MR 2140044, 10.2178/jsl/1120224726
  • 9. C.-P. Schnorr, A unified approach to the definition of random sequences, Math. Systems Theory 5 (1971), 246–258. MR 0354328
  • 10. M. van Lambalgen.
    Random sequences.
    Ph.D. Dissertation, University of Amsterdam, 1987.

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 03D28, 68Q30

Retrieve articles in all journals with MSC (2000): 03D28, 68Q30

Additional Information

Liang Yu
Affiliation: Department of Mathematics, Faculty of Science, National University of Singapore, Lower Kent Ridge Road, Singapore 117543
Address at time of publication: Institute of Mathematical Science, Nanjing University, 210093, JiangSu Province, People’s Republic of China

Received by editor(s): July 11, 2005
Received by editor(s) in revised form: August 21, 2005, and October 17, 2005
Published electronically: September 15, 2006
Additional Notes: The author was supported by a postdoctoral fellowship from computability theory and algorithmic randomness R-146-000-054-123 in Singapore, NSF of China No.10471060 and No.10420130638. The author thanks the referee for kindly correcting numerous English errors.
Communicated by: Julia Knight
Article copyright: © Copyright 2006 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.