From owner-cse584-sp07-list@LISTSERV.BUFFALO.EDU Thu Mar 8 11:24:41 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 l28GOfDS019040 for ; Thu, 8 Mar 2007 11:24:41 -0500 (EST) Received: from front2.acsu.buffalo.edu (warmfront.acsu.buffalo.edu [128.205.6.88]) by ares.cse.buffalo.edu (8.13.6/8.13.6) with SMTP id l28GObT3014489 for ; Thu, 8 Mar 2007 11:24:37 -0500 (EST) Received: (qmail 21408 invoked from network); 8 Mar 2007 16:24:37 -0000 Received: from mailscan1.acsu.buffalo.edu (128.205.6.133) by front2.acsu.buffalo.edu with SMTP; 8 Mar 2007 16:24:37 -0000 Received: (qmail 4504 invoked from network); 8 Mar 2007 16:24:36 -0000 Received: from deliverance.acsu.buffalo.edu (128.205.7.57) by front1.acsu.buffalo.edu with SMTP; 8 Mar 2007 16:24:36 -0000 Received: (qmail 25908 invoked from network); 8 Mar 2007 16:24:26 -0000 Received: from listserv.buffalo.edu (128.205.7.35) by deliverance.acsu.buffalo.edu with SMTP; 8 Mar 2007 16:24:26 -0000 Received: by LISTSERV.BUFFALO.EDU (LISTSERV-TCP/IP release 14.5) with spool id 3702462 for CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU; Thu, 8 Mar 2007 11:24:26 -0500 Delivered-To: CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU Received: (qmail 3889 invoked from network); 8 Mar 2007 16:24:26 -0000 Received: from mailscan1.acsu.buffalo.edu (128.205.6.133) by listserv.buffalo.edu with SMTP; 8 Mar 2007 16:24:26 -0000 Received: (qmail 17586 invoked from network); 8 Mar 2007 16:24:26 -0000 Received: from pollux.cse.buffalo.edu (128.205.35.2) by smtp3.acsu.buffalo.edu with SMTP; 8 Mar 2007 16:24:26 -0000 Received: from pollux.cse.buffalo.edu (ag33@localhost [127.0.0.1]) by pollux.cse.buffalo.edu (8.12.10+Sun/8.12.9) with ESMTP id l28GOPKF005971 for ; Thu, 8 Mar 2007 11:24:25 -0500 (EST) Received: (from ag33@localhost) by pollux.cse.buffalo.edu (8.12.10+Sun/8.12.8/Submit) id l28GOPaR005970; Thu, 8 Mar 2007 11:24:25 -0500 (EST) MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-UB-Relay: (pollux.cse.buffalo.edu) X-PM-EL-Spam-Prob: : 7% Message-ID: Date: Thu, 8 Mar 2007 11:24:25 -0500 Reply-To: Albert Goldfain Sender: "Philosophy of Computer Science, Spring 2007" From: Albert Goldfain Subject: Premise 1d in position paper #3 To: CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU Precedence: list List-Help: , List-Unsubscribe: List-Subscribe: List-Owner: List-Archive: X-UB-Relay: (pollux.cse.buffalo.edu) X-DCC-Buffalo.EDU-Metrics: castor.cse.Buffalo.EDU 1029; Body=0 Fuz1=0 Fuz2=0 X-Spam-Status: No, score=-2.6 required=5.0 tests=AWL,BAYES_00 autolearn=unavailable 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/2777/Thu Mar 8 08:40:01 2007 on ares.cse.buffalo.edu X-Virus-Status: Clean Status: R Content-Length: 1702 Part of Knuth's characterization of an algorithm includes: d. "Output. An algorithm has *ONE* or more outputs..." contrast this with 1c "*ZERO* or more inputs. This is not a typo...and most likely not a mental slip by someone as precise as Knuth. There are several modern high-level languages that will allow you to return nothing from a function. E.g., consider the C function: int store-and-return(int x) { int i; i=x; return; } In some sense, there are no "outputs" from this function, yet it is still somehow an algorithm (if any of you know pascal, there was a distinction between procedures and functions...some other languages call procedures subroutines, but the point is, these are not functions in the mathematical sense of ordered *PAIRS*). In Lisp, which may have been more dominant when Knuth wrote, every function *had* to return at least one value. We can, however, re-interpret the "output" of an algorithm so that it is not always the return value of a function. So in store-and-return, perhaps the memory location of the local variable i that gets the "output" of the algorithm. In a program like C's hello world main(){ printf("Hello World\n"); return; } perhaps it is the screen that you are printing to that gets the "output" of the algorithm. Notice also, that if you think of the store-and-return function as a "black-box", there would be no way to tell that it was doing anything. Behaviorally, you would hand an input into the black-box and observe nothing else! It may be that Knuth wants to exclude behaviorally unobservable algorithms. Bottom line: the "one or more" from premise 1d should not trip you up from analyzing the rest of the argument. Albert