---
Video Title: Busy Beavers
Description: Theory of Computation
https://uvatoc.github.io/f20/week8

17.4: Busy Beavers
- Describing Turing Machines
- Example TM
- Busy Beavers

David Evans and Nathan Brunelle
University of Virginia
---

Here is a Turing machine.

We can draw it.

We're drawing it and
sometimes I think drawing is

more confusing than
just listing the transitions.

So this is the way that we're drawing it,
where this is our delta function.

We've shown the delta function,
if you remember the definition,

this is our delta function.

The delta function takes a state and a
symbol and outputs a triple.

So, if we draw that, we're
going to draw the states, and

we're going to use the
edges to show the other things.

That's what this means.

So, this is the two inputs.

That's this transition rule, where this is
the read symbol, this is the write,

this is the direction, and this is the
next state.

So, I have a simple four state machine,
so you should be able to execute that.

So, I'll give you a little while to figure
out what this machine does.

There's no input.

It starts with a completely blank tape.

So, you should be able to
execute this, and you can work

with people nearby you
to figure out what this does.

If anyone gets the
exact answer, within the

time I have, I have a
special prize for you.

There's a good reason humans should not
simulate machines.

Good to understand what
it would mean to simulate it,

but we should have machines
that can simulate machines.

We have a Turing machine simulator.

So, here's the program.

This simulator also starts in state zero.

I've labeled the states A, B, C,
D.

So, there's four states,
but to make things simpler,

there's a state zero
that does that transition.

This is encoding the same rule.

The underscore is the blank, and the one
is the one.

Those are the two symbols we're going to
use.

We're not going to use zero.

Zero is too easily confused between zero
and blank.

So, this is the rule.

It says, if you're in state A, and you
read a blank, you should write a one.

Then, you should move
the tape head, move I to

right, that means increase
by one, and go to state B.

Unless I made a mistake, encodes the same
machine.

So, now we can take advantage of having
computers to run it.

We're in state A.

We wrote our one, and we moved right.

And now we go again.

How far did anyone get simulating it in
your head, or on paper?

So, we've gone now, how many steps?

We've gone 17 steps.

Any idea what it's going to do now?

Do we think it's going to run forever?

It's pretty hard to tell.

That's something we'll get into more soon.

But we can let it run, and it runs for 108
steps and stops.

So, this is actually a special Turing
machine.

If you only have four states and two
symbols, the longest you can make a

machine that runs for and still eventually
stops is 108 steps.

This is known that you can't
have a four state machine

with two symbols that runs
for more than 108 steps.

If it runs for more than 108 steps,
it means it's going to run forever.

Okay.

So, what if we had another state?

How long do we think it's going to run
for?

Should we try it?

We have a five state machine.

And we will start that one running.

It's fast.

Okay.

So, this one's running a little faster.

So, we only have one more state,
still two symbols.

So, I started this one running in my
office last week.

It's still running.

This is how far it got in my office.

It got up to about two and a half million.

It will actually stop after 47 million
steps.

And this is what's the best known five
state machine.

Best meaning runs for the most steps.

Whether that's best depends on what your
hobbies are.

But it runs for 47 million some steps.

And eventually does stop.

The BB stands for busy beaver.

But it's not known if this is the best.

There might be a better five state
machine.

We know one that runs for 47 million
steps.

Which is this one.

Which is having fun.

Going up to 40,000 now.

Will not finish before the end of class.

Yeah.

The definition of the busy beaver problem.

Is that it runs for some number of steps.

And does stop at the end.

It's the Turing machine that runs for the
most steps.

And eventually stops.

For any number of states.

There's some machine that satisfies that.

That's going to run for some number of
steps.

What's interesting about it.

The numbers get so astronomically huge.

Five states.

We're only up to 40 some million.

Once you get up to six states.

You're up to like 10 to the 10 to the 10
to the 10 to the 10.

Like the hugest numbers you can think of.

And there's a nice blog post.

About how huge these numbers get.

The largest numbers you can imagine.

Is what you get by adding a few more
states here.

But they're still finite.

And the way it's defined.

It has to be finite.