---
Video Title: Proving Uncomputability (Busy Boas and Busier Beavers)
Description: Theory of Computation
https://uvatoc.github.io/week10

21.3 Proving Uncomputability
- Busy Boa Problem
- Busy Beaver Bound

David Evans and Nathan Brunelle
University of Virginia
---

To prove on computability, we've got to
find some way to get a contradiction.

It can be by doing a
reduction, or it can be

some more direct way
of getting a contradiction.

And for certain problems, getting a direct
contradiction is easier.

For other problems, getting a reduction is
easier.

In theory, you can always use either
strategy for any problem.

But often times, if you don't have a
similar problem to start with,

doing the reduction is going to be harder
than getting a contradiction.

And I'll mention, for
this one, if you try to

solve this by doing a
reduction, it's really tough.

The reason that there's a straightforward
way to do that is to show that,

well, because we're doing idealist Python,
we have plus.

So we can always add something to the
output of BOA.

What should n be there for this to get a
contradiction?

Yeah, so let's... well, we need to have a
function.

Getting a contradiction by writing Python
code is a lot shakier than getting a

contradiction by writing
a Turing machine,

because it assumes
everything in Python exists.

But we're using idealist Python,
which does exist.

Well, it doesn't exist,
but in idealist Python,

we can assume
everything we expect exists.

So we're going to have some contradiction,

and it's going to return...

What this n should be is the length of
what we're defining.

Because whatever BOA returns
for that length should be the

biggest number that any
function of that length can return.

And that's certainly well-defined.

There's some value that's the
biggest thing you can return by

a function of that length, and
we're going to add one to it.

But that length was the length of the
function including the add one.

So it's a contradiction, right?

There's nothing it can return that is
actually the correct value.

So it must not exist.

But what about this one?

Now we're going to define...

And this gets to be a pretty weird thing.

So you've seen some BusyBeaver problems.

And maybe it's not
that surprising that, well,

you can't compute the
exact value of BusyBeaver.

Because that sounds like it's a
complicated function.

Maybe that's why we can't compute it.

So what this is asking is, can you
actually compute an upper bound on it?

And in this case, because it's an upper
bound, it's not just one function, right?

It's a whole set of possible functions.

Any function that always returns a number
bigger than the actual...

In this case, we're
talking about the furthest

tape cell, but it could
be the number of steps.

Any function that returns a number bigger
than that is okay.

To me, it's a much weirder result in some
sense that you can't compute it exactly,

that you can't even compute an upper
bound.

But let's prove that you can.

Part A, is this well-defined?

Is there some natural
number that is the correct

value, that would be
a correct value, right?

There could be more
than one for this beyond.

B function that I've
defined for any input.

If you knew a particular machine,
so for any given machine that halts,

you could run that
machine and you could look

at the furthest tape
square that it writes into.

There's some natural number that is the
number of that tape square.

So that must exist.

Why can't we compute it?

So how would we prove that this is
uncomputable?

So let's assume that we can compute it.

This is the way all of our
getting a contradiction to

something being computable
proofs are going to start.

We're always going to
have to assume that we can

compute it and there's some
machine that can compute it.

And now we want to use that machine to
produce something else.

And usually halts is a good thing to try
to produce.

It doesn't have to be halts, right?

It can be anything that you already know
is uncomputable.

But let's see if we can make halts.

So suppose you know the furthest tape
cell.

Do you know how many different configurations
of the Turing machine there are?

If it never writes beyond cell Z,
right?

So we've got Z as the...

If it computes it, we can get that number.

Do we know how many different
configurations there are of the Turing

machine if we know Z is the beyond number
for the number of states?

Well, now we don't have an infinite tape,
or we don't need an infinite tape.

If we know that we never write past cells
Z, our tape is from zero to Z.

So we know that the number of
configurations is finite.

So there are something like the size of
the tape alphabet to the Z times,

well, it's also times the number of finite
states.

So it's big, right?

It's some big number, but it's finite.

So in order for a Turing machine to not
halt, if we know these are all the

possible configurations, what would happen
for it to not halt?

Yeah, it would have to repeat.

If it repeats a configuration,
it's going to not halt.

If it doesn't repeat a
configuration, in order to halt, it

has to eventually get to a
configuration where it stops.

That means, at most, it can be in this
number of different configurations.

If it goes past that, it has to have
repeated one.

If it repeats a configuration,
it's going to repeat forever.

So that means that we can simulate a
machine up to about that number of steps.

We'd have to attempt it, but there's some
finite number of steps that we can compute

based on z that if we simulate the machine
for that number of steps, or we could even

keep track of the
configurations, it must have

repeated a configuration
if it hasn't halted.

So we can implement halts by running for
that number of steps.

If it hasn't halted by that
number, it's never going to halt

because we have a bound on
the number of configurations.

Yeah.

Oh, yeah, what's a configuration?

Turing machine has the state that it's in
and the tape.

So the configuration is the current state
and everything on the tape.

So that means it's everything
about the execution state

of the Turing machine is
captured in that configuration.

The finite state that you're in and
everything that's on the tape.

So if the number of configurations is
finite, Then your execution either repeats

configurations or it eventually stops within
that number of possible configurations.

Without knowing z, the number of
configurations you don't have a bound on.

Because the tape is infinite, you can
always generate a configuration you've

never seen before if you go off the edge
of the tape and write a new symbol.

But if you know that you
never go past slot z, then

you've got a bound on the
number of configurations.

That gives you a bound on the number of
steps you could possibly go without

repeating, which allows
you to know either the

machine will halt before
then or it will never halt.

So this is the configuration.

So we're in a Turing machine, we've got
our states, and we've got our tape.

If we're in the same configuration,
right?

Same configuration means we are in the
same state and this tape matches exactly.

We're always going to do the same thing.

The rules are deterministic.

Each rule here is based on what's on the
tape, where you're reading.

If everything's the same, it's always
going to do the same thing.

So it must be an infinite loop if you ever
get to exactly the same configuration,

which means you're in the same state and
everything on the tape is the same.

Once you repeat a configuration,
whatever you did after that, so from that

point, you could do a whole bunch of
stuff, go through a whole bunch of states,

write a bunch of stuff on the tape.

But if you ever get back there,
you're going to do exactly the same thing.

If what's on the tape is the same as what
was on the tape the last time,

that means the whole tape, not just the
square you're looking at.

To be the same configuration, the whole
tape's the same, the same state,

you're going to do the same thing.

So the only thing you can
do is run forever if you've got

back to the same exact
configuration you were in before.