B. Symbolic Systems

B.3 Computation and Information

Phase: Phases 1–5
Study time: about 330 hours
Prerequisites: nothing to start; B.1 proof before the theory unit
Leads to: B.2, C.3, E.2, E.3
Signature checkpoint: Nand to Tetris CPU passes all tests

Course description

Begin with Python, using Automate the Boring Stuff with Python alongside Harvard's free CS50x

[1]

or Downey's free Think Python

[2]

for a more structured route through the same fundamentals: conditionals, loops, functions, lists, and dictionaries. Write small programs as you go; the skill is breaking a task into steps you can specify exactly. Once the basics hold, move to data structures and algorithms: arrays, linked lists, stacks, trees, and graphs, then sorting, searching, and graph traversal, using Sedgewick's Algorithms or the free Problem Solving with Algorithms and Data Structures using Python. Learn enough Big O notation to say why one algorithm beats another. Ada Lovelace's 1843 notes on Babbage's Analytical Engine, especially Note G's procedure for computing Bernoulli numbers, are worth reading directly; whether she or Babbage deserves credit as "the first programmer" is itself a live historical argument, and following it is more instructive than repeating the label. Alan Turing's 1936 paper "On Computable Numbers"

[3]

, which defines the abstract Turing machine and the limits of what any computer can decide, is heavy going but is the paper that made "computation" a mathematical object.

For how computers actually run programs, build one from the bottom up: the Nand to Tetris project

[4]

takes you from NAND gates through logic, a CPU, an assembler, and a compiler, with test scripts that check each stage automatically, and Petzold's Code is the readable companion for the same material. You do not need to become a hardware engineer, but you should come out understanding what a bit, a byte, and an instruction actually are. Learn enough SQL to query a table and enough HTML and CSS to make a page. For machine learning, Andrew Ng's Machine Learning Specialization (Coursera and DeepLearning.AI, 2022) is a reasonable entry point. Learn what the P versus NP question asks, without trying to prove anything about it.

Claude Shannon's 1948 "A Mathematical Theory of Communication"

[5]

is readable in its opening sections and is where entropy gets defined as a measure of average surprise, alongside source coding and channel capacity, the two questions of how much a message can be compressed and how fast it can be sent reliably. MacKay's free Information Theory, Inference, and Learning Algorithms

[6]

, chapters 1 through 6, gives the formal treatment once Shannon's paper has set the questions up. This connects forward to C.1's thermodynamic entropy and to E.3's use of information measures for complex systems.

Checkpoints

Each checkpoint is tagged with the stage of the cycle it tests.

Stage	Checkpoint	Attempts
formalism	Without following a tutorial, write a program that simulates projectile motion with air resistance and plots the trajectory.	Post the first attempt
formalism	Implement binary search and Dijkstra's algorithm from scratch and state their running times.	Post the first attempt
formalism	Complete the Nand to Tetris CPU project with every supplied test passing.	Post the first attempt
skepticism	Reproduce Turing's diagonal argument that no single program can decide whether every program halts.	Post the first attempt
formalism	Compute the letter-frequency entropy of a large English text, compare it against the 4.14 bits per letter that Shannon estimated from letter frequencies alone[^shannon1951], then write a Huffman coder and check its compression ratio against that entropy.	Post the first attempt
abstraction	Explain what Shannon entropy and thermodynamic entropy share formally, and where the analogy between them breaks down.	Post the first attempt

Discussion

Proposed edits

Found an error, a missing idea, or a better source? Propose a change. A moderator reviews each proposal.

Sources

Previous: B.2 Next: B.4