|
When van Lambalgen's Theorem fails
Author(s):
Liang
Yu
Journal:
Proc. Amer. Math. Soc.
135
(2007),
861-864.
MSC (2000):
Primary 03D28, 68Q30
Posted:
September 15, 2006
MathSciNet review:
2262883
Retrieve article in:
PDF
Abstract |
References |
Similar articles |
Additional information
Abstract:
We prove that van Lambalgen's Theorem fails for both Schnorr randomness and computable randomness.
References:
-
- 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
Email:
yuliang.nju@gmail.com
DOI:
10.1090/S0002-9939-06-08541-8
PII:
S 0002-9939(06)08541-8
Received by editor(s):
July 11, 2005
Received by editor(s) in revised form:
August 21, 2005 and October 17, 2005
Posted:
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
Copyright of article:
Copyright
2006,
American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.
|
