---
Video Title: Rice's Theorem
Description: Theory of Computation
https://uvatoc.github.io/week10

20.1 Rice's Theorem
- The NoEvens Language
- A template for Proving Noncomputability
- Semantic Properties
- Rice's Theorem

Nathan Brunelle and David Evans
University of Virginia
---

Let's look at one more.

So our goal here is we're going to show
that this no even language is undecidable,

where no even was all descriptions of Turing
machines that only accept odd numbers.

That is, they don't accept any even
numbers.

This one's going to
look slightly different,

but only slightly to the
two we've seen so far.

We want to build this new machine m' such
that if that machine m' were to

hypothetically receive some input x,
then whenever that x was even,

that implies that x was not in the
language of that machine m'.

And we only want that to be the case if m
halted on w.

So whenever m halted on w, x does not
belong to the language, otherwise it does.

Something to keep in mind is that for our
other two examples, so for the universal

example and for the a10 example, if m
ran forever on w, we accepted nothing.

We could never accept, we could never hit
our return statement if m ran forever on w.

So in this case, what happened was any
machine, any Turing machine that accepted

the empty language, that
accepted no inputs, did not have

the property of either of
these original two examples.

So in this example, we're asking,
does our machine have the property,

does the machine's language have the
property of accepting a10?

This one said, does the
language of this machine

have the property that it
does the universal thing?

The empty language does not have the property
of accepting a10, or of including a10.

The empty language does not have the
property of being the universal thing.

The empty language does have the property
of not having even numbers in it.

But we're still going to be able to use
very much the same idea here.

So what we're going to do is, I'm going to
consider this mTrue that we had before to

be a Turing machine that does accept some
even input.

That is, mTrue, in this case, does not
belong to no even.

But I'm still going to set
things up in such a way

that m' matches mTrue
exactly when m halts on w.

But at the end, I'm going to return the
opposite of what I had before.

So we're going to say mTrue is a Turing
machine that does not belong to no even.

And what we're going to do is,
with m' when we receive our input x,

the first thing we're going to do is run m
on w.

If m on w halts, then we can do mTrue and
then return the opposite of that.

So the reason I'm doing
this is, here, the only

difference is which
machine we picked for mTrue.

So in this case, what I'm actually doing
is showing not no even.

So in order to show that
no even is not decidable, I'm

going to first show that
not no even is undecidable.

Which should tell me that no even was
undecidable as well.

Because if not no even was decidable,
then I could just invoke not no even and

then return the opposite in order to
decide no even.

If one language is decidable, its opposite
language is decidable as well.

Basically, what we're doing is,
I'm giving you a template.

So my goal was to give
you a template for how

you can prove large
categories of problems.

So this structure that I
gave you was exactly the

same structure for all
three of those situations.

The only thing that changed was which
mTrue we chose.

So this structure is going to
work as long as we can find an

mTrue that will allow us to
fill in the definition of m'prime.

All of these things that we just asked
about, we're asking this type of question.

Where we said, does the machine compute a
language with a certain property?

For instance, did that
machine only have finitely

many inputs, like we
talked about last time?

Did this machine accept a 1, 0?

And so forth.

So each of these are questions about some
property of the language of that machine.

On the other hand, we could also ask
questions like, does the program print 3?

Or does it run for 15 steps?

Or does it accept within 15 steps?

Something like that.

So these are questions that are more of,
like, questions about the implementation

of the machine than what function it
computes.

So these types of questions that we see
here, where I'm asking you a question

about the function of the
machine or the language

of that machine, we call
these semantic properties.

So semantic properties
are these properties that are

maintained for functionally
equivalent Turing machines.

So we say two machines, two Turing
machines, M and M prime, are functionally

equivalent if they always give the same
answer for the same input.

They compute the same function,
they're functionally equivalent.

Regardless of how they're implemented,
one could be slower, one could print

things along the way, But
as long as they accept and

reject the same things,
they're functionally equivalent.

We say a function is a
semantic function if it does the

same thing for two inputs
that are functionally equivalent.

So that is, we're only asking about what
the input-output behavior is for those

functions, not what they did along the
way.

So in this case, these examples are not
semantic, because two programs that

compute the same function may or may not
print three.

We could have one that prints three and
the other one that doesn't.

For two Turing machines that
compute the same function,

some of them might run
for 15 steps on input X.

Some of them might not.

That does not change whether or not
they're going to be the same function.

But for these, if I have two machines that
computed the same function, then I knew

that they were going to
have the same answer

when I asked these
semantic properties of them.

So if two functions... if two
machines compute the same

function, and I ask this
question of, does it accept 10?

Then the answer is going to be the same
for both machines.

So this is something we call a semantic
property.

Any property that is
the same for functionally

equivalent machines
is a semantic property.

Anything that could be
different for two machines

computing the same function
is not a semantic property.

The statement of Rice's theorem is to say
every semantic property, literally every

semantic property of Turing machines is
not computable except for two.

Exactly two.

The way it's phrased
is either that semantic

property is not computable
or else it's trivial.

Where the two examples, the two
counterexamples are the trivial ones.

Which are the ones that apply to no Turing
machines or apply to all Turing machines.

What Rice's theorem says is, if I ask you
a question about the language of a Turing

machine, or about the function that a
Turing machine computes, either the answer

is always yes, no matter what the Turing
machine was that you gave me, or it was

always no, no matter what
the Turing machine was that

you gave me, or you couldn't
tell in the general case.

That was an undecidable question.

