WE CAN HOLD a heated discussion about what mathematical theory of the second half of the twentieth century is most explanatory about the world. My stake is algorithmic information theory (AIT). AIT has shed light on various important questions such as what simplicity is, what a random number is, where the limits of mathematics are and how inductive inference can work. But what does AIT have to say about intelligence and its measurement? For good or for bad, AIT contaminates everything, and intelligence will not only be different, but a prototypical example. Of course, there are pitfalls and hurdles in AIT, and this third part of the book becomes more technical as a result, but we will not be able to dowithout AIT from now on. In this chapter we will introduce the main concepts of AIT with illustrations of how cognitive systems – ants or humans – are pervaded by the main ideas in AIT. As a first application of AIT, we will see how to generate cognitive exercises that are very much like those that appear in many IQ tests. This will unveil what these tests really are.

INFORMATION AND ALGORITHMS

Nuances apart, there seems to be general agreement in the view of cognition as some kind of information processing. But what is information processing? Shannon's information theory connects the notions of information coding, probability and communication, but the notion of ‘processing’ is diluted, as the coding procedures are performed in an idealistic way, as mathematical functions. In cognitive systems, we have much more than coding and communication. How are behaviours executed, modified and transmitted? How many resources are required for each behaviour in a given organism? What we know is that some behaviours are deeply coded into the DNA, retrieved, transformed and deployed into the phenotype. Likewise, other behaviours are composed into neural (or non-neural) control systems, stored, retrieved and deployed back again. In all these cases, there is some kind of computation involved.