cs313 »

cs313 unit 7.2

01 l More Undecidability

Now the halting problem isn't the undecidable problem. There's actually a very large number of undecidable problems as we'll soon see. And the technique here is almost the same that we use for showing np-completeness. So if you remember that once we had shown SAT to be np-complete. We could take a whole bunch of other problems such as vertex cover, clique, and independent set and of course many more and show these to be np-complete using a reduction because we were able to show that if you could solve vertex cover in polynomial time then you could also solve SAT in polynomial time and we'll now use a very similar technique. Now we know the halting problem is undecidable, we can look at other problems and show through a kind of reduction that if we could solve these problems here then we would be able to solve the halting problem, which of course is not possible. Now, the first problem we might be looking at is a generalized version of the halting problem. As you remember, the halting problem takes as input a program and an input on which to run that program and what we could now ask is of course a more general question and that is, does the program have any input on which it stops or does it always go into an infinite loop? And we'll call that the generalized halting problem. So we're given P and now the question is, is there any input I for which P halts? And I'll show you now that this problem here is also undecidable and then we'll look at other problems and you can show that they are undecidable. So the proof always work in a very similar fashion. You again start out with an assumption. And then lead that assumption into a contradiction. The initial assumption is that we had an algorithm or a program that can decide the generalized halting problem. So assume there's a program P' that solves this problem here. Now, how could we use this program here to solve the halting problem? Well, that's actually quite easy. So we have the program and the input. And now we construct a new program from that. That problem is actually quite easy. We just make the input here part of the program code so in kind of a pseudocode writing here the first line of that program P'' would be set the input variables to I and that is now part of the program code of this program here. Here it was a separate input and now it's part of the program code. So we set the input variables to the input and then run P as always. And now it's clear that if we have a problem that solves the generalized halting problem then we can just feed it to this program here because this program here actually ignores any input that we give to it. Finding out if that program over here will ever terminate is the same as asking if the original program P will terminate on the input I. This program here cannot exist because if the generalized halting problem were decidable this would also mean that the special halting problem here where we are given an explicit input would also be decidable. So we know that this problem is now undecidable as well.

02 q Equivalence Problem

Now I will give you another type of problem and this time you can prove that this problem is undecidable, and the problem is as follows and that problem is also one that sounds very simple. It's the equivalence problem.  So this time, we're given two programs, P and P prime, and the question that we want to answer is do this two programs do exactly the same thing? For example, do they implement exactly the same algorithm only using a different type of implementation, and now, what I would like you to do is prove that equivalence is undecidable by showing that if you have an algorithm that would solve equivalence then you could also solve the halting problem.  Now, the way we're going to do this quiz is as follows: I have here six building blocks or potential building blocks of this group, and I would like you to do the following: There are four building blocks that you actually need for the proof and there are two building blocks, which are not necessary for the proof.  And what I want you to do is to find out which building blocks you need and which you don't need, and for the building blocks that you need bring them in the right order.  So, right one next to the building blocks that would come first in a proof of undecidability of equivalence then you write a 2 next to the next building block and so on. It might be easier to first think of how you would prove this and then fill out the boxes rather than playing around with them.  How you prove that equivalence is undecidable?

02 s Equivalence Problem

To show that equivalence is undecidable, we should first start out with a program for which we want to decide the halting problem, and that should be P. We start out with the step here, and then we add a second program and that program is called P‘ and it goes into an infinite loop. No matter what input, this program is just programmed to always go into an infinite loop. Once we have those two programs P and P‘, we run them through the algorithm that decides equivalence and what that will do is it will basically ask-- does the program P for which we want to decide the halting problem do the same thing as the program that always goes into an infinite loop. And then, of course, that means if the two programs are indeed equivalent, then P will also go into an infinite loop because all that P‘ is doing is it always goes into an infinite loop and we don't even need the other two building blocks because we have now shown that you can use equivalence to solve the halting problem. You just compare any program for which you want to decide the halting problem to a program that always goes into an infinite loop and if they do the same thing, then they are equivalent. So you know that P will not halt, and if they are equivalent, well then P halts. Now, this was certainly one of the tougher quizzes in this course so congratulations for figuring it out, but of course I also trust that by now you have learned the ropes of theoretical computer science. You revert here is that I will give you a third proof of undecidability for free.

03 l Specification

