Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

Kolmogorov Complexity and Gödel's Incompleteness Theorems

Churchill CompSci Talks via YouTube

Overview

Explore the fascinating intersection of information theory and mathematical logic in this 26-minute conference talk. Delve into the concept of Kolmogorov complexity, which measures the shortest program length required to output a given string. Discover how this fundamental idea relates to data randomness and compressibility in information theory. Learn how Kolmogorov complexity can be applied to prove classical results in mathematical logic and computability. Follow along as the speaker presents an overview of Kolmogorov complexity, demonstrates its application in simple proofs, and then provides proof sketches for both of Gödel's incompleteness theorems using these concepts.

Syllabus

Kolmogorov Complexity and Gödel’s Incompleteness Theorems

Taught by

Churchill CompSci Talks

Reviews

Start your review of Kolmogorov Complexity and Gödel's Incompleteness Theorems

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.