---
Video Title: Proof by Reduction
Description: Theory of Computation
https://uvatoc.github.io/week10 (also week9)

19.3 Proof by Reduction
- Proving other Languages are Undecidable
- MacGyver saves the day!
- Reduction
- Pitfalls in Reduction Proofs

Nathan Brunelle and David Evans
University of Virginia
---

What we're going to do next
is we're going to find some

way of proving that other
languages are undecidable.

So we have two of them.

We have two non-computable languages or
non-computable functions, halt and accept.

Both of those were proved in kind of the
similar way.

We had a very similar contradiction for
both of those last class.

What we're going to talk about today is
how we can do more.

Those contradictions
are not something that

is going to be easy to
do for extra languages.

Those are sort of special
languages or special functions

that lend themselves to
that sort of contradiction.

What we're going to be
talking about today is a more

general way of proving more
languages to be undecidable.

And the technique we're going to use for
this is something called a reduction.

The idea of a reduction is that we can
show relationships between two entirely

different functions or different
languages.

We're going to show that a new language or
a new function is undecidable by relating

it in a particular way to a function we
already knew was undecidable.

So to show f is not computable,
we're going to, in a special way,

relate f to, let's say, f prime,
which isn't computable,

which we somehow already
knew wasn't computable.

So we're going to be leveraging our
knowledge that some function f prime

wasn't a computable
function in order to show

that this new function
f is not computable.

So the idea of reduction
is just show how two

different functions
relate to one another.

So in order to demonstrate this, we're
going to watch a little bit of a movie.

I got jealous of Professor Evans showing
you a movie last class.

So I decided that I'm going to show you a
movie this class too.

This is from a TV show from the 80s called
MacGyver.

Basically, the premise of this TV show is
that there is this guy who catches bad

guys and finds himself in these impossible
situations where he uses his own ingenuity

and just the resources around him to get
himself out of those situations.

So the setup for this scene is MacGyver
has been knocked unconscious and then

thrown into the storage closet of a bar by
the bad guys.

And they locked him in there.

He's got to figure out how to get out.

So what he's done is
he's found a piece of

duct that was just laying
around conveniently.

And he's strapping that to the floor.

And now since he's in the back of a bar,
this is a keg of beer that he is putting

into that duct and it happens to be a
perfect fit.

Now I guess he's taking out the trash or
something.

I'm not sure.

That is some high proof alcohol he's
dumping on the wood.

Followed by the world's most convenient
book of matches, the 80s music intensifying.

And now he can go out.

OK, so what MacGyver just did,
that was a reduction.

So MacGyver had this
problem that he was trying to

solve, where that problem
was that of opening a door.

So MacGyver had to open a door.

He had this problem he was trying to
solve, this function he needed to compute,

which was this opening a door function.

And what he did is he converted that.

He related that or reduced
it to this different problem,

this entirely different
problem, that of lighting a fire.

So he reduced the problem of opening a
door to that of lighting a fire.

And the way he did that
was he provided a function

that would kind of do
that conversion for him.

So he showed that the
problem of opening a door can

be converted into the
problem of lighting a fire.

And the way that he did that is by showing
that some way that I could light a fire,

in particular the way that he used,
was alcohol wooden matches.

So he had some way of lighting a fire,
he showed that that could be used in order

to build this Keg Cannon
battering ram, which

ended up being a
solution to opening a door.

So Keg Cannon battering rams, that opens
doors.

So the problem he needed to solve was
opening a door.

The way he decided to solve that was by
reducing it to lighting a fire,

because he knew that by solving this
lighting a fire problem, he could produce

a Keg Cannon battering ram and have a now
handy door opener.

So the way that we're going to use this
idea of reductions is to, in some sense,

compare the difficulty of two problems.

Undecidable problems,
non-computable problems, we're going

to consider those to be
really, really hard to solve.

Non-computable functions are hard
functions to compute.

So we're going to show other functions are
non-computable by using reductions in

order to show the relative difficulty of
these problems.

