Invariance Properties of Random Sequences
Дата
Авторы
Hertling,Peter
Wang,Yongge
Journal Title
Journal ISSN
Volume Title
Издатель
Journal of Universal Computer Science
Аннотация
Описание
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