PickVidsBest Computability & complexity theory Videos
The 34 Computability & complexity theory videos here were recommended by different people across different months. Choose by who it is for: 9 introductory, 14 intermediate, 10 for a general viewer, and 1 for someone who wants the harder derivation. Most of them are a talk. What they share is that one speaker finishes a claim, and the examples exist to hold that claim up. Channels you will keep seeing include Lex Fridman, Confreaks, Tom Wildenhain.
Ruby Conf 12 - Y Not- Adventures in Functional Programming by Jim Weirich
Jim Weirich's RubyConf 2012 talk derives the Y combinator step by step, live-coding in Ruby lambdas.
28c3: The Science of Insecurity
Meredith Patterson and Sergey Bratus argue that networked software stays insecure because protocols and inputs are too complex to recognize safely.
"Propositions as Types" by Philip Wadler
Philip Wadler's Strange Loop talk on Propositions as Types, the link between logic and computation (the Curry-Howard correspondence).
Break Me00 The MoVfuscator Turning mov into a soul crushing RE nightmare Christopher Domas
Christopher Domas's Derbycon 2015 talk on the M/o/Vfuscator, a compiler that emits only x86 mov instructions, showing mov is Turing complete.
Math's Fundamental Flaw
Veritasium's explainer on Godel's incompleteness theorems and the limits of mathematical proof, tracing set theory, Hilbert's program and the road to Turing and modern computing.
On The Turing Completeness of PowerPoint (SIGBOVIK)
A short SIGBOVIK 2017 presentation by Tom Wildenhain showing that PowerPoint animations are Turing complete, with a working Turing machine built in slides.
Life in life
A two-minute video of Conway's Game of Life running inside Conway's Game of Life, built from OTCA metapixels and Golly.
Lambda Calculus - Fundamentals of Lambda Calculus & Functional Programming in JavaScript
Gabriel Lebec's Fullstack Academy talk introduces lambda calculus syntax, the history of mathematical logic, and the essence of functional programming using JavaScript.
All the Numbers - Numberphile
Matt Parker talks Numberphile through the different kinds of numbers: algebraic, transcendental, computable, normal, and beyond.
P vs. NP and the Computational Complexity Zoo
An 11-minute animated introduction to P vs.
Ruby Manor 3 - Programming with Nothing by Tom Stuart
Tom Stuart's Ruby Manor 3 talk builds FizzBuzz using nothing but Ruby lambdas, working through Church encodings of numbers, booleans and data structures.
David Beazley - Lambda Calculus from the Ground Up - PyCon 2019
David Beazley's PyCon 2019 tutorial derives the lambda calculus from the ground up in Python, using only single-argument functions.
Great Impractical Ideas in Computer Science: PowerPoint Programming
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 - Winning the War on Error Solving the Halting Problem and Curing Cancer
Matt Might's Curry On talk on ending errors in code, both software and the human genome.
Stephen Wolfram: Cellular Automata, Computation, and Physics | Lex Fridman Podcast #89
Lex Fridman interviews Stephen Wolfram for about three hours on cellular automata, computation, the Wolfram Physics Project and his career with Mathematica and Wolfram Alpha.
Let's #TalkConcurrency Panel Discussion with Sir Tony Hoare, Joe Armstrong, and Carl Hewitt
A panel with Tony Hoare, Joe Armstrong and Carl Hewitt, hosted by Francesco Cesarini, on the history and future of concurrency.
Stephen Wolfram: Complexity and the Fabric of Reality | Lex Fridman Podcast #234
A long Lex Fridman interview with Stephen Wolfram on complexity, cellular automata, computational irreducibility and the Wolfram Physics Project.
What P vs NP is actually about
Polylog explains how algorithms can be turned into circuits and encoded as satisfiability problems, which lets you effectively run them backwards.
SIGBOVIK 2007: Generalized Super Mario Bros. is NP-Complete
Tom Murphy's satirical SIGBOVIK 2007 presentation, delivered under a pseudonym, proving that generalized Super Mario Bros.
1. Introduction, Finite Automata, Regular Expressions
The first lecture of Michael Sipser's MIT 18.404J Theory of Computation course, covering course mechanics, finite automata, regular languages and regular expressions.
MIT Godel Escher Bach Lecture 1
The first lecture of an MIT course on Douglas Hofstadter's Godel, Escher, Bach, covering themes like self-reference, recursion and incompleteness.
I Built a COMPUTER in Magic: The Gathering
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.
Extremely Large Numbers 1 - Introduction
The first video in a series on extremely large numbers, introducing the topic with examples.
Stephen Wolfram: Fundamental Theory of Physics, Life, and the Universe | Lex Fridman Podcast #124
A roughly four-and-a-half-hour Lex Fridman podcast conversation with Stephen Wolfram about his Wolfram Physics Project and a fundamental theory of physics, computation, life and the universe.