Page loading
Skip to main content
An illustration of a beaver writing numbers on a very long roll of tape

Busy Beavers!

An interactive intro to Computability Theory

What can computers do? What are the limits of mathematics? And just how busy can a busy beaver be? In this course, you and I will take a practical and modern approach to answering these questions — or at least learning why some questions are unanswerable!

The only prerequisite is that you’re comfortable coding. I prefer code like f(x) instead of math squiggles like . Less s, more gs. I try to use modern concepts (strings) instead of the original hacks (Gödel numbering). I do examples first; abstraction later. I emphasize real-world languages (mainly JavaScript) rather than Turing Machines and pseudocode.

(If you want to know when a new chapter comes out, sign up for updates here!)

What’s in the course?

Ten chapters. Six are still in the oven, and they’ll arrive when they’re cooked. You’ll get your money’s worth (or your money back).

One more chapter to be announced. Watch this space.

Who am I?

I’m Jim. I studied computer science at Imperial College. I also have ten years of experience in the software industry — enough to know that you’ll probably never need any of this computability theory to make cool stuff, but you might need it to impress your friends.

I also write at jameshfisher.com. You might know me from some phishing techniques I discovered. I also happen to be the creator of TigYog, the app that this course is built with.

What people are saying ...

Over 30K learners have completed chapters in Busy Beavers. Here are some things that they’ve said about it.

⭐⭐⭐⭐⭐ “Probably the best intro to computability theory I’ve ever seen.” — David Brumley, professor at Carnegie Mellon and ForAllSecure CEO.

⭐⭐⭐⭐⭐ “A great, accessible way to introduce Lean to my students!” — Tyler Josephson, chemical engineering professor at UMBC.

⭐⭐⭐⭐⭐ “Your Busy Beavers course reminds me of how it felt to read a book when I was a kid. You’ve taken theory that’s usually packed in a scary thick textbook, and turned it into a book that children could read. Awesome work!” — Reviewer by email.

⭐⭐⭐⭐⭐ “This was very satisfying. The format works well, and makes sure you as reader are doing at least a minimum amount of thinking about the topics being presented. Even the pops and dings (if you have sound on) are fun 🙂” — Reviewer on HN.

⭐⭐⭐⭐⭐ “Absolutely fascinating and a lot of fun!” — John George, Senior DevOps engineer, by email.

⭐⭐⭐⭐⭐ “Thanks for your hard work and attention to detail; this entire series has been delightful.”Reviewer on Lobste.rs.

Glossary of unused words 📖

Standard writing on computability theory has its own weird vocabulary. I try to avoid using it, and instead use modern developer vocabulary. Here are some examples of weird words you won’t see much of in this course.

Decidable, adj. If you can write isMember that returns whether a value is a member of a set, then the set is decidable, or recursive, or computable.

Diverge, v. To run forever; to never return or exit. (Can also include throwing an exception.)

Function, n. An abstract mapping from one set to another, e.g. “the function that maps programs to whether they halt or not”. Not the same as what developers call a function, which mathematicatians would call an “algorithm” or “procedure.”

Gödel number, n. A number that uniquely identifies a program. Nowadays we identify programs by their source code instead, and we have no need to assign numbers to programs.

Language, n. A set of strings, e.g. ["foo", "bar"], or all strings that only use the character "a".

Partial, adj. Undefined on some inputs.

Recursive, adj. See decidable. Not the same as what developers call “recursive”, which is a function that calls itself.

Recursively enumerable, adj. If you can write listMembers that prints out all members of a set, then the set is recursively enumerable.

Semantics, n. Generally means “the input-output behavior of the code.”

Quoted text:

Your feedback will be sent privately to the author. They may reply to you by email. Thanks for helping make this course better!