And the third problem which is undecidable is a problem called specification, and that problem basically asks--does a program do what it is suppose to do. And that problem in the general case is also undecidable because determining the equivalence of two programs is basically the same as using one of the programs as a specification for what the other one does. Unfortunately even determining if a program is correct cannot be done automatically, at least not in a general case and we'll get to the special cases at the end of this unit of course.

04 l Rices Theorem

Now the proofs for showing undecidability are somewhat easier than showing NP completeness, because basically, what we are doing is the following. We start out with saying that for any computer program, we can decide a certain property and then derive from that but then you could solve the halting problem. And you have seen that this works with a lot of properties. So deciding if the program will stop doesn't work, deciding if the program is equivalent to another program doesn't work, deciding if the program even does what it's supposed to do doesn't work. Even though you might still feel somewhat cheated by the original halting problem proof, you might be inclined to think that once you accept that then there's actually not much you can decide about the properties of a program at least in general, and it turns out that that is exactly true. In 1953, Henry Rice after whom Rice's Theorem is named proofed that basically you cannot use an algorithm to decide anything about the properties of a given program. So we must be a little bit more formal about this property x thing here. And Henry Rice used the notion of a functional property here. Now, what is a functional property? Sounds very complicated. Actually, it's a very simple definition. Any functional property has these two properties. First, it describes how the output relates to the input. So this is what we mean by behavior and that is important to how they relate to each other not for example how much time we need or something like that. And the second property is that there must be some programs that have this property, and other programs that don't have this property. So that when you look at all possible computer programs, some of them will have this property others won't so that it can basically distinguish between the two.

05 q Functional Properties

So to practice the definition of functional properties, here's our next quiz. I have here five potential functional properties and actually, I would like you to tell me which of these are functional properties and which of these are not. The possibilities are a program is a computer program, a program always returns 1, a program solves vertex cover, a program is a computer virus, and a program requires O(n) time. So which of these are functional properties.

05 s Functional Properties

The first one of course is not a functional property because condition two is not fulfilled. All computer programs are computer programs. There is no computer program that is not a computer program. Of course, this sounds a bit silly but it's actually the only example I could think of where this condition here is violated. A program always returns one already is a functional property. First of all, it describes how output relates to the input namely output doesn't care about the input and is always one and property two is also always satisfied. For example, there are computer programs that I could write that always return two and property two is fulfilled for all the other three as well, so I won't even mention it anymore. A program solves vertex cover? Yes, definitely that describes an input-output behavior, how output relates to the input. Is a computer a virus? I would say yes, this is a functional property. Now, it is a bit debatable if saying it is a computer virus already described sufficiently how the output relates to the input but I would say that probably any definition of a computer virus that you would give me would in some way describe what the computer virus is doing. So, it might ignore anything that receives and overwrite your hard disc, so put something in the memory, or it might lock your screen. So, I would say here, the input-output behavior is variable depending on how you define computer virus but it is always defined. Now, the final one that is a bit of a tricky one saying that a program only requires linear time is not a functional property because that does not describe how the output relates to the input. It is the property of the program but it is not a functional property because it doesn't ask what does the program do and what does the program do is actually this relationship here. It only asked how fast that the program are doing that. This is something that is a little more tricky to figure out, but basically, any time that you ask can a program do X that will be a functional property that you are asking for at least in almost any of the cases.

06 l Statement of Rices Theorem

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.

07 q Decidable Properties

So now to computer with Rice's Theorem before we go back into practice, I'll give you a quiz very similar to the one we just had. All I want you to do is to figure out which of the following properties are decidable for a given program? A program always returns 1, a program solves Vertex Cover, a program adds 2 numbers, doesn't do anything, converts and MP3 file, reads a file, terminates after 3 timesteps, is a virus, writes to a file, modifies itself, returns an integer, downloads data. So please make a check mark next to those properties that are decidable, and leave the others blank.

07 s Decidable Properties

