Calude, C.S.Salomaa, K.Roblot, T.K.2012-01-162012-01-162009CDMTCS Research Reports CDMTCS-374 (2009)1178-3540http://hdl.handle.net/2292/10527In 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.https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmTechnical ReportFields of Research::280000 Information, Computing and Communication SciencesThe author(s)http://purl.org/eprint/accessRights/OpenAccess