SimplicityTheory

Simplicity, Complexity, Unexpectedness, Cognition, Probability, Information

by Jean-Louis Dessalles
(created 31 December 2008)
(updated July 2015)

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 or event, i.e. a unique state of affairs. Elements in a computation sequence, such as a, b, c, should be understood as conceptual restrictions on situations.

Back to the Simplicity Theory page.