---
Video Title: ACCEPTS is Uncomputable (Part 1)
Description: Theory of Computation
https://uvatoc.github.io/week9

18.4: ACCEPTS is Uncomputable (Part 1)
- Defining ACCEPTS
- Why attempting to prove using Universal TM doesn't work

David Evans and Nathan Brunelle
University of Virginia
---

Let's get back to trying to find a
function that's worth computing,

even more worthwhile to compute than
self-rejecting, that is not computable.

What about this one?

It sounds like a much more natural thing.

We're going to define the language accepts
as the set of pairs of strings where the

first string is a description
of a machine and the

second string is an input
string to that machine.

And it includes the strings that would be
accepted.

The string mx is in the set if the machine
described by w would accept the string x.

Accepts here just means we run the machine
and it outputs a 1.

It runs to completion, it gets
to a halt, and what's on the

tape at the end with our input
determining function is a 1.

So is there a function that corresponds to
this language?

I'm trying to switch between languages and
functions a bit.

You should be comfortable with talking
about either language or their functions.

And mostly so far we've
talked about functions,

but how do we turn this
language into a function?

Yeah.

Good.

Yeah, so it's going to be a function that
takes the two strings as input.

And I should be clear, like when we're
talking about two strings as input to our.

Turing machine, the Turing machine has one
input.

It's what's on the tape, but we can come
up with some encoding.

Remember, we can add symbols to this.

So let's add a symbol and we're going to
encode the input as, here's the string w,

then there's the hash, and here's the
string x.

So the actual input is one string that's
on the tape, but we can always find some

encoding that allows us to think of that
as two separate inputs.

Our accepts machine is going to take those
two strings as input, and it's going to

if it's going to output one, else it's
going to output zero.

I think more natural to
think of things as functions

than languages, but
they're really the same thing.

So is this function computable?

Well, could we build a machine?

Remember, we just said
we can build a universal.

Turing machine that can
simulate any machine.

So a natural way to think about
implementing accepts would be to do that.

So we're going to take our universal
machine, we're going to feed in w,

we're going to feed in
x, and we're going to take

its output, and that's
going to be the output.

Is that going to work?

That seems like we've just designed a Turing
machine that can compute this function.

Okay, good.

Yeah, so definitely this should remind us
of self-rejecting.

So if we could build it, and then we could
build self-rejecting, something must be

wrong, because we know we can't build
self-rejecting.

That's a good point.

So what's wrong with... if we can
construct it, then maybe we should be more

worried about maybe our other proof was
wrong, because this seems much simpler.

But there's something that we're assuming
that's not true.

We've got to be careful what it means to
compute this function.

To compute it, we need... for any input,
we need to get the correct output.

That means it always needs to finish,
and it always needs to produce,

for any input we give it, the correct
output, which is defined by this.

It doesn't need to finish quickly,
but it does need to finish.

Does our universal machine finish?

Well, so w is always finite.

Our input's always finite.

Because we've got to write it down.

The tape's infinite, but the model that we
have, and there are sort of streaming

models or things that you could adjust
this, but the model we have is you write

your input down, and then you start the
machine.

So there's no way we can have an
infinitely long input, because we'd never

finish writing the input down,
and we'd never start the machine.

So the input is always finite.

These are both finite binary strings.

What the universal Turing machine is doing
is simulating m.

So if m would not finish, the simulation
won't finish either.

So this doesn't compute except, because
for some inputs, this might never finish.

It might run forever.

We don't know what the output is.

We're not going to get the correct output
if the simulation doesn't finish.

But we can't say, oh, it seems like it's
running forever, we should stop it.

And that means that the machine we're
simulating would not accept that string.

Because the only way to accept is if you
finish in output 1.

So if we knew it was
going to run forever,

we would know to reject
and we could stop it.

But at least just simulating in the Turing
machine what the universal machine is

doing doesn't tell us it's not going to
eventually finish.

You've seen that busy beaver, just the
five-state problem that I started last week.

It's still running, but it will eventually
finish.

So this is not a correct proof.

It's not computing accepts.

Does that mean it's impossible?

Is that enough to be convinced that we
can't?

Our definition of
accepting is it accepts only

if it halts and the
output is 1 when it halts.

So if we know the machine is never going
to halt, we know the output should be 0.

The output of accepts.

But if we don't get an output from
accepts, we haven't computed accepts.

And this wouldn't work because this might
run forever.

This might run forever.

And we never get our output.

And if it runs forever, it's not computing
the function it's supposed to compute.

But this doesn't prove that it's impossible
because there might be some other way.

This is just our first simple idea for how
to do it.

It doesn't work.

But if we're going to prove that accepts
is impossible, that's not good enough.

We've got to show that there's no way to
do it.

So we're going to need something stronger
than that.

We're going to need something that says,
if we could do this, our world falls apart.

We get a contradiction.

Everything is broken.

Let's go to the next slide.