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

Corresponding author: Peter Hertling ( hertling@cs.auckland.ac.nz )

© Peter Hertling, Yongge Wang.
This article is freely available under the J.UCS Open Content License.
Citation: Hertling P, Wang Y (1997) Invariance Properties of Random Sequences. JUCS - Journal of Universal Computer Science 3(11): 1241-1249. https://doi.org/10.3217/jucs-003-11-1241
Open Access
Abstract
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.
Keywords
Randomness, invariance properties