What computation is
What is a computation, and what can no computer ever decide?
3 videos, about 49 min. Watch in order, or jump to a timestamp.
- 1
Introductory, Derivation, 13 min
Lambda Calculus - Computerphile
- Treat functions as the primitive notion.
- Distinguish defining a function from applying it.
- Connect a small formal system to programming behaviour.
Jump to 0:27 church and the notion of a function, 3:53 applying the increment function
- 2
Intermediate, Derivation, 28 min
What is PLUS times PLUS?
- Represent numbers and operations as functions.
- Unlearn ordinary data types to see computation as rewriting.
- Follow beta reduction mechanically.
Jump to 0:21 factorial and three as lambda expressions, 1:19 starting over with lambda calculus
- 3
Intermediate, Proof, 8 min
Proof That Computers Can't Do Everything (The Halting Problem)
- Describe a machine completely enough for another machine to analyze.
- Construct a program that does the opposite of a prediction.
- Use contradiction to establish a limit of computation.
Jump to 2:14 a complete machine blueprint, 6:32 the contradiction
