Best Computability & complexity theory videos, as recommended on Hacker News

31 videos about computability & complexity theory that Hacker News commenters keep recommending, mentioned between 2008 and 2026. Mostly talk, explainer, lecture. Channels that come up most: Lex Fridman, Confreaks, Tom Wildenhain, Numberphile. Sorted by how consistently HN recommended them over the years.

The most recommended is Ruby Conf 12 - Y Not- Adventures in Functional Programming by Jim Weirich: HN recommends it repeatedly as one of the best and most entertaining programming talks, and as the talk that makes the Y combinator click, even for people who do not use Ruby.

talkRuby Conf 12 - Y Not- Adventures in Functional Programming by Jim WeirichConfreaks · 17 HN recommenders · 2013–2026
talk28c3: The Science of Insecurity28c3 · 9 HN recommenders · 2012–2024
talk"Propositions as Types" by Philip WadlerStrange Loop Conference · 9 HN recommenders · 2015–2026
talkBreak Me00 The MoVfuscator Turning mov into a soul crushing RE nightmare Christopher DomasAdrian Crenshaw · 6 HN recommenders · 2017–2026
explainerMath's Fundamental FlawVeritasium · 7 HN recommenders · 2021–2024
talkOn The Turing Completeness of PowerPoint (SIGBOVIK)Tom Wildenhain · 8 HN recommenders · 2017–2025
demoLife in lifePhillip Bradbury · 6 HN recommenders · 2013–2025
lectureLambda Calculus - Fundamentals of Lambda Calculus & Functional Programming in JavaScriptFullstack Academy · 5 HN recommenders · 2019–2024
explainerAll the Numbers - NumberphileNumberphile · 6 HN recommenders · 2019–2025
explainerP vs. NP and the Computational Complexity Zoohackerdashery · 4 HN recommenders · 2015–2026
talkRuby Manor 3 - Programming with Nothing by Tom StuartConfreaks · 4 HN recommenders · 2013–2019
tutorialDavid Beazley - Lambda Calculus from the Ground Up - PyCon 2019PyCon 2019 · 4 HN recommenders · 2019–2021
lectureGreat Impractical Ideas in Computer Science: PowerPoint ProgrammingTom Wildenhain · 4 HN recommenders · 2020–2026
talkMatt Might - Winning the War on Error Solving the Halting Problem and Curing CancerCurry On! · 3 HN recommenders · 2017–2019
podcastStephen Wolfram: Cellular Automata, Computation, and Physics | Lex Fridman Podcast #89Lex Fridman · 4 HN recommenders · 2020–2023
talkLet's #TalkConcurrency Panel Discussion with Sir Tony Hoare, Joe Armstrong, and Carl HewittErlang Solutions · 3 HN recommenders · 2019–2026
interviewStephen Wolfram: Complexity and the Fabric of Reality | Lex Fridman Podcast #234Lex Fridman · 3 HN recommenders · 2021–2023
explainerWhat P vs NP is actually aboutPolylog · 4 HN recommenders · 2024–2026
comedySIGBOVIK 2007: Generalized Super Mario Bros. is NP-Completesuckerpinch · 3 HN recommenders · 2013–2021
lecture1. Introduction, Finite Automata, Regular ExpressionsMIT OpenCourseWare · 4 HN recommenders · 2021–2025
lectureMIT Godel Escher Bach Lecture 1jasonofthel33t · 3 HN recommenders · 2017–2021
demoI Built a COMPUTER in Magic: The GatheringBecause Science · 3 HN recommenders · 2019–2026
explainerExtremely Large Numbers 1 - IntroductionGiroux Studios · 2 HN recommenders · 2016–2022
podcastStephen Wolfram: Fundamental Theory of Physics, Life, and the Universe | Lex Fridman Podcast #124Lex Fridman · 2 HN recommenders · 2021–2023
explainerTuring & The Halting Problem - ComputerphileComputerphile · 2 HN recommenders · 2019–2022
interviewDoes John Conway hate his Game of Life?Numberphile · 1 HN recommender · 2015–2024
explainerWhat is PLUS times PLUS?2swap · 1 HN recommender · 2025–2026
lectureScott Aaronson | How Much Math Is Knowable?Harvard CMSA · 1 HN recommender · 2025–2025
musicFind the Longest Pathswitchbg · 1 HN recommender · 2021–2026
demoArmok InvadersBaronWable · 1 HN recommender · 2016–2025
lectureSICP / What is "Computer Science" ?LarryNorman · 1 HN recommender · 2008–2014