Finite State Incompressible Infinite Sequences

Abstract

In this paper we define and study finite state complexity dips in infinite sequences and finite state incompressible infinite sequences. We show that the finite state complexity does not only depend on the codes for finite transducers, but also on how the codes are mapped to transducers. As a consequence we relate the finite state complexity to the plain (Kolmogorov) complexity, to the process complexity and to prefix complexity. Working with prefix-free sets of codes we characterise Martin-Lof random sequences in terms of finite state complexity: the weak power of finite transducers is compensated by the high complexity of enumeration of finite transducers. We also prove that every finite state incompressible sequence is normal, but the converse implication is not true. These results also show that our definition of finite state incompressibility is stronger than all other known forms of finite automata based incompressibility in particular the notion related to finite automaton based betting systems introduced in [25]. The paper concludes with a discussion of open questions.