Skip to main content
Course

Computation as a Universal and Fundamental Concept

Chapters

Intro Computation and Its Limits

Welcome to the Series
0:00
Can Computers Solve Everything?
0:34
Clever Algorithmic Shortcuts
1:35
Easy Problems vs Hard Problems
3:09
The P versus NP Question
4:32
Do New Technologies Change the Rules?
5:25
Top 10 Reasons to Watch This Series
6:42
#10: Turing and the Birth of Computer Science
7:19
#9: A Cast of Legendary Thinkers
7:53
#8-7: Surprising Truths About Complexity
8:38
#6: Grade School Math Is Not Optimal
9:47
#5: Funny Mathematician Stories
10:17
#4: Computer Science's Fight for Respect
10:49
#3: LLMs Change Nothing About These Limits
11:44
#2: What Quantum Computers Actually Change
12:25
#1: The Million-Dollar P vs NP Mystery
13:05

Lecture 1 Is There Anything Computers Can't Do?

Computation as a Universal Mystery
0:01
Alan Turing's Landmark 1936 Paper
0:46
Computer Science Before Computers Existed
2:49
Hilbert's Program and the Decision Problem
5:20
Gödel Shatters the Dream of Completeness
8:17
What Remained After Gödel?
9:55
What Is a Turing Machine?
11:44
Simple Machines, Infinite Power
15:27
Problems No Computer Can Ever Solve
17:47
The Halting Problem Explained
21:12
Why the Halting Problem Is Unsolvable
25:57
Step 1: The Universal Turing Machine
28:35
Why Computer Science Is a Real Discipline
33:23
Step 2: The Diagonalization Trick
36:03
Step 3: Reductions Spread Impossibility
40:47
Can Anything Beat a Turing Machine?
48:00
Church's Lambda Calculus and Turing-Completeness
53:17
The Eccentric Blackboard Ritual
55:07

Lecture 2 How Algorithms Outsmart Complexity

Algorithms Are Recipes for Problem Solving
0:00
A 23-Year-Old Disproves a Famous Conjecture
3:11
How Grade School Multiplication Works
6:48
Recursion: Solving Big Problems with Small Ones
10:49
Splitting Numbers Into Smaller Multiplications
13:52
The Key Insight: Reuse Instead of Redo
17:50
The Eureka Trick That Saves a Multiplication
21:46
Step-by-Step Faster Multiplication
24:02
Why This Matters: From Python to Matrices
26:41
Finding the Shortest Path in a Network
30:43
Why Checking Every Option Fails
33:55
Exponential Growth and Atoms in the Universe
39:40
Dijkstra's Algorithm: The Expanding Balloon
43:45
The Golden Era of Algorithm Design
48:46
The Homework Legend That Was Actually True
50:09
When Von Neumann Discovered Duality in Real Time
52:45
When Algorithms Hit a Wall: Enter P vs NP
55:44

Lecture 3 Easy Problems, Hard Problems

Recap: Shortest Paths and Algorithmic Shortcuts
0:00
Do Algorithmic Shortcuts Always Exist?
2:43
The Traveling Salesman Problem Explained
4:08
TSP: Solvable But Not Efficiently
7:18
A Bold Conjecture and the Road to P vs NP
10:11
What Makes a Problem Easy to Solve?
12:54
Polynomial-Time Algorithms Defined
16:31
Moore's Law: Polynomial vs Exponential Growth
19:16
The Class P and Its Connection to Turing
24:06
NP-Completeness: The Idea of Relative Hardness
26:36
NP Problems: Easy to Check, Hard to Solve
32:54
Universal Problems That Encode Everything
35:28
Two Possible Worlds: P = NP or P ≠ NP
39:09
Reductions: Proving One Problem Is As Hard
47:10
The Cook-Levin Theorem: NP-Completeness Exists
54:04
Tenacity in Research: Stories of Cook and Levin
57:01

Lecture 4 Two Worlds We Might Live In

Recap: Easy Problems, Hard Problems, and Shared Fate
0:01
Two Themes: Power and Limitations of Computation
3:17
Historical Backdrop: Algorithms vs Lower Bounds
5:47
Engineering Mindset vs Pure Math Mindset
8:20
Classifying Our Cast of Characters
11:30
Karp's 21 Problems: The Big Bang of NP-Completeness
19:41
How NP-Completeness Changed Everything
26:16
Meeting the Pioneers of NP-Completeness
28:20
Visualizing the Two Possible Worlds
29:10
The P vs NP Question Formally Stated
32:01
Millennium Prize: A Million Dollar Question
33:46
What Do P, NP, and NP-Complete Actually Mean?
36:55
Naming NP-Complete: Hardass or Hard-Boiled?
40:25
Why Experts Bet on P ≠ NP
43:45
The Vibes Argument: It Just Feels True
48:36
Why Proving P ≠ NP Is Nearly Impossible
49:37
Will We Ever Solve P vs NP?
52:57

Lecture 5 AI, Quantum Computing, and Beyond

Recap: The P vs NP Question
0:01
NP-Intermediate Problems and Ladner's Theorem
3:24
Factoring: The Problem Behind Your Encryption
5:48
Graph Isomorphism: Are Two Networks the Same?
8:35
Why Levin Had Bad Luck and Karp Didn't
10:57
What If We Prove P ≠ NP?
17:09
What If P = NP With Fast Algorithms?
22:03
The Awkward Scenario: P = NP But No Useful Code
25:53
When Definitions Need an Upgrade
30:51
Do New Technologies Challenge Computation?
34:12
Quantum Computing vs the Extended Thesis
39:42
Shor's Algorithm: Quantum Computers Break RSA
42:01
Post-Quantum Cryptography to the Rescue
45:00
Revising the Extended Church-Turing Thesis
46:19
Can AI Overcome Fundamental Limits?
49:43
Secrets Behind LLM Performance
53:35
How AI Creates the Illusion of Solving Everything
58:54
Computation Transcends All Technology
1:03:49