Simplicity, Complexity, Unexpectedness, Cognition, Probability, Information

by Jean-Louis Dessalles     (created 31 December 2008, updated April 2016)

Generation complexity and the W-Machine

Some events require complex combinations of circumstances

Generation complexity (or causal complexity) measures the minimal amount of instructions that should be given to the W-machine ("world machine") for it to generate the event.
The W-machine represents the "world" as the observer knows it or imagines it.

In pachinko, small balls are fired by the player to the top of the machine. They fall down through an array of pins that alter their course. Most balls end up in a collector and are lost for the player, but some may reach winning pockets.

The following example (see figure below) is inspired by the pachinko game. Imagine that a ball falls down along a binary tree such as the one depicted below. At each branching node, it must "decide" whether it should turn right or left. It eventually reaches a leaf of the tree after k such decisions. The generation complexity of the event "the ball reached leaf x" amounts to Cw = k.

Note that most events of the type "the ball reached leaf x" are not unexpected. By definition, unexpectedness is the difference between generation complexity (as defined here) and description complexity: U = Cw – C. As there are 2k leaves, one generally needs C = k bits to single out one of them. Therefore, unexpectedness U = 0 for most leaves. However, if the observer can use a simple feature to single out the winning leaf (e.g. the only coloured leaf), then C = C(f) and unexpectedness U = k – C(f) may be large. Note that C(f) is small, as f is the only perceptual feature among leaves.

Individuals are able to combine several basic machines to assess Cw.

W-complexity is a crucial component of unexpectedness. The computation of unexpectedness U requires some knowledge of the causal functioning of the "world" and of its constraints. In a world in which everything is possible, nothing is unexpected. Only a constrained world can surprise us.

The W-machine is a computing machine that respects the constraints of the "world". It is given the current state of the "world" as input. The W-complexity is the additional input that must be given to the W-machine for it to generate the situation. An object b that is considered to belong to the known "world" requires zero complexity to be generated: Cw(b) = 0.

Caveat: the world taken as reference has no objective character; it is the world as it is known by the observer (or, in the case of fiction, imagined).


Dessalles, J-L. (2008a). Coincidences and the encounter problem: A formal account. In B. C. Love, K. McRae & V. M. Sloutsky (Eds.), Proceedings of the 30th Annual Conference of the Cognitive Science Society, 2134-2139. Austin, TX: Cognitive Science Society.

Dessalles, J-L. (2008b). La pertinence et ses origines cognitives - Nouvelles théories. Paris: Hermes-Science Publications.

Dessalles, J.-L. (2013). Algorithmic simplicity and relevance. In D. L. Dowe (Ed.), Algorithmic probability and friends - LNAI 7070, 119-130. Berlin, D: Springer Verlag.

Saillenfest, A. & Dessalles, J-L. (2015). Some probability judgments may rely on complexity assessments. Proceedings of the 37th Annual Conference of the Cognitive Science Society, to appear. Austin, TX: Cognitive Science Society.


Back to the Simplicity Theory page.