On the descriptional complexity of systems and their output response

Abstract

Many problems require the analysis of the complexity of processes and systems, for instance, in control and manufacturing engineering one studies how complexity effects the tradeoff between hardware cost versus improved system performance. In computer science the so-called algorithmic (or Kolmogorov) complexity measures how long the minimal computer program needs to be in order that it produces a complete description of a static object. This has been traditionally studied in the context of computational complexity where the abstract Turing machine constitutes an algorithmic system. From this theory it is known that the more complex an object which acts on a random binary input sequence the more that it can deform the stochastic properties of the sequence. It has been until recently unknown whether such a relationship between complexity and randomness exists for a more general system, i.e., one which is governed by real physical laws. We postulate that the complexity of a real static system is its minimal description length. Through its interaction with the environment a real system is capable of deforming the stochastic properties of random inputs in proportion to its complexity. We describe recent developments which demonstrate this for systems as diverse as numerical schemes that describe physical solids, and decision systems which predict random sequences based on learning.