---
Video Title: An Undecidable Problem
Description: Theory of Computation
https://uvatoc.github.io/week10 (also week9)

19.2 An Undecidable Problem
Nathan Brunelle and David Evans
University of Virginia
---

Last class, we talked about some
undecidable problems or languages,

undecidable functions.

So one example was this acceptance
language or this acceptance function.

The way that this behaved was he said,
if I gave you some Turing machine and a

potential input string, we
want to answer this question,

does that Turing machine
accept that input string?

So this is the
acceptance problem or the

acceptance function or
the acceptance language.

These are all sort of similar ways to talk
about the same thing.

What I'm going to talk about right now is
this language, ATM, so this acceptance

language, which is the set of all machine
input pairs, machine description input

pairs, so all strings where that's a
description of a machine and an input for

that machine, such
that that machine, when

running on that input,
will accept or return one.

So we'd mentioned this last time,
and the way that we sort of proved that

this was not going to be a computable
language was we constructed this tricky

contradiction, where we said, if we had a
Turing machine that did accept this

language, or that did
properly compute this

language, then we would
end up with this paradox.

Basically, what we did is we set up... we
can consider this a pseudocode,

where we said, if we had a machine that
computed accept for us, that computed this

acceptance function, or
this acceptance language

for us, we could define
this new function, m'prime.

So if I had this function for accept,
I could define some new function for m

'prime, where what m'prime did is it took
as input some string, which we're going to

say is maybe the description of a Turing
machine.

So this is maybe the description of some
Turing machine.

And all that this function did was it
invoked accept on that string with itself.

So where both the Turing machine
description and the input to that Turing

machine are the same string, and returned
the opposite of that.

So if we had an implementation for accept,
what this function m'prime was going to

do, it was going to say to accept, so what
is m going to do on the description of m?

So we ask this of
accept, and then return

the opposite answer,
whatever that might be.

So whatever accept says, we return the
opposite.

So what this means is, if we had this
description for accept, what we would do

is we would say, let's ask this question
of, what happens if we invoke m'prime on

itself, on its own source, on its own
description?

So we have this
function m'prime, I'm now

going to invoke m'prime
on its own description.

So let's see what happens.

So let's consider what happens if m'prime
on m'prime accepts.

Since we defined m'prime to
do the opposite of accept, so

whatever accept did, m'prime
would return the opposite.

So that means that if accept m'prime ends
up being true, so if m'prime does accept m

'prime, then accept
is going to return true,

which means m'prime
is going to return false.

So if m'prime accepts m'prime,
then that implies that accept m'prime,

comma, m'prime equals true, which we then
said implies by our definition of m'prime

that m'prime on m'prime equals false,
because we do the opposite.

So that's a contradiction.

We said if m'prime
accepts m'prime, then in that

case, accept m'prime,
m'prime is going to return true.

Since m'prime returns
the opposite of that, it's

going to return false,
which is a contradiction.

That means that m'prime did not actually
accept m'prime.

So now we have to consider the opposite
case.

So if on the other hand, m'prime on m
'prime rejects, then that's going to imply

that accept m'prime on m'prime equals
false, which in that case is going to

imply that m'prime on m'prime equals true,
which means that it should accept.

So we have a contradiction.

Either way, this tries to answer,
we end up with a contradiction.

So the only thing that broke here,
the only thing that could have gone wrong

with our assumptions was
that we had this function

accept, that we could have
written this function accept.

So if I could write a Python program for
accept, then it's totally reasonable for

me to define this new
Python program m 'prime,

which just invokes accept
and returns the opposite.

However, we knew that this Python program
m'prime could not exist.

Because then the universe doesn't make
sense.

So it must have been that accept couldn't
exist.

The only use case we're looking at right
now, or the only model of computation

we're looking at right now, is one where
probabilities don't really exist.

This theorem is useful in the sense that
we know now, so now that we have this

proof, we know that
asking this question of,

does this Python
program accept this input?

In the general case, just can't really
work.

It can never work.

However, this is useless in the sense that
for probably every single Python program

you've ever written, you've
been able to determine

whether or not it's going
to halt for some input.

So there is this disconnect here,
where we have this really, really potent

proof, where we said, you cannot compute
this function, but then you have your

personal experience that says,
when can't I?

It seems like I can.

And basically, the
reason is because this is

only applying for the
absolute most general case.

So only in the absolute
most general case

is this an impossible
function to implement.

If you make some assumptions about what
your program or what your Turing machine

looks like, you might be
able to solve this, and you

might be able to solve it
probabilistically as well.

But that's a different problem entirely.

So for instance, if you look at a Python
program that does not have any while loops

or recursion in it, then
you know that that's always

going to halt, just without
knowing anything else.

If it's got no loops at all in it,
let's just even do that simple one.

If it's got no loops at all, it's going to
halt.

So for those, you can definitely solve
this problem.

But this just says that no matter how hard
you try to solve this acceptance problem,

somebody could always come up with a
sufficiently convoluted example function

where you're not going to be able to get
the right answer for your implementation.

Programming language researchers do this
sort of thing all the time where they want

to determine whether or not your program
has a certain property.

We're going to see by Rice's theorem,
that's not something that we're really

going to ever be able to solve,
but they solve it all the time.

Basically, that's because
most programs that humans

write are going to be
well-behaved enough that you can.

All that this is saying, when we say that
this is not a computable problem,

is that you can't solve it in general,
so you shouldn't try.

Instead, you should
try to solve a particular,

more isolated version of
that same problem instead.

That answer required five minutes longer
than you were probably expecting,

but it's an important point, so thanks for
asking.

Thank you.