From - Mon Mar 8 10:26:31 2004 X-Mozilla-Status: 0001 X-Mozilla-Status2: 00000000 Path: acsu.buffalo.edu!rapaport From: rapaport@cse.buffalo.edu (William J. Rapaport) Newsgroups: sunyab.cse.510 Subject: POSITION PAPER 2 -- ANALYSIS & GRADING Date: Sun, 7 Mar 2004 20:33:25 -0500 (EST) Organization: Computer Science and Engineering Lines: 335 Sender: Ncs@buffalo.edu Distribution: sunyab Message-ID: NNTP-Posting-Host: castor.cse.buffalo.edu X-Trace: prometheus.acsu.buffalo.edu 1078709605 3960 128.205.32.14 (8 Mar 2004 01:33:25 GMT) X-Complaints-To: abuse@buffalo.edu NNTP-Posting-Date: Mon, 8 Mar 2004 01:33:25 +0000 (UTC) X-Newsreader: trn 4.0-test76 (Apr 2, 2001) Xref: acsu.buffalo.edu sunyab.cse.510:313 ------------------------------------------------------------------------ Subject: POSITION PAPER 2 -- ANALYSIS & GRADING ------------------------------------------------------------------------ I have read and graded about half of your position papers. Everyone who turned one in but hadn't gotten graded last time got graded this time, plus a few people who had gotten graded last time got graded this time, too. This is a long posting, containing three parts: 1. A sample analysis of the argument for Position Paper 2. 2. A discussion of the major problems that I found with your analyses. 3. How I graded those papers that I did grade (as before, I only graded a subset of the papers that I received). Also, as before, if any of you who were graded on Position Paper 2 would like to revise your response once more, please hand in the revision no later than Tue., Mar. 23 (Spring Break gives you an extra week!); it should be typed, double-spaced, single-sided, and no longer than 2 pages. Please attach all previous version. ======================================================================== 1. Sample analysis of the argument. ------------------------------------------------------------------------ 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: An algorithm, A, for solving a problem P (or, for computing a function F) is a finite procedure (i.e., a finite set of instructions) for solving P (or, computing F) that is: 1. unambiguous for the computer or human who will execute it (i.e., all steps of the procedure must be clear and well-defined for the executor), and 2. effective; i.e., A must eventually halt, and it must output a correct solution to P (or, the correct computation of F). I interpret this to mean that any algorithm must satisfy this definition. Some of you tried to use what looked like logical formulas in your analyses (unfortunately, not very successfully :-(, so, for those who did, here's how to write this interpretation in first-order logic (FOL) (notice that you have to provide a "semantics" indicating what each of the non-logical symbols mean: Let "Alg(x)" mean: x is an algorithm. Let "Def(x)" mean: x satisfies the definition given above. Then premise 1 = Forall (x) [Alg(x) <-> Def(x)], or, in English: 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 computing 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 ;-) In FOL: Let "Prog(x)" mean: x is a program expressed in a computer programming language. Then premise 2 = Forall (x) [Prog(x) -> Alg(x)], or, in English: 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. 1. I.e., every program in any programming language can be translated into the language for programming Turing machines, and vice versa. 2. I.e., any problem that is solvable by any programming language (or, any function that is computable by any programming language) is solvable (or, computable) by a Turing machine, and vice versa. I interpret this to mean that any program is expressible as a TM program; in FOL: Let "TM(x)" mean: x is a TM program Then premise 3 = Forall (x) [Prog(x) -> TM(x)], or: for any x, if x is a program, then x is 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: 1. E.g., airline-reservation systems, ATMs, operating systems, etc., never halt. 2. E.g., heuristic AI programs don't always solve exactly the problem that they were written for, but only come very close. 3. E.g., the effectiveness of mundane procedures depends on the environment in which they are executed. (And so on.) I interpret this to mean that there are some programs that are not algorithms (in the sense of premise 1). The easiest way to represent this in FOL is to consider one such program (it doesn't matter which). Call it "p". Then premise 4, in FOL, is: Prog(p) & ~Alg(p) I.e., 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 the argument is not factual! But it also means something else: We have an example of an argument with inconsistent premises. That means that its conclusion, NO MATTER WHAT IT IS!, must be valid! (It's a principle of logic that, from a false statement, anything whatsoever follows. The conjunction of our premises must be false, since 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 ~TM(p), we would need to show ~Prog(p). To do that we would need to show ~Alg(p). But that's easy to show, since we already have ~Alg(p). I.e., because ~Alg(p), we can conclude that ~Prog(p), from which we can infer ~TM(p).] Because premises 2 and 4 are inconsistent, we can make them consistent by rejecting one of them. Let's consider both cases: Case 1: Reject 2; keep 4: Then our premises become: 1. Alg(x) <-> Def(x) 3. Prog(x) -> TM(x) 4. Prog(p) & ~Alg(p) Can we show 5? What does 5 say? These programs cannot be modeled by Turing machines "These programs" refers to programs like p. So, in FOL, 5 says: ~TM(p). Now, if we can show that Prog(p), then premise 3 will allow us to conclude that TM(p). And, indeed, we have Prog(p). So, we have TM(p). So, we cannot show ~TM(p)! So, in this case, the argument is invalid, and the correct conclusion is that TM(p), i.e., that all the examples in premise 4 are indeed Turing-computable. Case 2: Reject 4; keep 2: Then our premises become: 1. Alg(x) <-> Def(x) 2. Prog(x) -> Alg(x) 3. Prog(x) -> TM(x) Now can we show 5, i.e., ~TM(p), where p is such that both Prog(p) and ~Alg(p)? But there is no such p, because, by premise 2, if Prog(p), then Alg(p). So, in this case, too, the argument is invalid, but this time the correct conclusion is that TM(x), for all x. What about conclusion 6? For 6 to follow from 5, we need to show that ~TM(p) -> ~C(p), where "C(x)" means: x is computable. Taking the contrapositive, this means we have to show that C(p) -> TM(p). Given premise 3, which says that Prog(p) -> TM(p), we might try to show that C(p) -> Prog(p). 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. 2. Major problems with your analyses. ------------------------------------------------------------------------ The major problem that I found was that many of you are still not familiar with the proper terminology or methodology for analyzing an argument. You might want to re-read the website on critical thinking that I told you about at the beginning of the semester: http://www.kcmetro.cc.mo.us/longview/ctac/toc.htm Here's a quick summary: Given an argument with premises P1..Pn and conclusion C: P1 P2 ... Pn -- C to analyze it, do the following: a) For each premise Pi, decide whether you agree with Pi or not, and say why. (More formally, determine whether Pi is true or false, and give a brief argument in support of this.) b) If all the Pi are true, then the *argument* can be said to be "factual". As I use the term, only *arguments* can be "factual", not premises. Premises are either true or false. (Also, premises are not "arguments".) c) Determine whether the argument is valid. An argument is valid if it is impossible for it to be factual (i.e., all premises are true) while the conclusion is false. I.e., imagine a situation in which the premises are all true; in that situation, would the conclusion have to be true, too? If so, then the argument is valid. If not, then it's invalid. I.e., an argument is invalid if it's possible for the premises to all be true, yet for the conclusion to be false. (Note that only arguments, not premises, can be "valid" or "invalid". Sometimes, however, it's convenient to say that a *conclusion" validly follows from the premises, or, for short, that a conclusion is valid.) d) If the argument is both factual and valid, then it's sound. e) If you have decided that the argument is sound, then you are logically obligated to agree to the conclusion. If, however, you found the argument invalid OR found the argument to be non-factual, then it's STILL possible for the conclusion to be TRUE!!! So, in either of these cases, you must independently decide if you agree with the conclusion. And you must give your own argument for it. 3. Grading ------------------------------------------------------------------------ In grading this, I looked primarily for whether you followed the above steps. I only evaluated your particular reasons if I felt that they indicated some serious misunderstanding. So, for instance, I didn't care whether you thought that premise 2, say, was true or false; but I did care that you said which of those two truth values you thought it was, and I looked to make sure that you gave reasons for your opinion. So, your interpretation of the argument might have been very different from mine (in fact, most of them were), but the method of analysis ought to have been the same. So my grading scheme went as follows: Premise 1: Agree/disagree 0 or 1 point Note: I gave 0 point if you did not say clearly whether or not you agreed or disagreed; I gave 1 point if you did, but it didn't matter whether you agreed or disagreed. Reason 0, 1, 2, or 3 points Note: I gave 0 points if you did not give your reason for agreeing or disagreeing; I gave 3 points if you gave a clear reason. I gave 1 point if you gave a reason that seemed to me to indicate a clear misunderstanding. I gave 2 points as "partial" credit for an reason that was neither clearly right or clearly wrong. Premise 2: Agree/disagree 0,1 Reason 0,1,2,3 Premise 3: Agree/disagree 0,1 Reason 0,1,2,3 Premise 4: Agree/disagree 0,1, Reason 0,1,2,3 realization that 4 is inconsistent with 2, hence that arg't is not factual 0,1,2,3 Conclusion 5: Agree 0,1 Reason 0,1,2,3 realization that arg't from 1-4 to 5 is (trivially) valid 0,1 Rejection of 2 in favor of 4, & implication for conclusion plus reason 0,2,4,6 XOR Rejection of 4 in favor of 2, & implication for conclusion plus reason 0,2,4,6 Conclusion 6: def of "computable" 0,1,2,3 Agree? + reason 0,1,2,3 Total = 36 points 410/498 both 510 A 35-36 A- 33-34 B+ 31-32 B 29-30 B- 27-28 C+ 25-26 C 21-24 13-24 C- 17-20 D+ 13-16 D 7-12 F 0-6