Approximations of Algorithmic and Structural Complexity Validate Cognitive-behavioural Experimental Results

To objectively characterize the intrinsic complexity of behavioural patterns resulting from human or animal decisions is fundamental for deconvolving cognition and designing autonomous artificial intelligence systems. Yet complexity is difficult in practice, particularly when strings are short. By numerically approximating algorithmic (Kolmogorov) complexity (K), we establish an objective tool to characterize behavioural complexity. Next, we approximate structural (Bennett's Logical Depth) complexity (LD) to assess the amount of computation required for generating a behavioural string. We apply this toolbox to three landmark studies of animal behaviour of increasing sophistication and environmental influence, including foraging communication by ants, flight patterns of fruit flies, and tactical deception and competition (e.g., predator-prey) strategies. We find that ants harness the environmental condition in their internal decision process, thus modulating their behavioural complexity accordingly. Our analysis of flights (fruit flies) invalidated the common hypothesis that animals navigating in an environment devoid of stimuli adopt a random strategy. Fruit flies exposed to a featureless environment deviated the most from a Levy flight suggesting an algorithmic bias in their attempt to devise a useful (navigation) strategy. Similarly, a logical depth analysis of rat behaviour revealed that the structural complexity of the rat always ends up matching the structural complexity of the competitor and exploiting behavioural simulation of algorithmic randomness. We discuss how experiments on how humans perceive randomness suggest the existence of an algorithmic bias in our reasoning and decision processes, in line with our analysis of the animal experiments. This contrasts with the view of the mind as performing faulty computations when presented with randomized items.