Kolmogorov Complexity and Gödel’s Incompleteness Theorems
Channel: Churchill CompSci Talks
Date: 2019-10-04

Kolmogorov Complexity and Gödel’s Incompleteness Theorems, by Shubham Aggarwal (7th Feburary 2018)

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.