complexity

An 11-minute animated introduction to P vs. NP and the wider landscape of complexity classes, inspired by the Complexity Zoo wiki. It assumes no background in computer science.

Leonard Susskind lectures at Stanford on how gravity and quantum information theory have merged into a new way of thinking about physics. He covers entanglement and complexity, with applications from black holes to strange metals and the foundations of quantum mechanics.

Physicist Geoffrey West speaks at an FQXi conference on time about complexity and scaling laws. He covers how metabolism, growth and lifespan scale across organisms and how the same mathematics applies to cities and companies.

Lex Fridman interviews Donald Knuth about algorithms, complexity, The Art of Computer Programming, and his work habits. The conversation covers his approach to verifying algorithms and how he organises his time.

Kyle Hill of Because Science explains and demonstrates, using real cards, how Magic: The Gathering can be used to build a Turing machine, a computer inside the card game.

Find the Longest Path is a comedic song by Daniel J. Barrett, a Billy Joel parody that describes the NP-hard longest path problem in informal terms.

Jim Weirich's RubyConf 2012 talk derives the Y combinator step by step, live-coding in Ruby lambdas. It builds up an understanding of functional programming and lambda calculus from first principles.

Meredith Patterson and Sergey Bratus argue that networked software stays insecure because protocols and inputs are too complex to recognize safely. They propose using formal language theory and grammars to build secure, verifiable input handling.

Philip Wadler's Strange Loop talk on Propositions as Types, the link between logic and computation (the Curry-Howard correspondence). He traces its history through Church, Godel and Turing and shows how it shaped theorem provers and programming languages.

Christopher Domas's Derbycon 2015 talk on the M/o/Vfuscator, a compiler that emits only x86 mov instructions, showing mov is Turing complete. It explains how a full machine is built from mov and why the output is a nightmare to reverse engineer.

Rich Hickey's keynote at RailsConf 2012, a close sibling of his 'Simple Made Easy' talk. He distinguishes simple (not intertwined) from easy (familiar), and argues that software complexity comes from complecting things, with Rails-specific examples including large gem collections.

A short SIGBOVIK 2017 presentation by Tom Wildenhain showing that PowerPoint animations are Turing complete, with a working Turing machine built in slides. The talk is delivered deadpan as a serious research result.

A two-minute video of Conway's Game of Life running inside Conway's Game of Life, built from OTCA metapixels and Golly. It zooms smoothly between scales.

Matt Parker talks Numberphile through the different kinds of numbers: algebraic, transcendental, computable, normal, and beyond. It shows how few numbers we can actually name or describe.

Gabriel Lebec's Fullstack Academy talk introduces lambda calculus syntax, the history of mathematical logic, and the essence of functional programming using JavaScript. It also covers combinators, currying and Church encodings.

Scott Meyers' keynote at DConf 2014, drawing on 25 years of C++ experience to offer the D language community a plea about what it should avoid. It centers on the accumulated complexity and pitfalls of C++ as a cautionary tale.

Tom Stuart's Ruby Manor 3 talk builds FizzBuzz using nothing but Ruby lambdas, working through Church encodings of numbers, booleans and data structures. It is a hands-on introduction to lambda calculus.

David Beazley's PyCon 2019 tutorial derives the lambda calculus from the ground up in Python, using only single-argument functions. He builds booleans, numerals and more with no other language features.

Tom Wildenhain's guest lecture for CMU's Esoteric Programming Languages course shows that PowerPoint transitions and slides are Turing complete without macros, building up to a mind-bending fractal ending.

Matt Might's Curry On talk on ending errors in code, both software and the human genome. He covers conservative approximation of the halting problem via static analysis and a computational approach to precision medicine.

A panel with Tony Hoare, Joe Armstrong and Carl Hewitt, hosted by Francesco Cesarini, on the history and future of concurrency. The three creators of CSP, Erlang and the actor model discuss their differing approaches.

Milton Friedman explains why the US tax code is enormously complex and why meaningful reform is unlikely. He argues that politicians profit from the complexity, since tax breaks are products they sell and the code works as a tool of reward and punishment. The clip is about 14 minutes from his lecture series.

The first lecture of an MIT course on Douglas Hofstadter's Godel, Escher, Bach, covering themes like self-reference, recursion and incompleteness. The full lecture series is on YouTube.

The first video in a series on extremely large numbers, introducing the topic with examples. Later parts go deep into the fast-growing hierarchy.

An excerpt from Richard Dawkins's lecture on Climbing Mount Improbable demonstrating how a complex eye can evolve through incremental steps. It answers the creationist irreducible complexity argument.

A Computerphile video in which Mark Jago of the University of Nottingham explains Turing's halting problem and how it led to the blueprint for the modern computer.

John Conway talks in a short Numberphile interview about his mixed feelings toward the Game of Life, his most famous invention. He says he is not especially pleased that it overshadowed his other work.

A short demo of a playable Space Invaders game built inside Dwarf Fortress, with a downloadable map. It shows the game's mechanics used as a computing substrate.

Pro Magic player Luis Scott-Vargas triggers a mandatory-action infinite loop on Magic Online, and the game stalls in a non-terminating state.

An animated, musical visualization of Conway's Game of Life showing patterns made in the Golly program.

Casey Muratori's long talk arguing that modern software has ballooned to tens of millions of lines because of hardware and OS diversity. He proposes a stable ISA for entire system-on-a-chip packages and recalls when games shipped with their own boot disk.

John Ousterhout, Stanford professor and creator of Tcl, presents the ideas of his book A Philosophy of Software Design in a Talks at Google session. He covers managing complexity, deep modules and interfaces, and what he teaches in his Stanford software design course.

Alan Kay's 2015 talk on the power of simplicity, arguing that systems become simpler by building on more sophisticated fundamental building blocks and that big research horizons drove invention at Xerox PARC. It ranges across computing, tools and scaling software.

Joseph Tainter lectures at a 2010 sustainability conference on why complex societies such as Rome collapse. His thesis is that rising complexity brings diminishing returns until societies cannot afford to maintain it.

Stuart Halloway's satirical talk describes how to protect yourself from industry change by spreading complexity through systems while following idiomatic practice. It uses this inversion to catalog software design anti-patterns.

Raymond Hettinger's PyBay 2019 talk on the mental habits behind effective programming, drawn from coaching, teaching and StackOverflow. He covers problem decomposition, chunking, managing working memory and getting unstuck.

Brian Will critiques object-oriented programming and rewrites a roughly 3800-line OO program in a procedural style, cutting code and complexity. It is part of a series of OOP critiques.

Yehuda Katz's Railsberry 2012 talk on why Rails is hard to learn and use. He explains that the framework's many features reflect real complexity in web applications that newcomers do not yet see.

Robert Sapolsky's Stanford lecture on chaos and reductionism, which he calls one of the hardest of the course. It examines the limits of breaking systems into parts to understand them and introduces chaotic systems.

A DevGAMM talk by Jonathan Blow arguing that civilizations can lose technological capability and that software quality is already deteriorating. He discusses how knowledge fails to transfer between generations.