Automatic Randomness Tests

Abstract

In this paper we define a notion of automatic randomness tests (ART) which capture measure theoretic typicalness of infinite binary sequences within the framework of automata theory. An individual ART is found to be equivalent to a deterministic Büchi automaton recognizing $\omega$-language of (Lebesgue) measure zero. A collection of ART's induce a notion of automatic random sequence. We provide a purely combinatorial characterization of an automatic random sequence in the form of a disjunctive property for sequences. At last, we compare two kinds of automatic randomness tests presented in this paper.

21 pages