Kolmogorov Complexity and Gödel’s Incompleteness Theorems

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

• Shubham Aggarwal, Churchill College
• Wednesday 07 February 2018, 19:30-20:00
• Wolfson Hall, Churchill College.

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.

This talk is included in these lists:

• Churchill CompSci Talks
• Wolfson Hall, Churchill College
• computer science
• se393's list

Note that ex-directory lists are not shown.