So what we show here is we show this
problem A of opening a door is not a

harder problem to solve than that of
lighting a fire.

So basically the idea here is as long as I
had some way of lighting a fire,

I don't care which way it was to light a
fire.

Alcohol, wood, and matches seems to work.

If I happen to have gasoline, that would
probably work too.

But any way I have of
lighting a fire, that can

be used to build a Keg
Cannon battering ram.

MacGyver showed us that.

He proved that to us.

So that means that assuming I can light a
fire, opening a door is easy.

So assuming I can light a fire,
opening a door is easy.

This also means that if I somehow already
knew, if I somehow totally believed that

opening a door was really, really,
really hard to do, I must also be able to

conclude that lighting a fire was going to
be hard to do.

Because if I could light a fire easily,
then I could open a door easily.

So if opening a door was hard,
lighting a fire must also be hard.

So this is how we're going to use this
idea of reductions.

So because we could solve opening a door
by solving lighting a fire, I knew that

this problem of opening a door
was not substantially harder,

was not really any harder
than that of lighting a fire.

Lighting a fire was sufficient for opening
a door.

So what we're going to do is, if I have
this problem, this function, this

language, something like that,
let's call this A, if I can reduce A to B,

pay very careful attention here, this
might look backwards, but it's correct.

If I can reduce A to B,
then that means the difficulty

of A is less than or
equal to the difficulty of B.

So oftentimes the way we denote these
reductions is with this less than or equal

to sign that is kind of comparing the
difficulty of computing those two things.

So the difficulty of computing
A is less than or equal

to the difficulty of computing
B, because A reduces to B.

So what we're going to do is we're going
to be proving the impossibility or The

non-computability of certain functions
using this idea of reductions.

So let's say that I had a problem that I
knew was going to be impossibly difficult.

For instance, opening a door.

So opening a door is something that...

Let's say that I was somehow totally
convinced, the bad guy was totally

convinced, that it was going to be
impossible for MacGyver to open that door.

So here we have something we knew to be
impossible.

What we're going to do is, if I have this
reduction, if I had some way of solving

this separate problem, for instance,
lighting a fire.

So let's say I had method Y for solving
lighting the fire.

Because I had this reduction, where I
could actually take my solution Y to the

lighting a fire problem, and I could do
some sort of weird maneuvering in order to

convert it to some solution for the
opening a door problem.

Yeah, I know, unnecessary PowerPoint
animations.

But if I could show some way of
manipulating this solution to Y to become

a solution for opening a door,
then since I knew X wasn't possible,

and once I had a method
for using Y to perform X,

I must be able to conclude
Y isn't possible either.

So this is kind of a fancy
proof by contradiction, a special

kind of proof by contradiction
that we're seeing here.

We knew that X wasn't possible.

This is something we knew coming into
this.

Let's assume, towards reaching a
contradiction, that Y is possible.

Because I had this reduction, where a
reduction says I could use Y to do X.

I could use Y to solve X.

So if I had some way of using Y to solve
this problem X, then since I knew that X

wasn't possible, I must have been wrong in
my assumption that Y was possible.

Because otherwise I
could have used Y to

build my keg cannon
battering ram and solve X.

So therefore, our conclusion is Y is not
possible.

Let's say that I'm the mob boss or
something like that.

So I'm telling you, my henchman,
to lock MacGyver into the storage closet.

And you have convinced me as the mob boss
that it is totally impossible.

You've just definitively proven factually
that it is totally impossible for MacGyver

to break out of that storage closet that
has things like kegs and so forth.

Then somewhere along
the line, I must have

also been convinced
he couldn't light a fire.

So if we were like, let's try this again.

I want you to again lock MacGyver into
that storage closet.

If you locked him in there with matches
and high-proof alcohol and wood,

then he could get out of there by building
a keg cannon battering ram.

So if it's definitely impossible for him
to get out of there, then necessarily it

must have also been impossible for him to
light that fire.

So that's how we're using this.

So if, hypothetically, so if we knew,
walking in, we were just totally convinced

