CS 70 Discrete Mathematics for CSSpring 2008 David Wagner Note 24Self-Reference and ComputabilityThe Liar’s ParadoxPropositions are statements that are either true or false. We saw before that some statements are not welldefined or too imprecise to be called propositions. But here is a statement that is problematic for more subtlereasons: “All Cretans are liars.” So said a Cretan in antiquity, thus giving rise to the so-called liar’s paradoxwhich has amused and confounded people over the centuries. Actually the above statement isn’t really aparadox; it simply yields a contradiction if we assume it is true, but if it is false then there is no problem.A stronger formulation of this paradox is the following statement: “This statement is false.” Is the statementtrue? If the statement is true, then what it asserts must be true; namely that it is false. But if it is false, thenit must be true. So it really is a paradox. Around a century ago, this paradox found itself at the center offoundational questions about mathematics and computation.In this lecture, we will study how this paradox relates to computation. Before doing so, let us consideranother manifestation of this paradox, created by the great logician Bertrand Russell. In a village with justone barber, every man keeps himself clean-shaven. Some of the men shave themselves, while others go tothe barber. The barber proclaims: “I shave all and only those men who do not shave themselves.” It seemsreasonable then to ask the question: Does the barber shave himself? Thinking more carefully about thequestion though, we see that we are presented with a logically impossible scenario. If the barber does notshave himself, then according to what he announced, he shaves himself. If the barber does shave himself,then according to his statement he does not shave himself!The Halting ProblemAre there tasks that a computer cannot perform? For example, we would like to ask the following basicquestion when compiling a program: does it go into an infinite loop? In 1936, Alan Turing showed that thereis no algorithm that can perform this test. The proof of this remarkable fact is very elegant and combinestwo ingredients: self-reference (as in the liar’s paradox), and the fact that we cannot separate programs fromdata. In computers, a program is represented by a string of bits just as integers, characters, and other dataare. The only difference is in how the string of bits is interpreted.We will now examine the Halting Problem. Given the description of a program and its input, we would liketo know if the program ever halts when it is executed on the given input. In other words, we would like towrite a program TestHalt that behaves as follows:TestHalt(P, I) =(“yes”, if program P halts on input I;“no”, if program P loops on input I.Why can’t such a program exist? First, let us use the fact that a program is just a bit string, so it can be inputCS 70, Spring 2008, Note 24 1as data. This means that it is perfectly valid to consider the behavior of TestHalt(P, P), which will output“yes” if P halts on input P, and “no” if P loops forever on input P. We now prove that such a program cannotexist.Proof: Define the program Turing, as follows:Turing(P):1. If TestHalt(P, P)=“yes”, then loop forever.2. Otherwise, halt.So if the program P halts when given P as input, then Turing(P) loops forever; otherwise, Turing(P) halts.Assuming we have the program TestHalt, we can easily use it as a subroutine in line 1 of the above program.Now let us look at the behavior of Turing(Turing), i.e., look at the result of running the program Turing onthe input Turing. There are two cases: either it halts, or it does not. If Turing(Turing) halts, then it must bethe case that TestHalt(Turing, Turing) returned “no”. But that would mean that Turing(Turing) should nothave halted. In the second case, if Turing(Turing) does not halt, then it must be the case that TestHalt(Turing,Turing) returned “yes”, which would mean that Turing(Turing) should have halted. In both cases, we arriveat a contradiction—which must mean that our initial assumption, namely that the program TestHalt exists,was wrong. Thus, TestHalt cannot exist, so it is impossible for a program to check if any general programhalts.What proof technique did we use? This was actually a proof by diagonalization. Why? Since the set of allcomputer programs is countable (they are, after all, just finite-length strings over some alphabet, and the setof all finite-length strings is countable), we can enumerate all programs as follows (where Pirepresents theithprogram):The i, jthentry is H if program Pihalts on input Pjand L if it does not halt. Now if the program Turingexists it must occur somewhere on our list of programs, say as Pn. But this cannot be, since if the nthentry inthe diagonal TestHalt(Pn, Pn) claims to halt, then Turing loops. If the entry asserts that it loops, then Turingshould have halted. Thus the existence of a TestHalt program contradicts the fact that we listed all possibleprograms P, and therefore the halting problem cannot be solved.In fact, there are many more cases of questions we would like to answer about a program, but cannot. Forexample, we cannot know if a program ever outputs anything. We cannot know if it ever executes a specificline. We cannot even check to see if the program is a virus. These issues are explored in greater detail in theadvanced course CS172.CS 70, Spring 2008, Note 24
View Full Document
Unlocking...