---
Video Title: Prints3 and IsMalware are Undecidable
Description: Theory of Computation
https://uvatoc.github.io/week10

19.6 Prints3 and IsMalware are Undecidable

Nathan Brunelle and David Evans
University of Virginia
---

So let's say that I wanted to know whether
or not some Python program printed 3.

I have this Python program, and I'm just
going to ask this question in general.

Will this Python program print 3 when
running on that input?

This is another one of these cases where
it might now be pretty apparent that

there's lots of easy ways to solve this
for some subset of programs.

If I had a Python program where nowhere in
there did I have a print statement that

included a 3 inside it,
then certainly the answer is

going to be no, that Python
program does not print 3.

But you might write other convoluted
programs where there are print statements

in there that have a 3 inside,
and now it could be difficult to answer.

So we're going to show
that answering this in

the absolutely most
general case is not possible.

So we're going to show that it is
undecidable, it is not computable to

determine whether or not a given Python
program prints 3.

So the idea here is I want to use prints 3
to solve HALT.

That's my strategy.

I'm going to use prints 3 to solve HALT.

I'm going to reduce HALT to prints 3.

That is, use some solution for prints 3 in
order to build a solution for HALT.

And the way that I'm going to do this is
I'm going to construct a Python function,

M' such that M' prints 3 if and only if M
on W, which was given to HALT, halts.

So for a given M and W, I'm going to use
those to produce some M' where that M' is

going to have the property
that it's only going to

print 3 in the case that M
HALT when running on W.

So basically what we're going to do is
we're going to define M' on some input X

that we're never going to give it,
but it could take it if we wanted it to,

because we're never going to actually run
this function M' and what we're going to

do is we're first going to say Y is equal
to M on W, and we're going to just go

ahead and assume that our universal Turing
machine doesn't print 3.

That seems like a reasonable assumption,
that universal Turing machines shouldn't

need to print things, they just give
output.

They don't need to have side effects if we
don't want them to.

So we're just going to assume our
universal Turing machine doesn't print 3.

This first line, y equals m on w,
that's not going to print 3.

But as soon as we get past that line,
we're just going to print 3.

So now in this case, we can say if m on w
halts, we definitely print 3.

If, however, m on w runs forever,
we never print 3.

Because this line, y
equals m on w, stopped

us from ever getting
to that print statement.

So if we could answer this question,
does this function print 3?

Then we could answer the question of
whether or not this line finished,

so did m on w halt or run forever?

Question.

So this function, m prime, halts if and
only if m on w is going to halt.

So we do have this extra
assumption that the method

we use to simulate m on
w is never going to print 3.

So we have this assumption already.

Let's just assume that's not going to
happen.

So assuming that this
is going to be the case,

the only way we could
print 3 is if m on w halted.

If m on w ran forever, we definitely
didn't print 3.

Let's do one more really quick function.

It is undecidable to
determine whether or not

a given Python program,
let's say, is malware.

We're just going to define malware as it
does a bad thing.

It reads some sort of forbidden memory
location or something like that.

So you're going to see, hopefully, a
very similar pattern to what we saw before.

We're going to use malware to decide halt.

That is, reduce halt to malware,
to this malware problem.

And in order to do that, we're going to
build an m prime such that m prime is

malware if and only if m on w, which
was the input for halt, does actually halt.

So essentially, what we're
going to do here is we're going

to define our m prime very
similarly to what we did before.

So we're going to say, first, let's run m
on w.

And then afterwards, we're going to do a
bad thing.

Do a malware thing.

Something that malware does.

Read forbidden memory
locations or forward I love you to

everybody in your email
contact list or something like that.

So now we're going to assume that this
doesn't do bad things.

So maybe we do that
universal Turing machine thing

in a safe environment
so that it can't be malware.

And then afterwards, we're doing the bad
thing.

So if I could tell you whether
or not we did the bad thing,

then we've answered this
question of did m halt on w.

So therefore, malware is also going to be
undecidable.

What kind of ducating them?