SimplicityTheory


Simplicity, Complexity, Unexpectedness, Cognition, Probability, Information
by JeanLouis Dessalles
(created 31 December 2008, updated March 2022)
Description complexity and the OMachine
Only a few events can be concisely descibed 
Description complexity measures the minimal amount of instructions that should be given to the Omachine ("observation machine") for it to designate the event.
The Omachine 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 welldefined, 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.Finding a periodic pattern in the tiled floor shown on the right (seen at DenfertRochereau Metro Sation in Paris) might be less obvious, though. Let’s call C_{i}^{t}(s) the size of the best compression that an observer i has been able to produce within time t. This notion is, by definition, computable as soon as a computable cognitive model of the observer is available. On this Website, C(s) is used to designate C_{i}^{t}(s). In this sense, C(s) is computable. Back to the Simplicity Theory page.