On Pseudo-Random Sequences over Finite Automata

Article type: Research Article

Authors: Kramosil, Ivan

Affiliations: Czechoslovak Academy of Sciences

Abstract: It is a well-known fact that binary sequences (strings) of high algorithmic complexity can be taken as good approximations of statistically independent random sequences with two equiprobable outputs. Here “sequence of high algorithmic complexity” is such one, that the length of the shortest program generating this sequence by a universal Turing machine differs only by an a priori given constant from the length of the generated sequence. The present paper generalizes this result to the case of a finite (not necessarily binary) alphabet. Considering an infinite sequence of finite sequences of high algorithmic complexity over a finite alphabet, the relative frequency of occurences of each letter or finite string of letters is proved to tend to the inverted value of the total number of letters, or strings of letters of the given length, in question. This result may be seen as an analogy to the strong law of large numbers in the case of equiprobable probability distribution.

Keywords: Pseudo-random sequences, algorithmic complexity, Turing-machines

DOI: 10.3233/FI-1985-8104

Journal: Fundamenta Informaticae, vol. 8, no. 1, pp. 55-62, 1985