Cornell Math - MATH 788, Fall 2006

MATH 788: Topics in Applied Logic (Fall 2006)

Instructor: Bjørn Kjos-Hanssen

Meeting Time & Room

This term the course will cover Kolmogorov complexity and algorithmic information theory. We use the theory of algorithms to define the complexity of an individual finite bit string. This is then applied to infinite bit strings via their initial segments, and we get a notion of algorithmically random real number. Further topics include prefix complexity, a priori probability and Shannon entropy.

Prerequisites: Basic knowledge of logic, computability and probability; things like Turing machines and random variables.

Book: Ming Li and Paul Vitanyi. An Introduction to Kolmogorov Complexity and its Applications. Second Edition. Springer, 1997, ISBN 0-387-948868-6.