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.
- 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.
- HN 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.
- HN 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.
- HN calls it a legendary, clearly explained hacker talk whenever mov-only computing or anti-decompilation comes up.
- HN commenters recommend it as a clear, accessible introduction to incompleteness and the self-referential proof idea.
- HN repeatedly names it as one of the funniest and best talks, a favorite example of absurd computation.
- Phillip Bradbury demo recommended in 6 different months by 6 HN users, 2013–2025The canonical visual for nested simulation, Turing completeness and self-reference; HN readers call it mind-blowing and reach for it constantly.
- Fullstack Academy lecture recommended in 5 different months by 5 HN users, 2019–2024Repeatedly recommended as one of the most approachable introductions to lambda calculus and combinators.
- HN recommends it as an accessible explanation of number categories and why almost all numbers are unknowable.
- hackerdashery explainer recommended in 5 different months by 4 HN users, 2015–2026HN repeatedly recommends it as the best short, funny introduction to P vs. NP and complexity classes for people with no background.
- Strongly recommended in lambda calculus and Y-combinator threads as a mind-expanding half hour that clarifies the ideas.
- PyCon 2019 tutorial recommended in 4 different months by 4 HN users, 2019–2021HN calls it a brilliant, mind-bending introduction to lambda calculus for programmers.
- Repeatedly recommended in best-talks threads as a fun, mind-blowing demonstration of unexpected computation.
- Recommended as a jaw-dropping, must-see talk that gives an amazing intro to static analysis alongside Might's personal story.
- HN 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.
- HN recommends it for getting the inventors of major concurrency models together, disagreements included.
- HN recommends it as an accessible way into Wolfram's physics ideas and his personality.
- Polylog explainer recommended in 3 different months by 4 HN users, 2024–2026Recommended as an intuitive, animated explanation of P vs NP framed around reversing computation.
- HN likes it as a funny, entertaining presentation, frequently linked in threads on NP-hardness of games and NES automation.
- HN recommends Sipser's free lectures as the companion to the standard theory of computation textbook and a path to understanding how computers fundamentally work.
- Recommended as a companion to reading the dense book.
- Because Science demo recommended in 3 different months by 3 HN users, 2019–2026HN links it as the accessible, hands-on demo behind the claim that Magic is Turing complete.
- Giroux Studios explainer recommended in 2 different months by 2 HN users, 2016–2022Recommended in large-number threads as going further than other popular videos on Graham's number and ordinals.
- HN points to it as a detailed explanation of Wolfram's physics hypothesis, and for Wolfram's evident passion, though some find it long.
- Offered as a short, clear explanation of the halting problem and its link to decidability.
- Cited whenever commenters want to note that Conway did not enjoy being known mainly for the Game of Life.
- Mentioned in lambda calculus and combinator threads as a visual entry point to the topic.
- Harvard CMSA lecture recommended in 1 different month by 1 HN user, 2025Pointed to in Busy Beaver threads as an accessible expert talk on the topic.
- switchbg music video recommended in 1 different month by 1 HN user, 2021–2026HN shares it as a fun, memorable way to explain the longest path problem and as an entry in lists of programming and math songs.
- BaronWable demo recommended in 1 different month by 1 HN user, 2016–2025HN cites it as an impressive example of building computation inside Dwarf Fortress.
- LarryNorman lecture recommended in 1 different month by 1 HN user, 2008–2014Cited in debates over whether computer science is a science, and for Abelson's line that it is neither a science nor about computers.
- TCGplayer demo cited on HN 4 times, 2017–2023Cited as the real-world example of an inescapable loop in Magic: The Gathering, in discussions of its Turing completeness.
- Rational Animations demo cited on HN 4 times, 2016–2024HN commenters use it as an illustration of how simple rules can produce surprisingly complex behavior.
- MatthiasWandel demo cited on HN 8 times, 2013–2021HN 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.