A gentle introduction 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!
What’s in the course?
Ten chapters. Many are still in the oven, and they’ll arrive when they’re cooked. You’ll get your money’s worth.
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.
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.
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).