And there's actually only a single decidable property here. All of the other properties are undecidable. Now let's go quickly through them, one by one, to discuss why that is. So always returns 1; you know that is undecidable by Rice's Theorem. It's a similar case here; we already have that. Adding 2 numbers, Rice's Theorem. Doesn't do anything, Rice's Theorem. No matter how you define doesn't do anything; it will always come back to Rice's Theorem. Converts an MP3 file, Rice's Theorem. Reads a file; that is an interesting one, because you could argue that this does not fall under Rice's Theorem, but even if you have that argument, it's still not decidable, because what I could do, for example so I can modify any program so it will only read a file once it's done and that again will allow me to solve the halting problem. Is the program a virus; Rice's Theorem. Writes to a file. similar logic as reads to a file. Modifies itself; that is an interesting one, because of course here you could say Well, of course I could just go through the code and whenever the program accesses itself, I know it has that property, but the thing is this: the program could have certain lines that suggest this program modifies itself, but deciding whether those lines will actually be reached once the program executes, that again would allow you to solve the halting problem, so also this isn't decidable. The same one here; of course you can look at a certain program and say, Doesn't the program return integers? but you had a program that can decide if a program only returns integers, that again would allow you to solve the halting problem, And the same thing for downloading data. If I had a program that designs generally for any other program if it downloads data, I could use the same technique as for reading a file. I could basically modify any program so that it could run completely on its own data that it already has included and downloads data basically to signify that it's done. If I could decide this in the general case, then I would have also solved the halting problem. Now the question of course is, If this here has any practical relevance; for example, reading a file, because for most programs, of course, you will be able to decide if they ever read a file or not. Then again, on the other hand, if you look at general software testing, this is an interesting question from a perspective of code coverage, for example. If you could decide if a program reads a file, and of course you want the program to read a file, then that would tell you something about the correctness of that program.

08 l Cant We Decide Anything

Is this a super depressing ending to this course, and can't we decide anything? Well, of course, Rice's Theorem and undecidability in general is prone to a certain criticism. I mean a crucial thing to notice is that Rice Theorem means that there is no algorithm that can decide a functional property for any program that we through at it, but this is a very general case. Rice's theorem an also the halting problem, of course, can only concern this very general case. If you're trying to prove something about a program you know very well, you might be in a very different situation, so if you're trying to find out, for example if a program you wrote even halts, and you can't prove that or can't even show that, then maybe you should consider writing some better understandable code. But what it does mean is that there's no fully automated software testing without trade off. So it means that fully automated testing basically the dream of a program and you throw any other program at it, and it will tell you if it's correct, if it stops, if it crashes, and that's the dream that we probably can't fulfill, but if accept certain trade offs, so for example, if we accept that the automated testing program will be right most of the time or that it only works on special cases, then we might be in a better situation, so I would interpret Rice's theorem not as a general negative message, but rather as a piece of caution as to what computers can do and can not do.

09 q Malware Detection

So I would to consider with you one example of what Rice's Theorem might mean in practice and might not mean in practice, and the example I find very illustrative for this is malware detection, so determining if a program does something bad on your computer or if it is a harmless program that you want to run. So first of all, we have to think of it about what actually classifies a piece of software as malware? So a good classification of malware be that it's a piece of software that does something the user doesn't want it to do? Would it be a good classification if it deletes files? If it gathers information from your computer? If it disrupts or interrupts other programs? If it installs itself or something else without asking you as a user? Or some combination of the above.

09 s Malware Detection

I think the only correct answer here can be the last one; it's some combination of the above criteria, because there's always counter examples if you just take a single one of them. So for example, if software does something that the user doesn't want, if the software enforces copyright protection, some people might call that malware, actually, but there are of course cases where software does something that the user doesn't want and it's still for a good purpose. Software that deletes files, no way, because you can delete files on your computer using the normal delete command, and that is not malware. Gathering information from your computer, not as a stand-alone criterion, because there might be software that you actually want to gather information from your computer. Disrupting other programs; well, sounds like malware, but on the other hand, if for example you have an anti-malware program that disrupts malware, that will definitely disrupt, or hopefully disrupt the computer virus that is trying to infect your system. It doesn't have to be malware just because it interrupts other programsl. Installs without asking; well, with most software having automated updates, I don't think that classifies as malware alone.

10 q Automated Malware Detection

So you see, even finding formal criteria to tell you if software is doing something malicious that you don't want it to do, that's very difficult, but let's assume you had found those formal criteria. Now my question for you would be What would be the problem with automated classification of a program as malware from a theoretical computer science perspective? So even if you had formal criteria that defined exactly what malware is, so are the issues here that automated malware detection is an NP complete problem? Is it automated malware detection undecidable? Or is it that automated malware detection can never be perfect? That means you will always have programs that are not malware that will be classified as being bad or other programs that are malware but will basically slip through the net or slip by this program here.

10 s Automated Malware Detection

