Finite-State Complexity and Randomness

Abstract

In this paper we develop a version of Algorithmic Information Theory (AIT) by replacing Turing machines with finite transducers; the complexity induced is called finite-state complexity. In spite of the fact that the Universality Theorem (true for Turing machines) is false for finite transducers, the Invariance Theorem holds true for finite-state complexity. We construct a class of finite-state complexities based on various enumerations of the set of finite transducers. In contrast with descriptional complexities (plain, prefix-free) from AIT, finite-state complexity is computable and there is no a priori upper bound for the number of states used for minimal descriptions of arbitrary strings. Explicit examples of finite-state incompressible strings are given as well as upper and lower bounds for finite-state complexity of arbitrary strings and for strings of particular types. Various open problems are discussed throughout the paper.