PickVidsBest Computability & complexity theory Videos
「Computability & complexity theory」下面有34部被不同的人、在不同月份推荐过的视频。挑的时候先看对象：入门9部，适合还没学过的人；进阶14部，适合已经懂术语的人；普通向10部，按兴趣就能看；更硬的1部，留给想看推导或细节的人。这一类数量最多的是演讲，所以它们的共同点是一位讲者把一个判断讲完，例子是为了撑住这个判断。常出现的频道包括Lex Fridman、Confreaks、Tom Wildenhain。目录给这个主题划的范围是：Theory of computation: Turing machines, halting problem, P vs NP, complexity classes, lambda calculus, automata, Church-Turing, Goedel incompleteness, computability.如果只看三部，就从《Ruby Conf 12 - Y Not- Adventures in Functional Programming by Jim Weirich》开始，它负责把问题讲出画面；然后看《28c3: The Science of Insecurity》，换一种讲法或例子；最后看《"Propositions as Types" by Philip Wadler》，留给已经有基础的人。页面按每页24部切开，顺序看的是被推荐跨越了多少个月，不是播放量。每条标题下面那一句是这部片子自己的内容说明，用来区分它在讲定义、过程、演示还是观点。点进去能看到推荐原话、原文链接和适合谁看。看的时候把强烈推荐当成有人明确叫你去看，把引用当成只是拿来举例，把批评留下来对照，不要把每条评论都当成同一力度。
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.