L’auteur essaie tout au long du livre de dégager les interactions entre le monde philosophique, intuitif et le monde mathématique. Ces interactions amènent les mathématiciens à créer de nouvelles structures (formalisations de concepts intuitifs) qui en retour éclairent le monde intuitif (celui des physiciens et des biologistes). Les supports de logique mathématique qui sont souvent utilisés sont ceux de « théorie de la démonstration (systèmes formels), théories des fonctions calculables (récursives) : thèse de Church, théorie de Kolmogorov, de Martin-Löf, théorème d’incomplétude de Gödel, théorie ZF des ensembles, conjecture « P=NP ».

Le chapitre 1 présente la notion d’information, pose le problème de la connaissance rencontré par les physiciens, les biologistes (séquence du génome). On ramène les problèmes à ceux sur des suites de symboles et on essaie de trouver comment mesurer la complexité de ces suites (i.e. complexité pour connaître, calculer son n-ième élément) après avoir parcouru les théories de l’information de Shannon et de Bennett, qu’il pense être mal adaptées aux problèmes des physiciens et des biologistes car ne les résolvant pas.

Le chapitre 2 étudie la formalisation de la notion de « suite aléatoire ». Il passe en revue :
– les théories de fonctions calculables (récursives) : Church, Turing, Post, Gödel dans les années 30,
– la notion de suite infinie aléatoire au sens de Von Mises (1919),
– au sens de Kolmogorov(1965),
– au sens de Martin-Löf (1966),
– au sens de Chaitin (1975).
La thèse de Church, unanimement reconnue par les mathématiciens, propose de prendre comme définition de fonction « calculable » celle de fonction récursive. L’auteur propose de considérer que la « bonne » notion de suite aléatoire soit celle de Martin-Löf. Il étudie cependant dans le fin du chapitre d’autres approches.

Le chapitre 3 donne des classifications de la complexité des problèmes (des suites). Après avoir rappelé les définitions mathématiques des différentes notions utilisées (ensemble récursif, récursivement énumérable, approximable, compressible), il propose une classification en 5 classes disjointes.

Le chapitre 4 compare deux théories : celle de la complexité aléatoire de Kolmogorov et celle de la complexité organisée de Bennett. Il en donne les définitions, des illustrations et en étudie le bien-fondé. Il fait le lien avec la conjecture « P=NP ».

Le chapitre 5 étudie les capacités d’induction d’une machine : limites et propriétés. Le chapitre est très argumenté par de nombreux exemples.

Le chapitre 6 reprend l’étude des problèmes d’indécidabilité. Il analyse d’un point de vue philosophique l’inadéquation des systèmes formels de haut niveau au monde intuitif. Il étudie en particulier le théorème de Gödel, de Ramsey, le 10e théorème de Hilbert (résolu par Matijasevic en 70). Ce chapitre contient de nombreuses citations de logiciens contemporains sur la question.

Les chapitres 7 et 8 reviennent sur le problème de la calculabilité en physique. Il étudie la notion d’infini, de déterminisme, de discrétisation du monde, donne des variantes de la notion de récursivité. Enfin il étudie la question « Le monde physique est-il récursif ? »

Le dernier chapitre 9 s’intéresse aux paradoxes sémantiques ; ce qui l’amène à fixer les limites des modélisations formelles. Il s’appuie sur la théorie ZF et la théorie des types de Russell, la théorie de la vérité de Tarski, la solution de Kripke.