Complexity, Computation, and Measurement
Christoph Adami, Nicolas J. Cerf · arXiv (Cornell University) · 1996
We consider the duality between computation and measurement emerging from the thermodynamics of Turing machines. This duality suggests a new measure of complexity (physical complexity) which corresponds to our intuition and appears to be practical enough to estimate the complexity of genomes. From an automata theoretic point of view, this complexity is just the mutual information