# cs313 unit 7.1

no matter how powerful will ever be able to solve them.

## 02 l Limits of Computation

You've already learned quite a lot in the last 6 units: How to recognize challenging problems, the theory of NP-completeness, and how you can, nevertheless, solve these challenging problems using exact techniques such as search trees, pre-processing, or fixed parameter tractability, or approximate method. So approximation algorithms, or randomization. So far, all of the problems that we have looked at have had 1 thing in common: If you gave the computer enough time, and it has enough memory, then eventually you'll get an answer. So, of course, if you have an intractable problem, say an NP-complete one or an NP-hard one, then, of course, you will have to wait a long, long time to get your answer. The computer is, at least in principle, able to give you an answer. In this unit, we will be looking at the ultimate limits of computation. What that means is, I will show you some problems that are not hard to solve, but are impossible to solve. So the computer has no idea how to do this. And there's 2 surprising things waiting for you. First of all, these problems here are very simple, surprisingly simple. And the second thing is, although these problems are totally impossible to solve, actually, your computer is probably solving them every day. So some baffling things await you in this final unit of our course.

## 03 l Beauty of a Painting

Of course, there are certain problems that a computer can't solve. It can't appreciate the beauty of a painting for example. A computer cannot predict the outcome of a soccer match at least not accurately and of course, a computer also cannot see into the future and tell you the lottery numbers of next Saturday. So, at this point, we have to start off a little bit more formal and specify exactly what kind of problems we are talking about and what we mean when we say we want a computer to solve a problem for us And we will do this through three requirements. These requirements might seem very obvious to you but later on this unit you will see that these requirements actually has some very, very important consequences So, the laws of computer problems. Rule number one for a computer problem, the input must be given to us as a finite string using a constant number of symbols at each position in the string. The input for a computer problem could for example be a number of zeros and ones It's not infinite so it has a defined end and by constant number of symbols, I mean, constant number of symbols at each place So, in this case, at each place in the string, we either have a zero or one. Here, we could have a zero or one. Here we could have a zero or one and so on. You could also have a string like this. Again, its finite in length. And this time, we're using the real alphabet. So, it doesn't really matter what kind of symbols you use as long as the number is constant and that is basically the same requirement that we already have when we discussed the RAM. Because for the RAM, we also said that at each memory cell, we could only have a finite number of symbols so no variable can be arbitrarily large and the same thing as here, we cannot use an arbitrarily large alphabet at each point of the string, Rule number two is exactly the same as rule number one with one exception instead of input, we write output. So, we also want the output to be given as a finite string using a constant number of symbols. Actually, we could ever restrict ourselves to decision problems here, but we're going to keep it general. So, you get the computer a string and you expect it to out put a string and then finally rule number three. Is that going to be as surprising as rule number one and rule number two? Yes, it is. Because rule number three is going to be that if we get an output then we want that output to be a correct answer to our problem and that is one important point and answer where we can objectively say that it is correct The moment that is given to us and it is suppose to be definitive So, we do not want the computer to say Oh let me work on this for a little bit longer. When it produces the output that is suppose to be the answer.

## 04 q Computer Problems first,

its easy to miss some of the details here, which is of course why we're now going to have our first quiz. I'm going to give you a number of problems and I want you to tell me if this is a computer problem according to these three rules here or if we would not consider this as a computer problem. And you have to be very careful here. So, some of them are a little bit tricky, but then again you're already in the final unit. So, you've learned how to deal with tricky questions by now, I hope. So, here are eight problems for which I would like you to determine if they are computer problems according to these rules here. And again, some of them are bit tricky so you have to be really, really careful in checking it. The first three problems, given an essay written by his student. First problems, does that essay have at least 10,000 characters Second question, which grade does this essay deserve And third question, does the essay contain any misspelled words. A second set of potential computer problem would be the following here. Given two integers larger than zero, what is the sum of these two numbers? Second potential problem, does the smaller integer divide the larger one So is it a factor of the larger one so to say. Third question, given those two integers, please output a random integer between these two. So, between the smaller one and the larger one. And finally, I have two more problems for you to check. One problem is given the string of zeros and ones, check if that string is randomly generated and finally, calculate the square root of 5. So, please for each of these problems, if you think that this is a computer problem according to these three rules here then make a check mark,otherwise, leave the box blank. Again, some of them are a little tricky so you need to check carefully and if you get stuck then of course you can also skip to the answer, give this some thought first.

