An unpredictability approach to finite-state randomness

摘要

This paper investigates the concept of randomness within a complexity theoretic framework. We consider an unpredictability approach for defining randomness in which the preditions are carried out by finite-state automata. Our model of a finite-state predicting machine (FPM) reads a binary sequence from left to right and depending on the machine's current state will generate, at each point, one of three possible values: 0, 1, or #. A response of 0 or 1 is to be taken as the FPMs prediction of the next input. A # means no prediction of the next input is made. We say that an infinite binary sequence appears random to an FPM if no more than half of the predictions made of the sequence's terms by the FPM are correct. The main result of this paper is to establish the equivalence of the sequences which appear random to all FPMs and the ∞-distributed sequences, where a binary sequence is called ∞-distributed if every string of length k occurs in the sequence with frequency 2−k, for all positive integers k. We also explicitly construct machines that exhibit success in predicting the sequences which are not ∞-distributed. Finally, we show that for any given ∞-distributed sequence, all infinite subsequences which are constructible from FPMs are also ∞-distributed.