|
|
|
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.
Last modified:
April 25, 2006
|
