Simplicity Theory

Simplicity, Complexity, Unexpectedness, Cognition, Probability, Information

by Jean-Louis Dessalles
(created 2008.12.31)

(updated 2010.02.18)

Definition: Computation sequences

Generation complexity C_w and Description complexity C can be seen as the length of a minimal computation performed by the "world-machine" (for C_w) and by the observation machine (for C). We call a computation sequence, noted with operator *, the indication of an order in these computations. A recursive application of conditional complexity allows to write in full generality:

C(s) < C(a*b*c*s) = C(a) + C(b|a) + C(c|a&b) + C(s|a&b&c)

The inequality is due to the fact that imposing an order on computation can lead to sub-optimality.

In the above definition, s is a situation, i.e. a unique state of affairs (remember that complexity computations in ST are performed on events). Elements in a computation sequence, such as a, b, c, should be understood as conceptual restrictions on situations.

Back to the Simplicity Theory page