And I think 2 of these answers here are true. First of all, if you had perfect formal criteria for malware, the whole thing would fall under Rice's Theorem. Malware would be a functional property and we know that functional properties are not decidable, which in turn means that since the problem is undecidable that malware detection can never be perfect. It's not really clear what kind of error you will be making, so if you will be classifying good software as bad or bad software as good, but it can not be perfect, because if it were perfect, then that would violate Rice's Theorem. Now NP completeness of course; that is not true for several reasons, so first of all, running time is something something that we just can see here, and secondly, as you've learned, there are problems that are much worse than problems that lie in NP so it can also be that malware detection is actually worse than NP complete. We just don't know, so this is not a correct answer here.

11 l Godels Incompleteness Theorem

You may or may not have heard of Godel's Incomplete Theorem, but since they are also mentioned in conjunction with the Halting Problem and undecidability, it worth saying a few words about them. Godel's Incompleteness Theorem is named Austrian-born mathematician, Kurt Godel, are concerned with mathematics, but are actually closely related to undecidability and as you might know, any mathematical system starts out with a set of axioms. What are axioms? Axioms are statements which you assume to be true without having any formal proof of them, such as if A equals B and B equals C, then A must also equal C or you can always draw a line from one point to another point, no matter where they are. Those would be axioms. Now axioms often sound very trivial, like this one here or the fact that you can always draw a line between 2 points but for many of them there are actually scenarios where they are not true. So axioms are the basis of any mathematical theorem or proof. Now what Kurt Godel showed, and it was a shocker at his time and to many it is still today, is the following: So what Kurt Godel showed was that if you had a set of axioms and they don't contradict each other and they are listable, which means you could have an algorithm that lists you all of these axioms, so either they are finite or they can even be infinite as long as you have an algorithm that can produce them all; if this is the case, then there are some statements that are true but which you cannot prove based on these axioms and this is what he meant by incompleteness how he basically showed that no matter what foundation you base a mathematical system on, as long as that is a consistent foundation, then you can not prove everything without adding additional axioms at least. He also showed, and this is the second Incompleteness Theorem, which is basically an extension of the first one that a system of axioms cannot not demonstrate its own consistency and what that means is that very informally, a mathematical system can not be used to show that it itself is consistent. These 2 statements are in a way very similar to the Halting Problem and Undecidability. The axioms; you can think of those as programming statements. So any program or algorithm is composed of a number of simple instructions that are then arranged, and of course there is an infinite number of possible computer programs that you can write, but they are made up of a fine set of building blocks and the second Incompleteness Theorem is of course very similar to undecidability in the sense that it shows that you cannot use a system to prove everything about that system, very loosely speaking, and the undecidability of the Halting Problem and all of the other undecidable problems, of course says that we cannot use algorithms to calculate everything about algorithms. I know that from a practical perspective there's lots of criticism of this, but truth be told, I just find that super fascinating.

12 q Undecidability vs Semi decidability

It's a bit ironic that although theoretical computer science is very precise, there are sometimes very confusing naming conventions, and since many students, at least those I have had have been confused by this, I just quickly wanted to clear one thing up. You will sometimes read that the Halting Problem is semi-decidable and we have to say that it's un-decidable, so which one of these 2 is it? Is it undecidable or is it half-way decidable? And paradoxically, it's both, and let me explain why. So assume that we have a program, P, and we want to determine if it halts, so we want to know, does the program stop at a certain point in time, and the answer to that, as you know, can either be yes or no. Now let's think about the 2 cases that are possible. So the first one of those 2 cases is that P stops, and my question for you is, if P does stop, can we a yes after a finite amount of time?

12 s Undecidability vs Semi decidability

And there answer here of course is yes, so as long as the program stops and after a certain finite amount of time, we will get the answer yes, simply due to the fact that the program has terminated, so you know for sure that this a program that halts.

13 q Finite Amount of time

Now what about the other case? What if the program does not stop? Can we get this answer here after a finite amount of time?

13 s Finite Amount of time

And the answer here, of course, is no, because it doesn't stop, it will run on and on and on We will never get this answer here. We will just have to wait and wait and wait.

14 l Recursively Enumerable

