
Title:
2108 Statement Of Rice's Theorem

Description:

Now, what is Rice's theorem?

Rice's theorem is actually quite simple.

Rice's theorem simply says that if you asked for an algorithm

to decide the program has a functional property and it can be any functional property,

then, you're looking at an undecidable problem.

I don't even know, that come out of surprise to you

after we have shown that basically anything is undecidable.

It's almost a surprise now that any problem on a computer

should even be solvable but we'll get into that in a minute.

The main question, of course, how can you show Rice's theorem,

and the proof that is actually easy and it follows the same scheme as above here.

So the proof of this general statement

follows the same scheme that all of our other proofs of undecidability have basically used.

So, again, we assumed that there is a program that can decide

for another program if that possesses a certain functional property.

So we're given a program P again, any program P,

and we assumed that no matter what P is,

we can always say "does P have a functional property?"

Now, on the other side, assume that there is another program P',

and what we want to do is solve the halting problem for this program here

and then we'll use the algorithm here that can decide for any program P

if it has a functional property to solve the halting problem

and the way we do this is as follows:

We construct a new program we will call program X and this program has only 3 steps.

First, it runs P' then it clears all of the memory,

so basically a fresh start of a machine,

and this is the only reason why we need this condition too here for a functional property

because if we have an algorithm that can decide a functional property,

this means that there are some programs that has this property and others that don't.

So, we will now add to our program X a program that has this functional property.

So, run program with functional property,

and what then do is we take this program X and fitted into this algorithm here.

what you can see now is the following:

If P' here, the problem for which we want to solve the halting problem,

runs smoothly and terminates,

then this program X will have the functional property that we can decide

because it runs this algorithm here and it clears the memory

and then it runs the program with that functional property.

This is also the reason why time is not a functional property.

That would kind of destroy the proof of Rice's theorem.

But if time is not an issue, then as long as P' finishes,

the program X will have the functional property that we can decide here.

If, on the other hand, P' goes into an infinite loop,

then the program does not have the functional property

because it will never be able to reach these two lines here.

So, deciding the functional property for this new program X here

is the same as solving the halting problem for the original program that we started out.