---
Video Title: HALTS is Undecidable
Description: Theory of Computation
https://uvatoc.github.io/week10

19.4 HALTS is Undecidable
- HALTS and A_TM
- Reduction Proof that HALTS is Undecidable

Nathan Brunelle and David Evans
University of Virginia
---

Now let's use this reductions technique in
order to show, using a different method,

that the halting language is undecidable.

ATM is this acceptance language
which says all of the machine

input pairs such that that
machine accepts that input.

Halt is this halting language,
or if we give it machine input pairs,

it is going to return true if that machine
halts when it runs on this input.

So something to keep in mind is that in
order to accept, in order for a Turing

machine to accept an input, it had to halt
on that input first.

The only way to accept is to halt first.

So that means that every
Turing machine description

pair that belongs to
ATM also belongs to Halt.

So ATM is a subset of Halt.

Because in order to accept, we had to
halt.

Everything that accepts also halts, but
not everything that halts also accepts.

Because you can halt and reject.

We're going to use this idea for our
reduction.

We're going to use this observation for
our reduction.

So to show that Halt is undecidable,
is not computable, using our reduction.

Halt, recall, is every machine
description and input pair

for which that machine is
going to halt on that input.

So in order to show that Halt is
undecidable, this should be ATM.

We're going to show that ATM isn't any
harder than Halt.

So we went to use a solver for blank to
build a solver for blank.

So one of these blanks has Halt in it,
one of these blanks has ATM in it.

Which is which?

Discuss that with your neighbors.

Which one goes in the first blank?

Halt or ATM?

So we want to use a solver for HALT in
order to build a solver for ATM.

So in this case, what we're trying to do
is to show HALT as undecidable.

Right, so that's the thing that we want to
show is impossible to do.

ATM is the thing we already knew was
impossible to do in this circumstance.

So we knew that ATM was impossible.

We want to show that HALT is impossible.

So what we want to do is
say then that if HALT was

possible, then we could use it
to accomplish the impossible.

So since we knew ATM was impossible,
we wanted to show that we could use a

solver for HALT in order to build a solver
for ATM.

So that if HALT was possible, since we
could have used it to do the impossible,

HALT must have been impossible as well.

So, in this case, ATM is playing the role
of the door.

Halt is playing the role of the fire.

We're going to come in in advance knowing
this door can't be opened, and we're going

to use that fact to demonstrate lighting a
fire was impossible.

So, that's what we're going to do.

Here's what our reduction is going to look
like.

Let's assume, towards reaching a
contradiction, that halt was decidable.

We could compute halt.

That means that there must have been some
Turing machine, I'm going to call it R,

some Turing machine that decides halt.

That is the definition of what it means to
compute something, what it means to decide

something, is we can have this Turing
machine that computes it for us.

So, let's call that Turing machine R,
whatever it is.

We're going to show that we can use R,
whatever that machine was.

I don't care what it is, except Except for
the fact that it decides halt.

So I'm going to use R to build this new
machine D, which decides ATM.

So here's our machine D that's going to
solve ATM for us.

So here's our machine D.

It accepts two things as input,
a machine description and an input string.

Let's call those M and W.

And it's going to need to
tell us yes or no, true, false,

one, zero, something like
that as the output for this.

So that's what this machine needs to do
for us.

Say yes or no for that machine input pair.

And we're assuming
that there exists this.

Turing machine R that
can decide halt for us.

So that is, R can answer
this question of does some

machine on that input
halt or does it run forever?

So it's either going to halt or it's going
to run forever.

So the first thing we're going
to do is we're just going to

go ahead and invoke this
function R, this Turing machine R.

On this input pair M and W that was given
to ATM, to this machine D.

So the first thing D is going to do is
it's going to invoke R on that input,

on its input.

So it's just going to invoke R on M and W.

And R is going to tell us whether or not
the machine halted.

So if R rejects, that meant that that
machine ran forever on that input.

So if R rejects, that meant
the machine ran forever

on that input, which
means it didn't accept.

So we're just going to go ahead and reject
in that circumstance.

Whenever this machine
R says no or says zero,

machine D is going
to return no as well.

However, when machine R says yes, now
all we knew is that it was going to halt.

We didn't know whether or not it accepted.

We only knew that it was going to halt.

But what we can do is since we knew that
it halts, we can just try it.

We can just try running M on W and see
what happens.

Since I knew that was
going to halt, that was

not going to run forever
because R told me so.

If it's yes, what we're going
to do is just say, all right,

now do M on W doing that
universal Turing machine thing.

So we have this idea of a universal Turing
machine saying, I can have Turing machines

that simulate other
Turing machines that do the

same thing that other
Turing machines would do.

So let's just do that universal Turing
machine thing on M with W.

And now we know that we're going to get an
answer, either yes or no.

So, if when we ran m
on w, the answer was no,

then turns out we
didn't accept that string.

If the answer was yes, turns out we did.

So, if we had some method for solving
halt, that told us it was safe to just try

that machine on that input, to just invoke
that implementation for that input,

so that we can then just see how it
answers.

Because the only reason it might have been
risky to do this m on w thing was,

if it ran forever, then we would never get
an answer for d.

So, in this case, since halt warned us
that was definitely going to halt,

then we could just try it and then see
what the answer actually was going to be.

Since we knew that any Turing machine that
decided halt, we didn't make any

assumptions about what r was besides that
it existed and solved halt for us,

any Turing machine
that decides halt, we can

use that to compute or
decide this function atm.

Since ATM was impossible, so was halt.

So, that's our reduction.