Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 3 / Issue 11

available in:   PDF (202 kB) PS (67 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-003-11-1241


Invariance Properties of Random Sequences

Peter Hertling (Department of Computer Science, The University of Auckland, New Zealand)

Yongge Wang (Department of Computer Science, The University of Auckland, New Zealand)

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

Categories: F.1