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
(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
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.
3. The halting problem
Or, Turing’s trick to troll any termination test
Perhaps your IDE has warned you before: “this code is unreachable”. How useful! Can we get your IDE to warn you about all lines that are unreachable. Back in 1936, before computers really existed, Alan Turing was already thinking about this problem, and he has bad news for you ...
(This chapter is free while stocks last!)
5. Gödel’s first incompleteness theorem
Back in 1931, Kurt Gödel published his first mathematical mic-drop: “Our formal systems of logic can make statements that they can neither prove nor disprove.” In this chapter, you’ll learn what this famous theorem means, and you’ll learn a proof of it that builds upon 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.
7. Rice’s theorem
Your coworker’s function
is_ip_address could be replaced by a regular expression. Perhaps your IDE could recommend when a function can be replaced by a regex? Unfortunately, Henry Rice showed in 1951 that this check, along with many others like it, is impossible. Let’s follow the proof.
8. Just how busy can a busy beaver be?
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
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
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.”