That's only part of the story to show that all the computers we can imagine are equivalent. But, now we come to the question of, what are the problems that we can solve? Are there problems that we can't solve? To introduce that, I'll describe a very simple puzzle known as Post's Correspondence Problem. It's a family of puzzles and it's based on a set of cards. You'll see in an example in just a minute. So, we suppose we have N different types of cards, and we have no limit on the number of cards of each type. In each card is characterized by a top string and a bottom string. The question that we have to ask, given the N types of cards, is; does there exist an arrangement of cards with matching top and bottom strings? So, with a few examples you'll see. So here, say we have these four types of cards. Again, we have an unlimited number of each type. So, the first one has BAB on the top, and A on the bottom and like that. The last one is BA on the top, and B in the bottom. What we want to know is, can we take cards from these piles and as many as we want, and get an arrangement where the top and bottom strings reading across the cards are the same? In this case, the answer is easy. In fact, almost every move its force. So let's say we pick a card of type one. So, it's got A on the top, and ABA in the bottom. So, to get the top and bottom strings to match, now for our next card, we have to pick one that starts with a B. So, say we take a card of type three. So, now we have ABA on the top, ABA, and then a B in the bottom. So, again, to get a match, we have to have one that starts with a B on the top. So, let's say we take one of type zero for our next one. So, now we have alternating As and Bs ending with a B, on the top, and we have the same thing but with one fewer character on the bottom. So now, we need a card that has a B in the bottom. In this case, we pick a card of type two. Now, we have six characters on the bottom. We have eight characters on the top. So, we're going to need, after a little analysis, to pick one of type one. They both have to be As, and now we've got a match. There are nine characters alternating As and Bs both in the top and the bottom, beginning and ending with A. So, that's a solution for that set of cards. But here's another set of cards. Is there going to be a similar solution for this set of cards which is a little different? If you look at this one for a while you say, "Obviously there's no solution because you can't even match the first character. Every one of these cards differ on their first character. So, there's no way to even get started." So, that's the question in general. Given a set of cards, is there going to be a matching top and bottom strings? Here's a much more complicated set developed by my colleague, Andrew Appel and this one there actually exists a solution that starts with a card of type zero, and you're welcome to try it. But the question is, can you write a program that would take, as input, the sets of cards, and then tell you as output whether or not there is an arrangement that does the job. You can imagine that we might have crafted this as a programming assignment. At first blush it seems not so much more difficult than other programming assignments, or programming tasks that you've tried. So, maybe would be a reasonable thing for us to ask you to do as your learning program. Does there really exist an arrangement of cards with matching top and bottom strings? It's a reasonable idea. Now, let's do it. Let's take in card types as input, easy to do, and then solve the problem. The surprising fact is that it's not possible to write such a program. We can prove that. It's a rather amazing fact. So we could give you a job that you can't possibly do, and we know it. Now, we're not quite that sadistic with our students but there may be teachers out there who do. So, let's look at why we can say this. Here's another impossible problem. A famous one called the halting problem. And it's famous because Turing looked at this problem. So, let's say what we want to do is write a Java program that reads in code for given Java functions static method f, and it gets the input x, and is supposed to decide whether or not f(x) results in an infinite loop. So, for example, let's say we had this function as input. If you study this one for a while, you can say, "Okay, I can look at this and say, "Yeah, it's going to halt if x is a power of two. Otherwise, it's not going to halt." So you can convince yourself that that's the case. This one doesn't look that much different. It's same thing except now instead of multiplying by two, x equals 2x plus one. We do x equals 3x plus one. In that one, well that's the Collatz conjecture. We talked about when we did the recursion lecture. No one even knows whether that one halts or not. People have studied extremely long sequences and so forth, but there's no proof that that thing halts for all different values of x. So, at least these examples show that it might be a challenge to write a program that reads in code for a Java function decides whether or not it goes into an infinite loop. What we're going to talk about next is the proof that it's not possible to write such a program even leaving that Collatz conjecture aside. That's called the undecidability of the halting problem. So, we say that yes, no problem whose answer is yes or no is undecidable if there's no Turing machine that can solve it. That is that can be guaranteed to wind up in a yes state, or no state. Opposite of that is we say a problem is computable if there is a Turing machine that exists, that solves it. And what Turing showed in the same paper, where he showed the universality of Turing machines, is that the halting problem is undecidable. And that's got very profound implications. First of all, Patts proves the existence of something that we can't compute. There's a problem that no Turing machine can solve. But because of universality, that means there's no computer at all can solve that problem. And what's worst is there are many many problems that no computer can solve. We need to understand this concept, if we're going to be trying to solve problems with computers. So as a warm up to think about the proof of the undecidability, the halting problem, we're going to talk about a logical puzzle called the Liar paradox that goes back to ancient Greek philosophers. So what you're supposed to do is divide all statements into two categories: true and false. So two plus two equals four, we agree is true, two plus two equals 99, we agree is false. Earth is round, earth is flat, and so forth. Earthworms I guess have more hearts than three. So that one's false, and Saturn rotates counter-clockwise and so forth. All statements want to be divided into two categories, true and false. But now consider the statement ''This statement is false.'' Well, can we put it in the true category? No because it says this statement is false and if it's true then it's false. That's a contradiction. Can we put it in the false category? No because if we put it in the false category, that says the statement is false and it's in the false category so that's true. That's a contradiction. So what are we to make of this situation? Well, the source of the difficulty is self-reference, a statement referring to itself. The logical conclusion that we can draw from this is, that you can't label all statements as either true or false. Here's an example of a statement that can't be labeled either way. So we made an assumption that's not true and the existence of this statement is false contradicts the assumption and that's a proof that you can't do it. That's a way to think of the proof now that we're going to do for the halting problem. It's a little more complicated than this but it's based on the same idea. So this is not Turing's proof because we're going to do it in terms of Java programs, but by universality we may as well. So here's how. So we're going to assume that there's a function halt, that takes the code of a function say it's a string as input and the input to that function x, and solves the problem. So any function, any input to that function, this function halt will tell us whether or not it goes into a loop. Again, might as well use Java because we could phrase the same thing on a Turing machine. So this is an amazing function. You have some terribly clever analysis of f and x. It can return true or false. Either it halts or it doesn't halt. So the arguments of the function and the input say encoded as strings. The return value is true if f(x) halts and false if f(x) does not halt, and that function itself is always halt. It's supposed to be able to do this for any function and any input to that function. The idea is, like the Liar's Paradox, we're going to make that assumption, and we're going to follow a logical argument. If we get to an absurd statement, then we know the assumption is false. So here's how the proof goes. Again, assume the existence of halt(f, x) that solves the problem. So that's our code. Now, within the comments is something terribly clever. So now we're going to create a new function from that called strange(f), and that takes function as our argument. What's that's going to do is give the function itself as input. So and they're all strings, so there's no problem with doing that. So what's strange is going to do is if f(f) halts it'll go into an infinite loop. And if f(f) doesn't halt, then it'll halt. Is kind of the opposite. That's a simple code. If we have halt, then we can just call it with both its arguments the same. If it's f(f) is going to halt just go into an infinite loop. So that's strange. It's just a client to our assumed solution to the problem. Now, and this is why we call it strange. Now, we're going to call that function with itself as argument. So the question is, does that thing halt or not halt. Let's look at the two cases. So if strange or strange(strange) halts, then if you look at the code for strange(strange), it goes into an infinite loop. Strange(strange) halts. It goes into infinite loop. That's the definition of strange. If it doesn't halt on the other hand, then it halts. Again, that's the definition of strange, and that's absurd. If we were to have a solution to the halting function, we can make this call and it's just a client. That either if it halts, doesn't halt, or if doesn't halt, it halts. That means that since our only assumption was the solution to the halting problem, that thing cannot exist. This is admittedly a little mind-bending for people not used to logic. But you can go through and check all the steps of this. It's actually a pretty simple extension of the Liar's Paradox the way we've got it phrased. But it's very profound consequences.
