beavers Who are Busy

For the very first post of this blog I just wanted to explain what its name comes from. The name of the blog is a reference to the Busy Beaver function, which is a sort of abstract kind of function in computer science. The Busy Beaver function of n (which we’ll denote here as BB[n]) is defined as the largest possible output by a turing machine with n states, taking an input tape of all zeroes (What’s A Turing Machine?). This function has a few nice properties I’d like to share with you all.

*This post is more of an overview than a deep dive. If you have a good idea of how to work with turing machines, maybe try your hand at validating some of the more handwavey parts!*

Uncomputability:

That’s right, you can’t compute this function! Well, at least not using a digital computer. When we say that something is computable, we usually mean that it’s turing computable, which just means that there is a turing machine that models the function’s inputs and outputs. There are a few different ways of proving this result, but the way I’ll be showing you today will proceed in the following steps:

1. Prove that the Busy Beaver function never decreases
2. Suppose that there is some turing machine that models this function
3. Prove that the existence of said turing machine would imply that the Busy Beaver function does decrease, leading to a contradiction.

Step 1:

For the first step, imagine we have the turing machine in n states that gives us the output of BB(n), and we want to make a lower bound for BB(n+2) using it. One way would be this: Since we know the exact output of the machine and the state it ends in, as well as where the reader head is when it terminates (we can just run it to figure these things out), using our new extra states, we can just add a part to the end of the program which tells the reader head to either:

1. Move to the left until it hits a zero, then add a 1 (This will require 2 extra states)
2. Place down a 1 (This will require 1 extra state)

It will execute the first protocol if the reader head ends above a 1, and the second if it ends above a 0.

Since in both of the possible cases, we increase the output of the function by 1, we can say that BB(n+2) ≥ BB(n) + 1 > BB(n), or BB(n+2)>BB(n). We also know that BB(n+1) ≥ BB(n) (because you can reuse the best function from BB(n) and add on some useless extra states, at least). This is enough to prove that BB(n) doesn’t decrease.

Step 2:

Take a second to suppose…

Now we can move on.

Step 3:

Before we do the final part of the proof, I want to preface it by introducing a turing machine whose output will be larger than the number of states it uses (The reason why this is important will be shown later). Consider some turing machine D which takes in x and outputs 2x (We’ll just take it as a given that it exists here, but if you want, you can try to come up with your own!). By placing down a 1, then repeatedly composing D upon itself n times, we can attain an output that is equal to 2^n. If D uses k states, then the turing machine equivalent to its n-time composition would use n*k+1 states. For some n which is large enough, we’ll have that 2^n > n*k+1, and so this n-composition of D will have a larger output than its number of states.

For the final part of the proof, we’ll start by thinking about a turing machine constructed basically as the combination of two separate machines. More specifically, we’ll think about the turing machine which models the function you get when you compose D with itself a large number of times and run our supposed BB machine on the output. Lets call this machine Billy.

Just like before, let’s call the number of states used by Billy k, and the input to Billy’s BB stage n. Using a similar line of reasoning as before, we can say that if we compose D upon itself a large enough number of times before running BB, we will have that k+2 < n. Also, since Billy uses k states, we know his output must be less than or equal to BB(k). Since Billy’s output will just be BB(n), this tells us that BB(n) ≤ BB(k) while n > k+2. This is impossible though, since we proved in step 2 that BB(n) > BB(m) when n > m+2. Since every single step in our line of reasoning after we assumed that BB(n) was turing computable was correct, we know that said assumption must be where the error lies. Thus BB(n) is not turing computable.

Undecidability:

There is no turing machine that can tell you whether or not a given turing machine in n states outputs BB(n) when run on a tape of zeroes. This one’s proof is not extremely difficult once you know that BB(n) is not turing computable, so you might wanna try it for yourself!

Hint Incoming!

Try and find a way of using the hypothetical “Busy Beaver Predictor” to build a turing machine that would tell you what BB(n) is for any n (just a basic idea of its structure is fine).

Solution:

If we had a Busy Beaver Predictor, since we have a finite number of possible turing machines in n states, we would be able to build a turing machine that goes through all the possible turing machines and checks if each returns BB(n) using the predictor, until it lands upon a turing machine that does. We could then simulate the running of our “BB(n) machine”, and return its ouput. Thus, if we had a Busy Beaver Predictor, we would be able to make a turing machine that computes BB(n). Since we know this is not possible, it is also not possible to have a busy beaver predictor.

The Busy Beaver function is a fun way of introducing people to the world of theoretical computer science, so if you enjoyed reading this post, maybe tell a friend about the function as well. It’s always great to learn a new thing!

*Proofread by Alex Wang*