Mathematical Foundations of Computing
Proofs, logic, and the astonishing fact that some problems can NEVER be solved by any computer, ever.
AI tutor is turned off for this class
Use the CS103 lectures, notes, and assignments below to keep learning.
Big Idea
How Computing Works
Grade bands
K-2 · 3-5 · 6-8 · 9-12
AI literacy pillar
How AI works · Ethics
Lesson overview
Proofs, logic, and the astonishing fact that some problems can NEVER be solved by any computer, ever. This module climbs from an everyday intuition to the real mechanism, then names the Stanford course it descends from.
Teacher script · ~45 min
- 0–5
Hook
In most of life 'it works on the examples I tried' is good enough. In math and CS theory, you want certainty for ALL cases, forever. A proof is an argument so airtight no counterexample can exist. Learning to prove is learning to think with zero loopholes.
- 5–15
Explore
Students do the activity in pairs: Draw a 2-state machine that accepts only strings ending in 'a'. Trace 'banana' through it. You just ran an automaton.
- 15–30
Explain
Here's the bombshell: there are clearly-stated problems no computer can ever solve, no matter how fast. The classic is the Halting Problem: no program can reliably decide whether any given program will eventually stop or loop forever. This isn't 'we haven't figured it out'; it's provably impossible.
- 30–40
Connect to the summit
Show students this is the real thing professionals build: CS103, the real thing. Proofs, logic, and the astonishing fact that some problems can NEVER be solved by any computer, ever.
- 40–45
Check
Run the formative check below. Anyone who can explain a key term in their own words has it.
Student activity
Draw a 2-state machine that accepts only strings ending in 'a'. Trace 'banana' through it. You just ran an automaton.
Slides
Formative check
- 1.In your own words, what is "Proof by induction"? (Looking for: Prove a base case, then that each case implies the next, covering infinitely many at once.)
- 2.In your own words, what is "Finite automaton"? (Looking for: A simple rule-following machine that accepts or rejects strings.)
- 3.In your own words, what is "Turing machine"? (Looking for: A minimal model of computation that defines what 'computable' even means.)
Carry-away concepts
- Proof by induction
- Prove a base case, then that each case implies the next, covering infinitely many at once.
- Finite automaton
- A simple rule-following machine that accepts or rejects strings.
- Turing machine
- A minimal model of computation that defines what 'computable' even means.
- Undecidability
- A problem that provably no algorithm can solve for all inputs.
From the summit · the Stanford source
You learn rigorous proof, set theory and logic, formal languages and automata, and the theory of computability and its hard limits.
This module descends from CS103 at Stanford. Students who climb the full ladder arrive here.