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.