------------------------------------------------------------------------ Subject: POSITION PAPER 2 -- ANALYSIS ------------------------------------------------------------------------ This is a long posting, containing a sample analysis of the argument for Position Paper 2. There are many ways to analyze any argument, and different analyses can come up with radically different evaluations. What follows is merely *one* way that this argument could have been analyzed. The point of this sample is not so much to show you what you *should* have said (because, after all, what I say below is itself an argument open to analysis and evaluation). Rather, it's main purpose is to show you *how* to analyze an argument. ------------------------------------------------------------------------ Analysis of premise 1: Knuth...characterizes the informal, intuitive notion of "algorithm" as follows: a. "Finiteness. An algorithm must always terminate after a finite number of steps...." b. "Definiteness. Each step of an algorithm must be precisely defined; the actions to be carried out must be rigorously and unambiguously specified for each case...." c. "Input. An algorithm has zero or more inputs...." d. "Output. An algorithm has one or more outputs...." e. "Effectiveness. [A]ll of the operations to be performed in the algorithm must be sufficiently basic that they can in principle be done exactly and in a finite length of time by a [hu]man using pencil and paper...." ------------------------------------------------------------------------ (By the way, his name is "Knuth", pronounced "k'nooth". It is not "Kunuth" or "Kunth", as some of you consistently wrote it :-) http://www-cs-faculty.stanford.edu/~uno/ Also, although this *premise* is his explication of 'algorithm', the rest of the *argument* is mine, not his.) ------------------------------------------------------------------------ I interpret Knuth's characterization of 'algorithm' to mean that any algorithm must satisfy this definition. We can simplify a bit as follows: premise 1 = For any x, x is an algorithm iff x satisfies the definition given above. For the sake of argument (since it will turn out not to matter!), let us assume that this is true (it's certainly plausible). Analysis of premise 2: Computer programming languages (like Java, Lisp, Fortran, etc.) are formal languages for expressing (or "implementing") algorithms. I interpret this to mean that any program expressed in a computer programming language is an algorithm. (Other interpretations are possible, as many of you impressed upon me; some of them are even good interpretations ;-) So: premise 2 = For any x, if x is a program expressed in a computer programming language, then x is an algorithm. I will reserve comment on whether this is true or false till our analysis of premise 4. (But we can take it to be true; it's pretty reasonable.) Analysis of premise 3: Every computer programming language is equivalent in expressibility to a Turing-machine programming language. a. I.e., every program in any programming language can be translated into the language for programming Turing machines, and vice versa. b. I.e., any function that is computable by any programming language is computable by a Turing machine, and vice versa. Note, by the way, that this is a *single* premise. "I.e." is an abbreviation for the Latin phrase "id est", which means "that is"; in other words, "i.e." means "in other words". I interpret this to mean that any program is expressible as a TM program: premise 3 = For any x, if x is a program, then x is expressible as a TM program. This seems to me to be true. It is a restatement of the fact that the class of functions computable by any of the standard models of computation (TMs, lambda calculus, recursive functions, register machines, etc.) is the same as the class of functions computable by any of the others. Since all high-level, computer-programming languages, or, to be more precise, any that have sequence, selection, and (while-)repetition, are TM-equivalent, I take it that premise 3 is true. As it turns out, it doesn't matter (see below)! Analysis of premise 4: Some real computer programs violate parts of definition 1: a. E.g., airline-reservation systems, ATMs, operating systems, etc., never terminate. b. E.g., heuristic AI programs don't always compute exactly the function that they were written for, but only come very close. c. E.g., the effectiveness of mundane procedures depends on the environment in which they are executed. d. E.g., algorithms can apparently be written that can perform an infinite computation in a finite amount of time (by continually accelerating). (And so on.) (By the way, as long as I'm teaching you some Latin, "e.g." is an abbreviation for the Latin phrase "exempli gratia", which means "for the sake of example", or just "for example", for short.) I interpret this to mean that there are some programs that are not algorithms (in the sense of premise 1). The easiest way to think about this is to consider one such program (it doesn't matter which). Call it "p". Then premise 4 is: p (whatever it is) is a program that is not an algorithm. Now, note that my interpretation of premise 4 is the *negation* of my interpretation of premise 2! (Premise 2 says that EVERY program is an algorithm; premise 4 says that SOME program is NOT an algorithm.) That means that both of them can't be true at the same time, which means that it's impossible for all of the premises to be true simultaneously! I.e., we have an example of an argument with inconsistent premises. That means that it is valid, NO MATTER WHAT ITS CONCLUSION IS! (It's a principle of logic that, from a false statement, anything whatsoever follows. The conjunction of our premises must be false, because two of them are negations of each other, so anything follows, including conclusion 5.) Let me repeat: This IS a valid argument (as I have interpreted it; remember, other interpretations are possible). [In case you're still not convinced, consider this: To show that p is not expressible as a Turing-machine program, we would need to show that p is not a computer program. To do that, we would need to show that p is not an algorithm. But that's easy to show, since we already have that p is not an algorithm by the way we defined p. I.e., because p is not an algorithm, we can conclude that p is not a program, from which we can infer that p is not expressible as a TM program.] Because premises 2 and 4 are inconsistent, we can *make* the argument consistent by *rejecting* one of them. Let's consider both possibilities: Case 1: Reject 2; keep 4: Then our premises become: 1. for any x, x is an algorithm iff x satisfies Knuth's definition 3. for any x, if x is a program, then x is expressible as a TM program 4. p is a program but not an algorithm Can we show 5? What does 5 say? These programs do not implement TMs. "These programs" refers to programs like p. So, 5 says: p is not expressible as a TM program Now, if we can show that p *is* a computer program, then premise 3 will allow us to conclude that p *is* expressible as a TM program. And, indeed, we have that p is a computer program. So, we have that p is expressible as a TM program. So, we *cannot* show that p is NOT expressible as a TM program! So, in this case, the revised argument is invalid, and the correct conclusion is that p IS expressible as a TM program, i.e., that all the examples in premise 4 are indeed Turing-computable. Case 2: Reject 4; keep 2: Then our premises become: 1. for any x, x is an algorithm iff x satisfies Knuth's definition 2. for any x, if x is a computer program, then x is an algorithm 3. for any x, if x is a computer program, then x is expressible as a TM program NOW can we show 5, i.e., that p is *not* expressible as a TM program, where p is both a computer program but not an algorithm? But there is no such p, because, by premise 2, if p is a computer program, then it *is* an algorithm. So, in this case, too, the revised argument is invalid, but this time the correct conclusion is that x *is* expressible as a TM program. What about conclusion 6? For 6 to follow from 5, we need to show that if p is not expressible as a TM program, then p is not computable. Taking the contrapositive, this means we have to show that if p is computable, then it is expressible as a TM program. Given premise 3, which says that, if p is a *computer* program, then it is expressible as a *TM* program, we might try to show that, if p is computable, then p is a computer program. To do that, we would need a definition of "computable" (as many of you noted), but the argument doesn't provide that, so 6 does NOT follow from 5. To summarize: We see that 5 validly--but trivially--follows from 1-4, but since 1-4 are inconsistent, the argument from 1-4 to 5 is unsound. And we see that the argument from 5 to 6 is invalid. However, we *still* need to decide if we think that 5 and 6 are true, independently of this particular argument. After all, you might be able to think of a better argument for 5 or for 6. I won't provide that here, however, since we need to move on to other issues.