Intro to Kolmogorov Complexity @DrTrefor
Intro to Kolmogorov Complexity  @DrTrefor
Uploaded February 2025 | Updated November 2026, 18 hours ago
Typo 1: 2^5=32 not 16!!!! Just pretend I said "32" throughout the entire video:D Oops.
Typo 2: More importantly is that I missed the | | on the length when talking about randomness at 4:19 and 15:46. That is, we say a string y is kolmogorov random aka incompressible if K(y) is greater than or equal to |y|, not just y as written.

Kolmogorov Complexity is loosely the shortest computer program that outputs a given string. We'll use this to define a notation of being Kolmogorov random (aka incompressible) and use that to come up with a very nice proof that there are infinitely many prime numbers. Thanks to my colleague Gourab Ray for inspiration for this video.

♡♡♡SUPPORT THE CHANNEL♡♡♡
►Support on PATREON: patreon.com/DrTrefor
►MATH BOOKS I LOVE (affiliate link): amazon.com/shop/treforbazett
►CURIOSITY BOX: CuriosityBox.com/DrTrefor use CODE drtrefor for 25% off awesome STEM merch boxes

0:00 Kolmogorov Complexity
5:14 f minorizes g
8:42 Turing Machines
10:49 Full definition
12:05 Concatenation
14:01 Proving it is the best
15:44 Incompressible aka Random
17:50 Infinitely many prime numbers

CORRECTIONS:
1:52 2^5=32 not 16!!!! Just pretend I said "32" throughout the video
4:19 More importantly is that I missed the | | on the length when talking about randomness. That is, we say a string y is kolmogorov random aka incompressible if K(y) is greater than or equal to |y|, not just y as written.

COURSE PLAYLISTS:
►DISCRETE MATH: youtube.com/playlist?list=PLHXZ9OQGMqxersk8fUxiUMSIx0DBqsKZS
►LINEAR ALGEBRA: youtube.com/playlist?list=PLHXZ9OQGMqxfUl0tcqPNTJsb7R6BqSLo6
►CALCULUS I: youtube.com/playlist?list=PLHXZ9OQGMqxfT9RMcReZ4WcoVILP4k6-m
►CALCULUS II: youtube.com/playlist?list=PLHXZ9OQGMqxc4ySKTIW19TLrT91Ik9M4n
►MULTIVARIABLE CALCULUS (Calc III): youtube.com/playlist?list=PLHXZ9OQGMqxc_CvEy7xBKRQr6I214QJcd
►VECTOR CALCULUS (Calc IV): youtube.com/playlist?list=PLHXZ9OQGMqxfW0GMqeUE1bLKaYor6kbHa
►DIFFERENTIAL EQUATIONS: youtube.com/playlist?list=PLHXZ9OQGMqxde-SlgmWlCmNHroIWtujBw
►LAPLACE TRANSFORM: youtube.com/playlist?list=PLHXZ9OQGMqxcJXnLr08cyNaup4RDsbAl1
►GAME THEORY: youtube.com/playlist?list=PLHXZ9OQGMqxdzD8KpTHz6_gsw9pPxRFlX

OTHER PLAYLISTS:
►Cool Math Series:
youtube.com/playlist?list=PLHXZ9OQGMqxelE_9RzwJ-cqfUtaFBpiho
►Learning Math Series:
youtube.com/watch?v=LPH2lqis3D0&list=PLHXZ9OQGMqxfSkRtlL5KPq6JqMNTh_MBw
►LaTeX: youtube.com/watch?v=-HvRvBjBAvg&list=PLHXZ9OQGMqxcWWkx2DMnQmj5os2X5ZR73&index=2&ab_channel=Dr.TreforBazett

SOCIALS:
►X/Twitter: http://X.com/treforbazett
►TikTok: tiktok.com/@drtrefor
►Instagram (photography based): instagram.com/treforphotography
Intro to Kolmogorov ComplexityMy Self Study SystemHow to write your homework using LaTeXThe Learning Crisis in AcademiaThe Geometric Meaning of Differential Equations // Slope Fields, Integral Curves & IsoclinesThe Mathematician behind BubblesMy Birthday ParadoxHow to find DOMINATING STRATEGIES  with Game TheoryThe Beautiful Barnsley Fractal #shortsIS CHESS A GAME OF CHANCE? Classical vs Frequentist vs Bayesian ProbabilityAll the TRIG you need for calculus actually explainedThis is the best way to stack blocks.
Dr. Trefor Bazett |

Intro to Kolmogorov Complexity

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER