A computable class of Descriptional complexity measures, based on automata
Automatic complexity of strings smallest number of states of a DFA (deterministic finite automaton) that acceptsxand does not accept any other string of length |x|. Note that a DFA recognizing the singleton language {x} always needs |x|+1 states, which is the reason the definition considers only strings of length |x|.
Automatic Kolmogorov complexity and normality revisited
Automaticity I: Properties of a Measure of Descriptional Complexity
is an analogous descriptional complexity measure as Automatic complexity but for languages.
The finite-state dimension is defined in terms of computations of finite transducers on infinite sequences,
Entropy rates and finite-state dimension – pdf
Finite-state dimension and real arithmetic ☆
Newest measure in this area.
Paper: http://www.sciencedirect.com/science/article/pii/S0304397511005408
Finite state complexity defines smallest length of input that will produce result under finite transducer (finite state machine with output basically, which i think can describe the GP maps). Then we can apply Ards argument of how many ways of fitting this shortest string in the fixed-length input of interest (say the genotype). This could be the beginning of the formal theory we need! We probably would also want to develop a concept of algorithmic probability (like Salomonoff's) for finite state machines.
Finite-State Complexity and Randomness
Finite-State Complexity and the Size of Transducers
Finite state transducer Finite model theory
Others
Approximating the smallest grammar: Kolmogorov complexity in natural models. However, the model allows the advice strings to be over an arbitrary alphabet with no penalty in terms of complexity and, as observed in [8], consequently the NFAs used for compression can always be assumed to consist of only one state... (so not very good measure).