Home › Topics › Mathematics & Theoretical CS
Computability & complexity theory: videos Hacker News recommends
Theory of computation: Turing machines, halting problem, P vs NP, complexity classes, lambda calculus, automata, Church-Turing, Goedel incompleteness, computability. Below: every video in this topic that at least three HN users linked with real commentary, in at least three different months (8 talks, 7 explainers, 6 demos), best-scored first, with the comments on each video page.
- 17 HN recommenders 18 months 2013–2026HN 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.
- 9 HN recommenders 9 months 2012–2024HN commenters call it one of the best security talks and the standard introduction to LANGSEC, which they use to argue for simpler, well-specified input formats.
- 9 HN recommenders 8 months 2015–2026HN regards it as an entertaining and eye-opening introduction to why logic and functional programming are connected, and it is a frequent pick in favorite-tech-talk threads.
- 6 HN recommenders 7 months 2017–2026HN calls it a legendary, clearly explained hacker talk whenever mov-only computing or anti-decompilation comes up.
- 7 HN recommenders 7 months 2021–2024HN commenters recommend it as a clear, accessible introduction to incompleteness and the self-referential proof idea.
- 8 HN recommenders 6 months 2017–2025HN repeatedly names it as one of the funniest and best talks, a favorite example of absurd computation.
- 6 HN recommenders 6 months 2013–2025P Phillip Bradbury · demoThe canonical visual for nested simulation, Turing completeness and self-reference; HN readers call it mind-blowing and reach for it constantly.
- 5 HN recommenders 5 months 2019–2024F Fullstack Academy · lectureRepeatedly recommended as one of the most approachable introductions to lambda calculus and combinators.
- 6 HN recommenders 6 months 2019–2025HN recommends it as an accessible explanation of number categories and why almost all numbers are unknowable.
- 4 HN recommenders 5 months 2015–2026H hackerdashery · explainerHN repeatedly recommends it as the best short, funny introduction to P vs. NP and complexity classes for people with no background.
- 4 HN recommenders 4 months 2013–2019Strongly recommended in lambda calculus and Y-combinator threads as a mind-expanding half hour that clarifies the ideas.
- 4 HN recommenders 4 months 2019–2021P PyCon 2019 · tutorialHN calls it a brilliant, mind-bending introduction to lambda calculus for programmers.
- 4 HN recommenders 4 months 2020–2026Repeatedly recommended in best-talks threads as a fun, mind-blowing demonstration of unexpected computation.
- 3 HN recommenders 3 months 2017–2019Recommended as a jaw-dropping, must-see talk that gives an amazing intro to static analysis alongside Might's personal story.
- 4 HN recommenders 4 months 2020–2023HN points to it as an accessible long-form introduction to Wolfram's ideas and a window into his passion, though some are critical of his claims.
- 3 HN recommenders 3 months 2019–2026HN recommends it for getting the inventors of major concurrency models together, disagreements included.
- 3 HN recommenders 3 months 2021–2023HN recommends it as an accessible way into Wolfram's physics ideas and his personality.
- 4 HN recommenders 3 months 2024–2026P Polylog · explainerRecommended as an intuitive, animated explanation of P vs NP framed around reversing computation.
- 3 HN recommenders 3 months 2013–2021HN likes it as a funny, entertaining presentation, frequently linked in threads on NP-hardness of games and NES automation.
- 4 HN recommenders 3 months 2021–2025HN recommends Sipser's free lectures as the companion to the standard theory of computation textbook and a path to understanding how computers fundamentally work.
- 3 HN recommenders 3 months 2017–2021Recommended as a companion to reading the dense book.
- 3 HN recommenders 3 months 2019–2026B Because Science · demoHN links it as the accessible, hands-on demo behind the claim that Magic is Turing complete.
- 2 HN recommenders 2 months 2016–2022G Giroux Studios · explainerRecommended in large-number threads as going further than other popular videos on Graham's number and ordinals.
- 2 HN recommenders 2 months 2021–2023HN points to it as a detailed explanation of Wolfram's physics hypothesis, and for Wolfram's evident passion, though some find it long.
- 2 HN recommenders 2 months 2019–2022Offered as a short, clear explanation of the halting problem and its link to decidability.
- 1 HN recommenders 1 months 2015–2024Cited whenever commenters want to note that Conway did not enjoy being known mainly for the Game of Life.
- 1 HN recommenders 1 months 2025–2026Mentioned in lambda calculus and combinator threads as a visual entry point to the topic.
- 1 HN recommenders 1 months 2025H Harvard CMSA · lecturePointed to in Busy Beaver threads as an accessible expert talk on the topic.
- 1 HN recommenders 1 months 2021–2026S switchbg · music videoHN shares it as a fun, memorable way to explain the longest path problem and as an entry in lists of programming and math songs.
- 1 HN recommenders 1 months 2016–2025B BaronWable · demoHN cites it as an impressive example of building computation inside Dwarf Fortress.
- 1 HN recommenders 1 months 2008–2014L LarryNorman · lectureCited in debates over whether computer science is a science, and for Abelson's line that it is neither a science nor about computers.
- cited 4× 0 months 2017–2023T TCGplayer · demoCited as the real-world example of an inescapable loop in Magic: The Gathering, in discussions of its Turing completeness.
- cited 4× 0 months 2016–2024R Rational Animations · demoHN commenters use it as an illustration of how simple rules can produce surprisingly complex behavior.
- cited 8× 0 months 2013–2021M MatthiasWandel · demoHN cites it as the classic example of a mechanical binary adder and a source of inspiration for marble-based computers.
Questions
What is the most recommended computability & complexity theory video on Hacker News?
Ruby Conf 12 - Y Not- Adventures in Functional Programming by Jim Weirich by Confreaks: 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.
How is this computability & complexity theory list ranked?
By HackerTube's score: the number of distinct months in which an HN comment recommended the video, plus half a point for every month with a strong recommendation. One viral thread counts less than steady recommendations over years.
Where do the videos come from?
From every Hacker News comment between 2007 and 2026 that linked a YouTube video, labeled by an AI model as a recommendation, a citation, a joke or a criticism. The list is published by HackerTube under ODC-By 1.0; this edition adds indexable pages and the comment context.
Video list and Hacker News comment labels from HackerTube (prompted by @karpathy), released under ODC-By 1.0, built on the open-index/hacker-news archive. Hacker News data is provided by Y Combinator; comments remain the work of their authors. Video titles, channel names and thumbnails belong to their creators and are shown via YouTube. HackerTube Watch is an unofficial edition. Data export of 2026-10-31.