Don’t ask this particular beaver to do your work for you.

It can’t.

Which beaver is it?

The BUSY BEAVER.

Remember in the post about Rayo’s number, I talked a tiny bit about the Busy Beaver function? We’re going in depth today!

So the Busy Beaver game/machine is a Turing machine game with… you know what?

Let’s talk about a thing called n-state busy beaver game.

The machine has n states, and also another state called HALT. Out of the states, one of the states is a starting state. Typically, if the states were named 1, 2, 3, 4, … then the starting state must be 1. The Turing machine uses a two-way infinite tape, left and right, so no going in two dimensions. The tape uses an alphabet of just {0, 1} like a light being on or off.

The machine has a transition function, which takes two inputs: the current state the machine is in that is not HALT, and the symbol of the cell the machine is in. The three outputs are: the symbol that needs to overwrite the current cell, a direction to move, and the state to transition to, which may be the HALT state. In the overriding, it may be overridden with the symbol it was originally at.

BB(1) = 1, BB(2) = 4, BB(3) = 6, BB(4) = 13, BB(5) ≥ 4098, and BB(6) ≥ 3.514 * 10^18276. That’s how large the numbers are.

BUT WAIT THERE’S MORE!

In the post about Rayo’s number, we talked about the Super Busy Beavers.

Super Turing machines.

They know if a Turing machine will stop, like a halting oracle. (Yes I know this is directly copied from Numberphile) If a Turing machine has this “halting oracle”, then it’s a super Turing machine. You can compute the Busy Beaver numbers through these super Turing machine.

That’s it?

Yes.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.