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

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):9-16, 1981. MR 0630478 (82j:03050)
  • 2. G. J. Chaitin.
    Information, randomness & incompleteness, volume 8 of World Scientific Series in Computer Science.
    World Scientific Publishing Co. Inc., River Edge, NJ, 1990. MR 1153671 (92m:01094)
  • 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(2):533-554, 2004. MR 2058188 (2005b:03106)
  • 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:295-310, 1966. MR 0224469 (37:68)
  • 7. Per Martin-Löf.
    The definition of random sequences.
    Information and Control, 9:602-619, 1966. MR 0223179 (36:6228)
  • 8. André Nies, Frank Stephan, and Sebastiaan A. Terwijn.
    Randomness, relativization and Turing degrees.
    J. Symbolic Logic, 70(2):515-535, 2005. MR 2140044
  • 9. C.-P. Schnorr.
    A unified approach to the definition of random sequences.
    Math. Systems Theory, 5:246-258, 1971. MR 0354328 (50:6808)
  • 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.

American Mathematical Society