that it was impossible for MacGyver to get
out of that storage shed, then if we had

assumed that it was possible for him to
light a fire, since he could have used

that fire to open the door, our conclusion
is the fire wasn't possible.

Basically, the reason
that it becomes a proof

by contradiction is
because of step two.

We assumed something that was false.

So what we're going to do is I'm going to
show you how we can use this idea.

We're going to show how
we can show in a different

way that the halting
function is not computable.

Walking in the door, we
knew that there was not a.

Turing machine to decide
the acceptance function for us.

So ATM was that acceptance language.

So there is not a Turing machine that
could do that acceptance problem for us,

that could solve the acceptance problem
for us.

So we know that already.

We have proven that independently of
anything else.

We just know that to be a fact.

So let's assume, towards reaching a
contradiction, that is, that I have some.

Turing machine that's
going to decide the problem.

B, which I'm going to
say is the halting problem.

So let's say that problem B
is the halting problem, and

I have some Turing machine
that's going to decide it.

What I'm going to do is I'm going to show
how I could use this solution to HALT

in order to make a solution for the
acceptance problem.

I'm just going to describe some method
where if hypothetically I had a function

or I had a Python program or a Turing
machine that could compute HALT for me,

I could use that to compute the acceptance
problem for me.

Whatever method that looks like,
since we knew X didn't exist, there wasn't

anything that could decide ATM,
that acceptance problem for us.

But we could use this
solution to the HALTing

problem to make a solution
to the acceptance problem.

Our conclusion must
be that we couldn't have

actually built that solution
to the HALTing problem.

So we're going to use our knowledge that
ATM was impossible to solve in order to

demonstrate that HALT was impossible to
solve.

So we've already shown that
HALT was impossible to solve,

we're just going to prove
it in a different way now.

Before we carry on, let's consider the
opposite.

So let's explore this
technique, the powers and

limitations of this reduction
technique a little bit.

So what we did is we showed that a
solution to this problem of lighting a

fire could be used to make a solution to
this other problem, opening a door.

Does this mean that they're equally as
difficult?

So the question is, what about the
opposite?

Does this mean that if I
could open a door... so we

showed that if I can light
a fire, I can open a door.

Does this mean if I could open a door,
then I could light a fire?

Yeah, so the answer is no, I'm seeing lots
of this.

Because there's lots of There are a number
of ways to open doors.

For instance, I could use an axe.

If there was an axe in the room,
then I didn't need MacGyver to light a

fire in order to be able to open that
door.

So there might be other ways besides
solving problem B in order to solve A.

So this does not mean that they're equally
difficult.

This does not mean that the opposite is
going to be true as well.

This only works in one direction,
is the important thing here.

Also, be careful about the direction.

A lot of what you're
going to see, a lot of

the notation, seems
to be counterintuitive.

Something to keep in mind is that when you
see less than or equal to, you're

comparing the hardness of two different
problems.

So, let's say that I'm using a
solver for problem B in order

to solve problem A, showing
that A is not harder than B.

What reduces to what?

Fill in the blank with A and B in these
two blanks.

Which one is which?

So in this case, we're
using a method for solving.

B in order to produce
a method for solving A.

Which one's the door?

Which one's the fire?

So which one's the door?

Yeah, which one's the door?

We're using a solver for B to solve A, so
the end problem we're trying to solve is A.

So that's the door.

And B is going to be the fire.

So what reduces to what?

Yes.

So we're going to say A reduces to B.

The problem of opening a door reduces to
the problem of lighting a fire.

Something else to keep in mind is that
your transformation must only be things

that you can do, that are permitted for
you to do.

Basically, in this case, what
can-do means is anything

that you can do with a Turing
machine that always halts.

Reductions can be used for lots and lots
and lots of different things.

If you haven't already, you will see also
reductions in your algorithms class.

We're going to be using them again for
another topic later this semester as well.

The thing that you can do changes on your
application.

For this application,
you're allowed to do

anything that a Turing
machine can do and help.

Is.

The어떷 card included