SimplicityTheory |
 |
Simplicity, Complexity, Unexpectedness, Cognition, Probability, Information
by Jean-Louis Dessalles (created 31 December 2008, updated March 2022)
Description complexity and the O-Machine
Only a few events can be concisely descibed |
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.Finding a periodic pattern in the tiled floor shown on the right (seen at Denfert-Rochereau Metro Sation in Paris) might be less obvious, though. Let’s call Cit(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 Cit(s). In this sense, C(s) is computable. Back to the Simplicity Theory page.