JUCS - Journal of Universal Computer Science 3(11): 1241-1249, doi: 10.3217/jucs-003-11-1241
Invariance Properties of Random Sequences
expand article infoPeter Hertling, Yongge Wang
‡ Department of Computer Science, The University of Auckland, Auckland, New Zealand
Open Access
We present invariance characterizations of different types of random sequences. We correct Schnorr's original, incorrect characterization of Martin-Loef ran dom sequences, compare it with Schnorr s corresponding characterization of his own randomness concept, and give a similar, new characterization of Kurtz random sequences. That is, we show that an infinite sequence is Kurtz random if and only if for every partial, computable, measure-invariant function the sequence is not recursive. 1.) Proceedings of the First Japan-New Zealand Workshop on Logic in Computer Science, special issue editors D.S. Bridges, C.S. Calude, M.J. Dinneen and B. Khoussainov.
Randomness, invariance properties