So the answer no is something we cannot obtain in finite time and that is why the Halting Problem is called semi-decidable, because we can kind of decide half of the answers and it's also called undecidable because we cannot output a clear yes or no after a finite amount of time. Why this nit-picking; what's the difference, you might ask. The interest of this, of course, is rather theoretic, but semi-decidable problems have a very interesting property called recursive enumerability. Now that sounds a bit strange; what does that mean? Recursive enumerability means that you can write a program that outputs all combinations of inputs and programs, and I seriously mean all combinations of inputs and programs that halt. So this program here cannot say for any input and program that this combination will not halt but it can output a complete list of inputs and programs that will halt, so let's have a look at this program, and of course, this program runs on infinitely, so it start off by defining a length called max length to be 0 and then it goes into an infinite loop, which is this one here, and what it does then is it increases max length by one each time it goes into this loop here, enumerates all programs of length at most max length. Now if you fix this max length here, there is a huge number of programs that have a length at most max length but it's finite; it's huge but finite, and the same goes for the inputs. So for all combinations of programs and inputs that are shorter than this value max length here, we run a simulation for exactly max length steps and if the program halts on the input after exactly max length steps, then we print the program, and we print the input. If it hasn't halted yet, don't care, throw it away, wait until the next loop.

15 q Algorithm

So please take a while and familiarize yourself with this algorithm and then tell me some of its properties. Does this algorithm eventually find any combination of program and input that halts, or are the some that this algorithm might be missing? Is this algorithm feasible or infeasible in practice? And finally, could we modify this algorithm here so that it doesn't only find program and input combinations that do halt, but also those that don't halt.

15 s Algorithm

And the answer here, surprisingly, at least I think it's very surprising this algorithm is capable of finding any combination of program and input that halts, and the reason is simple; if a program halts, then the program has a finite length, the input has a finite length, and the number of steps in which the program can run on the input, if it halts, is finite, and at a certain point in time, since this loop here is infinite, max length will be larger than any of those 3 constraints, and once max length has become large enough, we will find that P terminates on the input after a certain number of steps, and so we will print it. The only reason why the algorithm could not find the certain combination of program and input is that the program does not halt on that input. The first one, amazingly, means that the algorithm is indeed correct. Of course it is totally infeasible in practice, as well, because if you think about it, a program is a text string; now even for very, very, very small values of max length the number of these text strings for the program and of course also the number of text strings for this input here becomes exponentially huge, so it's a purely theoretical construct, but it explains at least in some theoretical computer science courses, you will hear that the Halting Problem is referred to as recursively enumerable. So the algorithm is totally impractical, but it is nevertheless correct, and that is the reason why the combination of programs and inputs for which the program halts on the input is called recursively enumerable, at least in some theoretical computer science courses. Now this one is interesting; can this algorithm be modified to output any programs that don't halt? And the answer here of course is no, because this technique here clearly only works when the program stops. As long as the program goes on, we can not make any statement about it. We cannot say it's a program, will it still continues running, if it will stop at a certain point in time, and that is the reason why we can't modify this algorithm, so that it finds combinations of programs that input that don't halt. This of course also tells you again why the problem is semi decidable because we can find those combinations here, but we can not find those over here.

16 l Congatulations

So are there any worse problems than undecidable ones? Well, that kind of depends on your subjective view, but from a perspective of computer science undecidability is the biggest and meanest monster of complexity; for a computer, there's no worse thing than "I can't do it." Which is undecidability, so the answer here is no, but that also means that you have completed your journey, which means that all that remains to be said is Congratulations for completing our Introduction to Theoretical Computer Science! I consider this to be a rather challenging course, so you should really be proud of yourself for having learning so many advanced concepts. You have learned about NP complete problems, some of the toughest problems that are out there, and you have also learned how to recognize these problems, so detecting NP completeness. You have also learned how to navigate around NP completeness using techniques such as search trees, pre-processing, fixed parameter tractability, approximation algorithms, and other techniques such as randomized algorithms, and finally, and this is all but trivial, you now even understand the cliffs of undecidability. I hope I've conveyed to you for many problems that are very, very challenging to solve, digging deeper into underlying algorithms and techniques can really be rewarding, because not only is it fascinating, but actually, problems that to many people will seem unsolvable can be solved using the tools that you've now learned. Theoretical Computer Science or the science of challenging problems is a very rich and deep field and you're no ready to dig deeper. Whether you want to dig deeper into the theory or you want to dig deeper into writing your own algorithms to solve nearly impossible problems, that is up to you, but in any case, I wish you all the best for that journey, and once more, congratulations for completing this course.