## 06 q Does the Program stop

So, as always, when I introduce a new concept to you, we'll have a little quiz about this here. Now, it's always a bit difficult to ask, does P go into an infinite loop when given I, so we'll slightly change that to the opposite question here, and ask, does the program stop when given I? So it's basically the other way around, and also it's the more conventional definition of the halting problem, because it's called the halting problem and not the infinite loop problem, to just ask 'does the program stop?' Basically it's really just the opposite of an infinite loop. So if a program stops, it does not go into an infinite loop, and if it does not stop, it must be in some infinite loop. But let's do the quiz now. So I have here 3 programs. This is program 1, this is program 2, and program 3. And, of course, I have inputs for those programs, and what I would like you to tell me for each combination of a program and an input, does the program stop when given this input? It stops, then you can check here, if it does not stop, so if it goes into an infinite loop, then I would like you to check here.

## 06 s Does the Program stop

And, of course, this is not difficult to check. So the first program, definitely that will stop. It will print out the 3 words and the length of that word, and then it's done. Second 1? Yes. That goes into an infinite loop, because x starts out as -2, and while x < -2, it will decrease x. Now, you might have been a bit nitpicky here by saying, "Well, there was a certain limit on how large or small variables can get." Let's assume here that we're working with an integer structure that can get as small as we need it to be, and just uses up more memory in that case, and, in that case, this program here will indeed go into an infinite loop. And now for this 1 here it's very easy to see that it terminates. It just adds 1 to the -100 here, and then it's done. So definitely yes. This program will stop.

## 07 l halt

For these simple examples here, it's very easy to check if the program stops on a given input or does not stop. What if we had an algorithm that could solve the halting problem for any computer program and any input? That would actually be immensely useful. For example, in software testing or in debugging, you would just write your code and then ask the algorithm, "Does this code go into an infinite loop at some time?" And the algorithm would tell you if everything is okay. So, of course, there might be other errors, but at least you've eliminated So let's assume we had such an algorithm. So we had an algorithm, and that algorithm, or function, is called "halt," and halt is called with 2 arguments: 1 is a program, the other is the input. And, of course, this here is a string, and this 1 over here is a string as well. And our specification will be "halt solves the halting problem." Notice that we do not say how long halt has time for this. So halt can be an amazingly, amazingly complicated algorithm. It basically has unlimited resources. This algorithm can solve NP-complete problems, it can solve verse problems, we don't really care. The only thing that we care about is that halt solves the halting problem in some finite amount of time. So even in 1,000 years, 2,000 years, we don't care. As long as halt is guaranteed to solve this problem for any program and for any input, then we're satisfied. No further requirements other then that, after a certain amount of time the algorithm either says "Yes. This problem stops on the input," or "No." And now comes the amazing part. I can prove to you that this algorithm cannot exist. There is no algorithm, no matter how clever, how sophisticated, that can solve the halting problem. The halting problem, in other words, is known as a problem that is undecidable, by which we mean that no computer program or algorithm can reliably decide the halting problem for all possible combinations of programs and inputs. So how do we show that? You might remember from our proof of NP-completeness that considering all possible algorithms for a problem can sometimes lead to very, very messy mathematical proofs. In this case, however, the proof is actually not that difficult. So we're going to go through it together.

## 08 l Proof by Contradiction

And the way we're going to prove this is by using a technique known as a proof by contradiction, which means that I will first assume that the halting problem is decidable, and then show you that this leads to an unresolvable contradiction. So we start out by assuming the halting problem is decideable. So the exact opposite of what we're actually trying to prove. And that is the whole strategy in a proof by contradiction, of course. If we assume this, then it means that there must be some algorithm that actually solves the halting problem, because if there is no such algorithm, then it wouldn't be decidable. And, of course, this algorithm, halt, takes any program, any input, and then, after any given time, using the most complicated, sophisticated techniques whatsoever, it will give us an answer to the halting problem. So there's an algorithm, halt, for the halting problem, and I'm just going to abbreviate it like this here. This algorithm here, halt itself, cannot go into an infinite loop because we are guaranteed that it produces a yes or no answer. This is very important to keep in mind. I'm now going to construct a simple program that, in a way, does the exact opposite of halt. So we'll now use the halt algorithm to build a new algorithm called inverse halt, and it's called inverse halt because it basically, more or less, does the opposite that halt does. Inverse halt, again, takes a program and an input, and it now does the following: If halt determines that the program will stop given this input here, this program here, inverse halt, will go into an infinite loop. And if halt determines no, this program will go into an infinite loop, then inverse halt will stop. So basically, inverse halt stops if the program doesn't stop, and it does not stop if the program stops. So it has exactly the opposite behavior of that program, given that input. And now comes the clever trick. We feed this program here into itself. Now, this is a step that can be quite confusing. At least, sometimes it is very confusing to me. Take a bit of time to consider this. Halt is an algorithm, so halt is basically a text string. Halt is a program, just as this program here is a program. Halt, because it's an algorithm, it's also a program. If we have the program code for halt, then we also have the program code for inverse halt. So this whole thing here can also be considered a program. If you work a bit more on computer science you know similar cases like this. So, for example, if you compile a compiler; that is a very similar case. The compiler might be written in the same source code as the program that your using the compiler to compile. Now I hope I haven't confused you further with this. So the main thing to keep in mind, inverse holt is also a program. So we can now do the following, or run the following program. We run inverse halt as the program input. We feed it itself, and for the input part here we just use an empty string.

## 09 q Inverse halt halts

And now my question to you to think about is the following--what does it mean if this program that we run in inverse halt (inverse halt) stops, so it does not go into an infinite loop. Does it mean that running halt on inverse halt and the empty string returns yes or does it mean that running halt on inverse halt and the empty string returns no, and if you're thinking ahead if it's here, you should notice that there's a third answer, but we'll discuss that in a minute. For now, I just wan you to draw the direct implication for this.

## 09 s Inverse halt halts

This is actually not that complicated to answer. If inverse halt stops on this code here, what does that mean? That means that inverse halt must've gone into this part here of the code because it stops, and this can only be if halt run on the program, which in this case is inverse halt and the empty string is a no, but let's think what that means.  Inverse halt when run on inverse halt and the empty string if that program halts it means that if we had called halt on the same input it returns no. Now, halt is in an algorithm that solves the halting problem.  If it returns no, what it says is the following: Inverse halt itself does not halt when we give the empty string as an input. Let's look back what that means here. We designed inverse halt, so that it does exactly the opposite of the program. So, if the program stops then inverse halt does not stop and if the program does not stop then inverse halt stops. Now, we have just said that inverse halt does not stop, which means that the original program because inverse halt always works in the opposite way the original program stops. But, the original program again is inverse halt running on the empty string. If inverse halt does not halt when given the empty string, it means that inverse halt does halt when given the empty string, and of course, that is a contradiction. It cannot be that both cases are true.  We cannot have the inverse halt does not stop when given the empty string and at the same time inverse halt does stop when given the empty string.

## 10 q Inverse halt doesnt halt

Something's not quite right here. Let's ask the question once more the other way around. What if this program here does not halt? What does that mean if we run the halt algorithm on inverse halt and the empty string.?

## 10 s Inverse halt doesnt halt

And in this case, we come to similar contradictions. So the halt algorithm here will have said yes, because if this program here does not stop, it has gone into an infinite loop, and it can only go into an infinite loop if halt has said yes. Which has a similar implication again. It means that inverse halt stops when given the empty string as an input, but, again, we made inverse halt behave exactly the other way around than this program here does, which, of course, implies that inverse halt does not stop when given an empty string as an input. And again, we have a contradiction here, because either inverse halt stops on the empty string, or it does not stop, but it cannot do both. And that is why we must come to the following conclusion: No matter what this program here is doing, we always come to a contradiction because we find out that inverse halt, run on the empty string, is supposed to stop and not stop at the same time.

What is this mean that we have a contradiction here.  It must mean that either something in the proof has gone wrong or we made some assumption that cannot be true.  Now, let's check them one by one.  The fifth one we just checked in the quiz, so that's where we arrived at the contradiction.  Running this program here, there's nothing wrong with that.  It's a program. So, we assumed that we have it so we can run it.  There's also nothing wrong with this program here. I mean we used to halt algorithm, which we assumed we had and we constructed a very simple algorithm around that with which there's nothing wrong to see.  Well, this step here is correct. So long as the step up here is correct.  So, we have made no mistake in step number two. No mistake in step number three, no mistake in step number four, and no mistake in step number five.  However, if we go through this chain, we arrived at a contradiction. And therefore, something must be wrong with step number one, which is exactly the contradiction we were looking for.  We assumed that the halting problem was decidable that there was an algorithm for this problem.  And therefore, if the assumption that the halting problem is decidable is wrong, it must mean that the halting problem is indeed undecidable. There is no algorithm that will tell you for any given program and any given input if that program will ever stop.  Now, the technique that we used here at least if you're not used to it can be quite confusing. I would, therefore, like to give you a second illustration of this proof here just to make sure that you understand it.

## 12 q Another Approach

So let's construct a table like this. We have here different programs and inputs. So we have program 1, input 1, program 2, input 2 and of course, this list goes on-- can be any programs, any inputs, and let's assume that for the first program, given this input here, the algorithm halt--says yes--meaning that program when we stopped on input 1. And for program 2, we're going to assume that halt says no, which means that program 2 does not stop on the input 2. What I would like you to think about as the next quiz quickie here is what the inverse halt algorithm will do in these cases here. So in this case up here, will the inverse halt program stop or will the inverse halt program go into an infinite loop and the same thing down here. So given this case program 2, will this piece of code here stop or will it go into the infinite loop.

## 12 s Another Approach

And the answer here is of course that the inverse halt program always does the opposite of what the original program does. If the program stops, then the inverse halt program mean as it is will go into an infinite loop--it will not stop. On the other hand, if program 2 does not stop, then inverse halt will stop.

## 13 l Logic Crash

So far all is well, but now comes the trick that we used in the proof, and this table I think is a good way to illustrate this. Now let's assume that we actually put the inverse halt program here into this list, which we can do. Here we used inverse halt, and we used the empty string as an input, although the input doesn't really matter. Now, there are two cases that we distinguished. Either running halt on this program and input here will return yes or it will return no. Now, if it returns yes that means that inverse halt stops just as above here. If halt is yes, the program stops, same thing down here. If halt says no, this means that inverse halt does not stop and now comes the need part. If I asked what does inverse halt do and I used the same logic as you just did in the quiz then I would come to the following conclusions.. If the program stops then inverse halt will go into an infinite loop so I just copied your answer down here. And if inverse halt doesn't stop, I again just copied your answer down here then inverse halt stops. Wait a minute, if inverse halt stops then what inverse halt does is it goes into an infinite loop. That somehow doesn't quite fit and also down here. If inverse halt does not stop, what inverse halt will do? It will stop. Can't really be that case. And this is the technique used in the proof. Basically, the construction of halt and inverse halt works fine so long as you don't fit inverse halt because then the two logics here will crash. So thinking about what this algorithms do in this way here will give you a different conclusion than if you think about it in this way here and there's nothing wrong here with the construction. It makes perfect sense. The only thing that isn't right is the assumption that the halt program can exist in the first place.

## 14 q Implications

Now, before we continue, I would like you to think a little bit about the implications of what we have just shown. We have just shown that the halting problem is undecidable. What I would like to think about for a moment here is what that means or implies, and I would like you to select the ones that are correct. The halting problem being undecidable, does that mean that an algorithm that solves the halting problem would take far more than exponential time to run, does it mean that an algorithm for this problem here for the halting problem cannot exist or does it mean that if we gave them any specific program and are asked to solve the halting problem that will never be possible, at least not using an algorithm.

## 14 s Implications

So the first statement here is obviously not true. We have not even talked about time. We have just pondered the existence of an algorithm for the halting problem or more specifically, the non-existence of such an algorithm, and that is exactly what we have shown. We have shown that there's no algorithm that solves the halting problem if we allow that algorithm to be given any program and any input, but of course, there are specific programs for which we can use algorithms to decide if they will go into loops or not and this is for example one technique that is used in automated software testing. It's not that there can be an algorithm that solves the halting problem for specific cases or specific programs, the halting problem cannot be solved for the general case. So if say you have an algorithm that can solve the halting problem for any program, any input that you throw at it, that cannot be the case, but for specific, special cases, we haven't shown anything so far.

## 15 l Intuition of Undecidability

Now, I don't know about you, but every time I come across the halting problem, I cannot buy the mathematical arguments, but I still feel some would cheat it. It's important I think to realize what is being implied by undecidability and what is not being implied. Informally, all that the undecidability of the halting problem says is that you cannot analyze every aspect of computation using computation. Let's say this program here is supposed to solve the halting problem. This would be the program halt here. The difficulty lies in the fact that all this required not only to be able to say what one given program program two does, and of course, we'll assume there's also an input, but basically, it's supposed to be able to say this for an infinite number of programs. Now, the following is by no means a scientific explanation, but I think it's a good way to think about it. If we have the requirement that halt must be able to look at every other problem here then halt will also be part of this list. So somewhere in that stack of programs, you will have halt. Now, if you say halt must be more complex, and again, this is not a scientific explanation must be more complex that any program it's looking at, well, then halt must be more complex than halt itself, which of course is to an infinite cycle of complexity. So here, we cannot have this spiral of infinity, which of course cannot be so there's the error right there, and again, this is just an intuition a way which I like to think about it. You may find other ways more convenient. What I find is with undecidability and especially the halting problem there is a lot of misunderstandings and pitfalls. And actually, I would now like to go with you through one of the most common pitfalls regarding the halting problem and its undecidability.

## 16 l Common Pitfall

Wome of you might be saying for any real computer, the halting problem is decidable using the following argument. So you're given a program and you're given an input and you put it into the following algorithm. You start out by stimulating step one of the program. So again use the stimulation here just as in previous units. So you simulate step one. If the program terminates at that step then we output "Yes." And else, we record a snapshot of the machine-of the simulated machine, of course. And what I mean by snapshot is something you might remember from the NP completeness proof of SAT. A snapshot is a complete picture of the memory of the machine as well as the line where the program is currently at. And the reason why this algorithm is doing it is it's using one property of an infinite loop and that is if a machine goes into an infinite loop then snapshots at some point in time must repeat. So the third step of the algorithm is it takes that snapshot that had just recorded and compares it against all previous snapshots of the machine. And if it finds just one duplicate, it knows the machine has been exactly at that place before, which means it would also return to that place an infinite number of times. In that case, the halting algorithm or at least this algorithm here, which is supposed to solve the halting problem with output "No." And then the algorithm would simulate the next step of the program and go to step number two. This algorithm would be guaranteed to terminate at a certain point in time either if the program itself terminates or the simulation of the program indicates that it terminates or if the program goes into an infinite loop. Here is important that we have a real computer because if we have a real computer, we do not have infinite memory. So if we do not have infinite memory and the program goes into an infinite loop then at a certain point in time we must have a repeating snapshot. Now, if we had infinite memory that would not be the case.

## 17 q Real Computer and Halting Problem

Now I would like to ask you two questions. My first question for you would be--is this argument correct? Does this algorithm here solve the halting problem on a real computer, so a computer with a finite memory? Please give me your answer here.

## 17 s Real Computer and Halting Problem

