computability

Scott Aaronson's Harvard CMSA talk traces what mathematical truths are knowable, from Godel and Turing to the Busy Beaver function. He covers recent work on Busy Beaver values.

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.

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.

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.

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.

Tom Murphy's satirical SIGBOVIK 2007 presentation, delivered under a pseudonym, proving that generalized Super Mario Bros. is NP-complete. It is a short, deadpan take on a complexity theory result.

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

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.

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.