SimplicityTheory

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.

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 C_w = 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 = C_w – C. As there are 2^k 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 C_w.

Lottery: when a given situation can be considered as one among N equivalent alternatives, the W-machine requires a minimum of log₂ N bits to produce it. This rule can be used when an object, a location or a moment is picked out of a range of possibilities (see the remarkable lottery example).
Knowledge: When an event contradicts the observer’s beliefs (see the running nuns example), C_w is derived from the W-complexity of the least complex causal hypothesis that must be revised for the contradiction to be cancelled (see Dessalles, 2008b, chap. 6.2).
Causal story: individuals are able to combine the W-complexities of successive events, considered as a computation sequence. For independent successive decision c_i the "world" has to take: C_w(c₁*c₂*c₃*s) = c_w(c₁) + c_w(c₂) + c_w(c₃) + c_w(s|c₁&c₂&c₃). See the rabid bat and the running nuns for illustration.

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: C_w(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).

Note that condition ‘|’ has not the same meaning for generation complexity and for description complexity.
Conditional description complexity C(s|a) means that a is available for the description of s.
Conditional generation complexity C_w(s|a) means that the generation complexity of s is computed from a ‘world’ in which a is true (Dessalles, 2013).
Generation complexity is influenced by logical relations and can be used to define independence.

Bibliography

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.