Those are the only three situations.

Either the answer is
always yes, the answer is

always no, or else you
couldn't tell me the answer.

What we're going to do
is, here I've got this general

pattern for these types
of semantic properties.

So if P is a semantic property,
then let's consider this language where

I'm going to say, it is the set of all
Turing machine descriptions, where that

described a machine whose language
satisfied property P, whatever that was.

So PTM is all descriptions of Turing
machines whose languages satisfy P. So our

goal is, we're going to say,
if I had a decider for PTM, as

long as PTM wasn't one of
those two trivial counterexamples.

So if we have a decider for PTM,
then we can use that decider to decide

halt, no matter what the property is
asking.

So our goal is, we're going to say,
given an MW, or we're asking halt about

that MW, we're going to define a new
machine M' such that if M' were to receive

input X, it's going to accept or reject
those X's, those inputs, such that its

language would eventually have the
property P, if and only if M on W halted.

So if I had any property that I might ask,
any semantic property of my Turing

machines, I can define M' in the following
way.

When M' receives input X, the first thing
we're going to do is we're going to say,

M true is some Turing machine
whose language does have property P.

There must exist at least one Turing
machine with property P for this to work.

If I can't find such a
Turing machine, then this

reduction just does not
apply in this situation.

So that's why we have this
one special case of, if the

property holds for no Turing
machines, we can decide it.

Because this reduction won't apply,
because I can never find such an M true.

So what we're going to do is we're just
going to say, M true is some arbitrary.

Turing machine, any Turing machine,
whose language does have property P.

Then what we're going to do is we're going
to run M on W, set Y to be equal to the

result of running M true on the input X,
and then give the same result as M true.

So basically what we're showing here is
that if M on W halts, the language of M'

equals the language of M true,
and therefore M prime has property P.

Because M true had property P,
this was a semantic property, the answer

is the same for any two machines with the
same language.

However, if M on W ran
forever, then that means the

language of M prime is
equal to the empty language.

It didn't accept anything.

What this whole structure shows us is if
property P is not trivial, and the empty

language doesn't have
property P, then M prime

has property P if and
only if M on W halted.

So in this case, if M on
W halts, the language

of M prime equals
the language of M true.

Since M true had property P, M prime must
also have property P, whatever it is.

If M runs forever on W, that means M prime
doesn't accept anything.

So if we were to assume, let's just go
ahead and assume that the empty language

doesn't have property P,
then that just means that.

M prime has property P if
and only if M halted on W.

So assume that the empty language doesn't
satisfy this property.

In that case, since the language of M
prime matches that of M true if M halted

on W, and the language of M prime was the
empty language if M ran forever on W,

that means M prime has property P if and
only if it ran forever.

However, in the case that the empty
language does have property P,

then we can just repeat
the whole procedure

but use the opposite
of property P instead.

We can just do not property P instead.

So when we were looking at
no even, the empty language

does have the property of not
accepting any even numbers.

So therefore, this structure doesn't just
work immediately for no even.

However, it would work for yes even.

This structure does work
for yes even because the

empty language does not
have any even values in it.

So the opposite of no even being yes even.

For yes even, the empty language does not
have this property of yes even.

Ugh, double negatives.

Because the empty set has...

So because the empty set has the property
no even, we're instead going to do yes

even and then just come up with the
opposite answer.

So now, no matter what property P is,
as long as I can find at least one Turing

machine M true that's going to have that
property, then this makes for a reduction

to show that determining
whether or not a machine's

language has that
property is undecidable.

So what we can do then is for a lot of
these things that we've seen so far,

if I ask you a question about a Turing
machine, what you can do in order to use.

Rice's theorem to simplify your life is
say, if that question I asked was a

semantic question, then
first check if it was one of

these two counterexamples
where these are decidable.

And if so, then it's decidable.

That question's a decidable question and
the answer's either always yes or always no.

So for instance, if I ask the question of
does this Turing machine accept-rejector

run forever on every
input, that is a property that

will be true of literally
every Turing machine.

So if we had one of these trivial
questions that was either true for every.

Turing machine or
false, it's like if I said does

this Turing machine
Turing machines smell bad.

No Turing machines smell bad because they
don't really exist.

They're just mathematical ideas.

So none of them have scent.

So no Turing machines smell bad.

That is a trivial property about Turing
machines.

It doesn't apply to any of them.

So basically, they either have to be dumb
questions like that, where you just should

have known the answer already,
or else it wasn't going to be a decidable

thing to answer, provided that question
was a semantic question.

If it was not a semantic question,
then we can't use Rice's theorem.

So for instance, does it print 3?

That is not a semantic question,
so Rice's theorem simply doesn't apply.

Does it run for 15 steps on X?

Rice's theorem simply does not apply
because that's not a semantic question.

So if somebody is asking a question about
a Turing machine, and you want to figure

out whether or not that was a computable
thing.

So let's say I ask a question about Turing
machines.

I want you to answer some question about
Turing machines.

The first thing I'm going to ask is,
is this a semantic property?

Will the answer be the same for any two
Turing machines with the same language?

If yes, then we're going to ask,
is it trivial?

That is, does it apply to some Turing
machines, but not others?

If the answer is yes to that, then it is
not trivial, so it's undecidable.

If the answer is that it always has the
same answer for every single Turing

machine, then it's trivial, it is
decidable.

If it's not...

So if the answer is no, it's not a semantic
property, then you have to do a reduction.

So Rice's theorem just says that we have
this shortcut for semantic properties.

You