Simplicity, Complexity, Unexpectedness, Cognition, Probability, Information

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

Description complexity and the O-Machine

Only a few events can be concisely descibed

Description complexity measures the minimal amount of instructions that should be given to the O-machine ("observation machine") for it to designate the event.
The O-machine represents the observer’s knowlmedge and computing capabilities.

Note about computability: Like the usual definition of Kolmogorov complexity, Description complexity is not computable. It is easy to prove that no program can output C(s) when s is given as input. Ideal compression is well-defined, but cannot be computed. This observation led to the wrong conclusion that human minds have no access to complexity.

Human beings do have computational power that allows them to detect, for instance, pattern repetition. For instance, anyone who knows about numbers can detect a pattern in the series 122333444455555, namely "n repeated n times", which leads to significant compression.

Let’s call Cit(s) the size of the best compression that an individual i has been able to produce within time t. This notion is, by definition, computable as soon as a computable cognitive model is available. On this Website, C(s) is used to designate Cit(s). In this sense, C(s) is computable.


Back to the Simplicity Theory page.