Abstract:
We present invariance characterizations of different types of random sequences.
We correct Schnorr's original, incorrect characterization of Martin-Löf
random sequences, compare it with Schnorr's corresponding characterization of
his own randomness concept, and give a similar, new chararacterization 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.