Course Program:
Topics (subject to change): Definitions of algorithmic complexity. The invariance theorem. Incompressibility. Resource-bounded complexity. Physics, information, and computation.
Textbook:
Grading:
Two midterms and a final exam of equal weight
Notes:
Topics (Section headings from the book):
1 Preliminaries
1.1 A Brief Introduction
1.2 Prerequisites and Notation
1.7 Basics of Computability Theory
1.11 Information Theory and Coding
2 Algorithmic Complexity
2.1 The Invariance Theorem
2.2 Incompressibility
2.8 Algorithmic Information Theory
3 Algorithmic Prefix Complexity
3.1 The Invariance Theorem
3.3 Incompressibility
3.4 K as an Integer Function
3.8 *Complexity of Complexity
3.9 *Symmetry of Algorithmic Information
7 Resource-Bounded Complexity
7.1 Mathematical Theory
7.2 Language Compression
8 Physics, Information, and Computation
8.1 Information Theory
8.3 Information Distance
8.4 Normalized Information Distance
8.5 Thermodynamics
8.6 Entropy Revisited