University of Cambridge > > Churchill CompSci Talks > Kolmogorov Complexity and Gödel’s Incompleteness Theorems

Kolmogorov Complexity and Gödel’s Incompleteness Theorems

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Matthew Ireland.

The Kolmogorov complexity of a string is defined as the length of the smallest program which outputs it. It encapsulates the ideas of randomness and compressibility of data and is a standard concept used in Information Theory. Surprisingly, it can also be used to give elegant proofs of some classical results in mathematical logic and computability.

This talk will first give an overview of Kolmogorov Complexity and then use it to prove some simple results. It will then present proof sketches for both of Gödel’s incomplete theorems using these notions.

This talk is part of the Churchill CompSci Talks series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2024, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity