0:03

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.

Â