![[Search]](/static/images/search.gif){kind=small}
![[A-Z Index]](/static/images/az.gif){kind=small}
![[Contact]](/static/images/contact.gif){kind=small}
![[University of Cambridge]](/static/images/identifier2.gif){kind=small}
![[Talks.cam]](/static/images/talkslogosmall.gif)
Wednesday 07 February 2018, 19:30-20:00
Kolmogorov Complexity and Gödel’s Incompleteness Theorems
- 👤 Speaker: Shubham Aggarwal, Churchill College
- 📅 Date & Time: Wednesday 07 February 2018, 19:30 - 20:00
- 📍 Venue: Wolfson Hall, Churchill College
Questions? Contact
Matthew Ireland
Abstract
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.
Series This talk is part of the Churchill CompSci Talks series.
Included in Lists
Note: Ex-directory lists are not shown.