Teaching is sharing the beauty of ideas and an obsession with problems—then discovering, in their solutions, even better ones.
Algorithmic Information Theory
Doctoral course · Università della Svizzera italiana · 2023
Algorithmic information theory measures the information in an individual object by the length of the shortest program that produces it. This self-contained graduate course begins with codes and Shannon information, then reviews computability theory: universal Turing machines, the halting problem, and Rice’s theorem.
From these foundations, we develop plain and prefix complexity, connect randomness with incompressibility, and explore Solomonoff’s induction. Chaitin’s halting probability Ω and incompleteness theorem reveal quantitative limits on what formal axiomatic systems can prove. We then study the coding theorem, which links complexity to universal probability, and use lower semicomputable semimeasures to establish the chain rule.
My exposition moves freely between computer science, mathematics, physics, and philosophy. Originally taught at Università della Svizzera italiana in spring 2023, the course is freely available as a lecture series accompanied by notes and problem sheets.