Prediction of Binary Sequences by Evolving Finite State Machines

This paper explores the possibility of using the evolution of a population of finite state machines (FSMs) as a measure of `randomness' of a given binary sequence. An FSM with binary input and output alphabet can be seen as a predictor of a binary sequence. For any finite binary sequence, there exists an FSM able to perfectly predict the string but such a predictor, in general, has a large number of states. In this paper, we address the problem of finding the best predictor for a given sequence. This is an optimization problem over the space of all possible FSMs with a fixed number of states evaluated on the considered sequence. For this optimization an evolutionary algorithm is used: the better the FSMs found are, the less `random' will the given sequence be.