From owner-cse584-sp07-list@LISTSERV.BUFFALO.EDU Wed Apr 4 16:06:46 2007 Received: from ares.cse.buffalo.edu (ares.cse.Buffalo.EDU [128.205.32.79]) by castor.cse.Buffalo.EDU (8.13.6/8.12.10) with ESMTP id l34K6jGk012695 for ; Wed, 4 Apr 2007 16:06:45 -0400 (EDT) Received: from front1.acsu.buffalo.edu (coldfront.acsu.buffalo.edu [128.205.6.89]) by ares.cse.buffalo.edu (8.13.6/8.13.6) with SMTP id l34K6QV4065374 for ; Wed, 4 Apr 2007 16:06:27 -0400 (EDT) Received: (qmail 1115 invoked from network); 4 Apr 2007 20:06:26 -0000 Received: from mailscan1.acsu.buffalo.edu (128.205.6.133) by front1.acsu.buffalo.edu with SMTP; 4 Apr 2007 20:06:26 -0000 Received: (qmail 29913 invoked from network); 4 Apr 2007 20:06:26 -0000 Received: from deliverance.acsu.buffalo.edu (128.205.7.57) by front3.acsu.buffalo.edu with SMTP; 4 Apr 2007 20:06:26 -0000 Received: (qmail 5812 invoked from network); 4 Apr 2007 20:06:19 -0000 Received: from listserv.buffalo.edu (128.205.7.35) by deliverance.acsu.buffalo.edu with SMTP; 4 Apr 2007 20:06:19 -0000 Received: by LISTSERV.BUFFALO.EDU (LISTSERV-TCP/IP release 14.5) with spool id 4383559 for CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU; Wed, 4 Apr 2007 16:06:19 -0400 Delivered-To: cse584-sp07-list@listserv.buffalo.edu Received: (qmail 12606 invoked from network); 4 Apr 2007 20:06:19 -0000 Received: from mailscan4.acsu.buffalo.edu (128.205.6.136) by listserv.buffalo.edu with SMTP; 4 Apr 2007 20:06:19 -0000 Received: (qmail 28470 invoked from network); 4 Apr 2007 20:06:18 -0000 Received: from castor.cse.buffalo.edu (128.205.32.14) by smtp1.acsu.buffalo.edu with SMTP; 4 Apr 2007 20:06:18 -0000 Received: from castor.cse.Buffalo.EDU (rapaport@localhost [127.0.0.1]) by castor.cse.Buffalo.EDU (8.13.6/8.12.10) with ESMTP id l34K6HmT012645 for ; Wed, 4 Apr 2007 16:06:17 -0400 (EDT) Received: (from rapaport@localhost) by castor.cse.Buffalo.EDU (8.13.6/8.12.9/Submit) id l34K6HDi012644 for cse584-sp07-list@listserv.buffalo.edu; Wed, 4 Apr 2007 16:06:17 -0400 (EDT) X-UB-Relay: (castor.cse.buffalo.edu) X-PM-EL-Spam-Prob: : 7% Message-ID: <200704042006.l34K6HDi012644@castor.cse.Buffalo.EDU> Date: Wed, 4 Apr 2007 16:06:17 -0400 Reply-To: "William J. Rapaport" Sender: "Philosophy of Computer Science, Spring 2007" From: "William J. Rapaport" Subject: POSITION PAPER 3 -- ANALYSIS To: CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU Precedence: list List-Help: , List-Unsubscribe: List-Subscribe: List-Owner: List-Archive: X-UB-Relay: (castor.cse.buffalo.edu) X-DCC-Buffalo.EDU-Metrics: castor.cse.Buffalo.EDU 1335; Body=0 Fuz1=0 Fuz2=0 X-Spam-Status: No, score=-2.0 required=5.0 tests=AWL,BAYES_00,SUBJ_ALL_CAPS autolearn=no version=3.1.7 X-Spam-Checker-Version: SpamAssassin 3.1.7 (2006-10-05) on ares.cse.buffalo.edu X-Virus-Scanned: ClamAV 0.88.6/3014/Wed Apr 4 14:32:14 2007 on ares.cse.buffalo.edu X-Virus-Status: Clean Status: R Content-Length: 8739 ------------------------------------------------------------------------ Subject: POSITION PAPER 3 -- ANALYSIS ------------------------------------------------------------------------ This is a long posting, containing a sample analysis of the argument for Position Paper 3. 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...." I interpret this 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, 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-loop, 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! 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 cases: 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 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 it 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 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", 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 all false, 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.