Mathematical Foundations of Computing
Proofs, logic, and the 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.
Lesson overview
Proofs, logic, and the fact that some problems can NEVER be solved by any computer, ever.
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.
- 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.
- 15–30
Explain
Some clearly stated problems can't be solved by any computer, however 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
Read aloud the "From the summit" section below. Ask students which ideas from today they recognize in it.
- 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.
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 is based on a Stanford course.