Page loading
Skip to main content
0%

Busy Beavers!

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.

Coming soon

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.

Coming soon

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.

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.

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!