And the answer here is that--yes, this algorithm is actually correct. It might not be very practical in terms of running time but the arguments are perfectly fine. If you have finite memory and a program is in an infinite loop, then at a certain point in time snapshots are states of the machine must repeat themselves--there's no other way.

## 18 q Practical Relevance

My question for you is--if we should think that this argument is actually practically relevant meaning okay. On an infinite machine, you might not be able to solve the halting problem, but on any real computer, it's actually possible to solve the halting problem.

## 18 s Practical Relevance

And the answer here, I think, is clearly no because a real computer, of course, has finite memory, but think about your machines. So let's say you have an older computer like me--so you have 1 gigabyte of memory. One gigabyte of memory is approximately 1 billion bytes or 8 billion bits. Now, how many different snapshots can you have with 8 billion bits--that is 2?????????? snapshots. You wouldn't find a fraction of that as atoms in the universe. The argument is correct in theory, but it does not have any practical relevance--almost like the halting problem, which I will soon show you also has actually very little practical relevance, but for this counter argument, it's basically the same. For real computer, I think you can consider the memory to be practically infinite. So this algorithm here just isn't going to cut it unless by real computer, you mean a very, very, very simple one.

## 19 p Undecidability

Okay, so now you might be thinking--well, okay, so programs can become so complicated that no algorithm can decide whether they run infinitely or not. So is there a short program for which I could show you undecidability. Oh yes, there is such as a program--it's not very practical but it is an example for undecidability for very simple program. Here's a simple example of a problem that is actually not decidable, although it's very simple to write. So the input to that problem is an integer and we will just call that integer i and the output is the number of iterations that it takes to get to i=1 using the following two rules-- If i is even, then set i to i/2 so they divide by 2. If i is odd, set i to 3i+1, just two simple rules. And so for example when you start out with i being 10, then we first apply the first rule. We get down to 5, 5 is odd so the new value is 16 and then we divide by 2, we divide by 2, we divide by 2, we divide by 2, so we have 1, 2, 3, 4, 5, 6 iterations. So i=10, then the answer is 6. So now we're going to let you play a little bit with this algorithm and then discuss the undecidability for it.

## 20 l Collatz

These two rules here form what is known more formally as the Collatz series named after the German mathematician Lothar Collatz and appeared somewhat erratic as I think you've seen with the program. Sometimes it will terminate very quickly for certain values of i and sometimes actually it will behave super eratic and it will go up and down and up and down until it finally terminates. Now here's the thing, it has been conjectured that this algorithm here will terminate for any value of i but so far nobody has been able to prove that. So if we were given an integer for this function here for which the Collatz hypothesis that this algorithm here always terminates has not been verified then that would indeed be undecidable. Now truth be told, it would have to be a very large integer because the Collatz hypothesis has been verified for large numbers indeed. Nevertheless, once the integer is out of this range, we have no way of deciding whether this algorithm would terminate or not. The only thing we can do is run it so the Collatz problem or the Collatz hypothesis is an open mathematical problem and of course as you know it's not the only open mathematical problem so we could have other mathematical problems as well. But I want to show you something. So if we have an algorithm that solves the halting problem, so if we indeed had this algorithm halt what we could then do for example is write the following program for i = 1 to 10¹?? then run the Collatz rules for i so we start with i = 1 then we go to i = 2 and so on and then we feed this problem into the halting algorithm. And now if the halting algorithm says yes, then this means that the Collatz hypothesis is true for any number from 1 to 10¹?? and if it says no then it means that there is some number for which the Collatz hypothesis is not true, which means that this part here would go into an infinite loop and then we can easily check this for larger and larger and larger numbers. An algorithm that would be able to solve the halting problem would actually be able to solve almost any open mathematical problem there is out there. Any mathematical problem that can be formulated as an algorithm could be decided by an algorithm that solves the halting problem. So this would almost be a kind of omission algorithm which also provides an intuition why this halting algorithm here cannot possibly exist. It would just simply be too powerful. It could answer almost any mathematical question that we can think of.