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).
1. Uncomputable functions
In this intro chapter, we’ll discover that there are functions that you can’t write in JavaScript (or any other programming language).
2. Interpreters and universality
A modern developer’s laptop is littered with VMs, containers, code sandboxes, et cetera. The concept of simulation might seem obvious — but it certainly wasn’t when Alan Turing discovered the concept. In this chapter, we’ll implement an interpreter, which is the modern equivalent of Turing’s “Universal Computing Machine”, and which is key to understanding Turing’s solution to the halting problem.
6. Godel’s second incompleteness theorem
Not satisfied with one bombshell, Kurt quickly arrived at a second. So what if there are things our systems can’t prove? Perhaps those things are unimportant anyway. Well, Kurt’s second theorem finds a very important thing that these systems can’t prove: their own consistency!
In this chapter, we will learn why our systems, if they are consistent, cannot prove their own consistency. This builds neatly on top of the first theorem.
8. Just how busy can a busy beaver be?
Let’s play a game! We’ll write a JavaScript program of less than 10 characters that prints as much as possible before halting. Whoever’s program prints more is the busiest beaver, and they win the game.
What’s the busiest program? Just how busy is it? How can we find it? In this chapter, we’ll have a crack at these questions, but fair warning: we might not get many answers.
9. Quines and fixed points
Your DNA is a program that, when executed by a messy chemical computer (you!), spits out copies of itself. Are there JavaScript programs that perform the same trick when executed by node? What about Python? In this chapter, we’ll discover what a language needs in order to allow for self-replication.
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.”