Approximations of algorithmic and structural complexity validate cognitive-behavioral experimental results


Approximations of algorithmic and structural complexity are important in cognitive and behavioral thinking because they provide a framework for understanding how the brain may process information and make decisions. Algorithmic complexity refers to the computational resources needed to perform a particular task. Estimating the algorithmic complexity of a task can help us understand the cognitive demands of that task, which in turn can inform how we design interventions to improve cognitive processing when structural complexity determines the relationships among various factors in a cognitive system and design new strategies for natural and artificial intelligence. By accounting for the complexity of behavioral relationships, scientists can gain insight into of how these concepts interact and influence each other. This can  provide a truly powerful framework for understanding the cognitive mechanisms underpinning human and animal behavior. However, there are still challenges and limitations in applying these methods to psychological experiments, such as choosing appropriate estimating algorithms, determining optimal parameters, dealing with randomness and noise, and interpretation results.

In a new research study published in the peer-reviewed journal Frontiers in Computational Neuroscience Dr. Hector Zenil from the University of Cambridge and the founder of Oxford Immune Algorithmics Ltd, a spin-out of the University of Oxford, in collaboration with Dr. James Marshall at the University of Sheffield, and Dr. Jesper Tegnér from the King Abdullah University of Science and Technology examined that numerical approximations of algorithmic and structural complexity that can be used to validate cognitive-behavioral experimental results from animals and humans across various scenarios and applications. They demonstrated that approximations to algorithmic complexity measure inherent properties of putative hidden behavioral patterns resulting from decision-making, while structural complexity measures the computational effort required for generating a behavioral output. The authors tested their hypothesis by applying these approximations to three notable studies on animal behavior involving ants, fruit flies, and rats.

The research team computed the approximations using various methods including Entropy, their Coding theorem method (CTM), their Block decomposition method (BDM) and an estimation based on the concept of Logical depth as introduced by computer scientist Charles Bennett. The authors applied these approximations to the landmark studies of animal behavior involving ants, fruit flies and rats with confirming results. The study of ants involved analyzing the foraging communication patterns of giant red ants. The study found food placed in more intricated places required longer times to be communicated, indicating a sophisticated communication system. The study with fruit flies involved analyzing carefully the flight patterns of Drosophila melanogaster in different environments: featureless, landmark and cluttered. The authors observed that the flight patterns of fruit flies deviated from Levy flight, a model of optimal random search, in all environments, validating the landmark result but without requiring clinical experiments. Moreover, the flight patterns of fruit flies in the featureless environment had the lowest algorithmic complexity but still proof of work, suggesting an algorithmic bias in their navigation strategy and not a mere random reaction. The study of rats involved analyzing the tactical deception and competition strategies of in a game-like scenario with a human competitor. The authors found that the rats exhibited a high level of behavioral flexibility and adaptation to the competitor’s actions. They observed that the structural complexity of the rats’ behavior always matched the structural complexity of the competitor, indicating a balance between exploration and exploitation. The study further found that the rats’ behavior simulated algorithmic randomness, suggesting a conscious cognitive strategy to avoid being predictable. The study compared the results of the animal experiments with previous experiments on how humans perceive randomness. According to the authors, humans tend to underestimate the complexity of random sequences and overestimate the complexity of non-random sequences. They suggested that this phenomenon reflects an algorithmic bias in human reasoning and decision processes, similar to the one observed in fruit flies. Therefore, numerical approximations of algorithmic and structural complexity can provide an objective tool to characterize behavioral complexity and cognition in different domains.

In summary, Dr. Hector Zenil and colleagues demonstrated how numerical approximations of algorithmic and structural complexity can provide an objective tool to characterize behavioral complexity and cognition in different domains. The study reveals the existence of an algorithmic bias in the decision processes of animals and humans, which may reflect their adaptation to environmental conditions and their strategy to avoid predictability. Together, algorithmic and structural complexity provide a powerful framework for understanding the neural basis of cognitive processes.

About the author

Dr. Hector Zenil

PhD Phil (Sorbonne), PhD CompSci (Lille), MPhil (Paris 1, ENS), MSc (Oxford), elected member of the London Mathematical Society and the College of Health Leaders in Canada. World expert in reversible large computer language models, or RLLMs based on Algorithmic Information Dynamics (AID).

Before joining the University of Oxford as a Senior Researcher and faculty member at the Department of Computer Science (ranked first worldwide), he contributed to some of the code that allows Siri and Alexa to answer factual questions that has also been incorporated into ChatGPT.  He has raised over USD 10M in grant and private equity funds from investors in 3 countries to transform healthcare with AGI.

He is the author of Algorithmic Information Dynamics (Cambridge University Press) and A Computable Universe (World Scientific/Imperial College) with a foreword by Sir Roger Penrose, Nobel Prize in Physics 2020.


Zenil H, Marshall JA, Tegnér J. Approximations of algorithmic and structural complexity validate cognitive-behavioral experimental results. Frontiers in Computational Neuroscience. 2023 ;16:179.

Go To Frontiers in Computational Neuroscience