Course 5 · Module 3
Computation
This module covers the mathematics of computing: what an algorithm is, how fast one can be, and what no algorithm can ever do. You'll follow the idea from Euclid's method for common divisors to Turing's imaginary machine, see why some problems are easy to check but seem hard to solve, and look at how computers, and now AI systems, are taking part in proving theorems. It's where mathematics meets the machines it made possible.
Module objectives
- Describe what an algorithm is and explain why the halting problem can't be solved by any algorithm.
- Explain the P versus NP problem and describe how computers and AI systems now take part in mathematical proof.
Lessons
- Lesson 1 Computation: Algorithms and the limits of computation, from Euclid's algorithm to Turing You'll run a 2,300-year-old algorithm that's still in use and see how the idea of a step-by-step procedure was made precise in the 1930s. You'll follow Turing's argument that some… 61111h 3m
- Lesson 2 Computation: Efficient algorithms, P versus NP, and computers that help prove theorems You'll see why some problems are easy to check but appear hard to solve, and why a million-dollar prize hangs on whether that appearance is real. You'll then look at how computers… 611111h 33m