Enseigner, c’est partager la beauté des idées et l’obsession des problèmes — puis découvrir, dans leurs solutions, des problèmes encore meilleurs.
Théorie algorithmique de l’information
Cours doctoral · Università della Svizzera italiana · 2023
La théorie algorithmique de l’information mesure l’information contenue dans un objet individuel par la longueur du plus court programme qui le produit. Ce cours doctoral, conçu pour être autonome, commence par les codes et l’information de Shannon, puis revient sur les fondements de la calculabilité : machines de Turing universelles, problème de l’arrêt et théorème de Rice.
Sur ces bases, nous développons les complexités de Kolmogorov simple et préfixe, explorons les liens entre hasard et incompressibilité, puis l’induction de Solomonoff. La probabilité d’arrêt Ω et le théorème d’incomplétude de Chaitin révèlent des limites quantitatives à ce que peuvent démontrer les systèmes axiomatiques formels. Nous étudions ensuite le théorème du codage, qui relie complexité et probabilité universelle, et utilisons les semi-mesures inférieurement semi-calculables pour établir la règle de chaîne.
Ce cours ignore les frontières entre l’informatique, les mathématiques, la physique et la philosophie. Donné initialement au printemps 2023 à l’Università della Svizzera italiana, il est accessible gratuitement en vidéo, accompagné de notes de cours et d’exercices.
