Skip to content
Truth Academy.
Truth Academy
← All modules
How Computing WorksCore45 min

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.

Big Idea

How Computing Works

Grade bands

K-2 · 3-5 · 6-8 · 9-12

View on the ladder →

Lesson overview

Proofs, logic, and the fact that some problems can NEVER be solved by any computer, ever.

Teacher script · 45 min

  1. 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.

  2. 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.

  3. 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.

  4. 30–40

    Connect to the summit

    Read aloud the "From the summit" section below. Ask students which ideas from today they recognize in it.

  5. 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

1Title: Mathematical Foundations of Computing
2Hook: Being sure, not just pretty sure
3Do it: Machines made of rules
4How it works: Some things are uncomputable
5Key idea: Proof by induction
6Key idea: Finite automaton
7Key idea: Turing machine
8From the summit: the Stanford course

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.