From owner-cse584-sp07-list@LISTSERV.BUFFALO.EDU Tue Feb 27 13:07:21 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 l1RI7Kt4005690 for ; Tue, 27 Feb 2007 13:07:20 -0500 (EST) Received: from front3.acsu.buffalo.edu (upfront.acsu.buffalo.edu [128.205.4.140]) by ares.cse.buffalo.edu (8.13.6/8.13.6) with SMTP id l1RI7EOp086968 for ; Tue, 27 Feb 2007 13:07:14 -0500 (EST) Received: (qmail 6256 invoked from network); 27 Feb 2007 18:07:14 -0000 Received: from mailscan4.acsu.buffalo.edu (128.205.6.136) by front3.acsu.buffalo.edu with SMTP; 27 Feb 2007 18:07:14 -0000 Received: (qmail 6204 invoked from network); 27 Feb 2007 18:07:13 -0000 Received: from deliverance.acsu.buffalo.edu (128.205.7.57) by front3.acsu.buffalo.edu with SMTP; 27 Feb 2007 18:07:13 -0000 Received: (qmail 15851 invoked from network); 27 Feb 2007 18:07:08 -0000 Received: from listserv.buffalo.edu (128.205.7.35) by deliverance.acsu.buffalo.edu with SMTP; 27 Feb 2007 18:07:08 -0000 Received: by LISTSERV.BUFFALO.EDU (LISTSERV-TCP/IP release 14.5) with spool id 3554751 for CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU; Tue, 27 Feb 2007 13:07:08 -0500 Delivered-To: CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU Received: (qmail 10266 invoked from network); 27 Feb 2007 18:07:08 -0000 Received: from mailscan3.acsu.buffalo.edu (128.205.6.135) by listserv.buffalo.edu with SMTP; 27 Feb 2007 18:07:08 -0000 Received: (qmail 20961 invoked from network); 27 Feb 2007 18:07:07 -0000 Received: from pollux.cse.buffalo.edu (128.205.35.2) by smtp4.acsu.buffalo.edu with SMTP; 27 Feb 2007 18:07:07 -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 l1RI77xX028795 for ; Tue, 27 Feb 2007 13:07:07 -0500 (EST) Received: (from ag33@localhost) by pollux.cse.buffalo.edu (8.12.10+Sun/8.12.8/Submit) id l1RI77SI028793; Tue, 27 Feb 2007 13:07:07 -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: Tue, 27 Feb 2007 13:07:06 -0500 Reply-To: Albert Goldfain Sender: "Philosophy of Computer Science, Spring 2007" From: Albert Goldfain Subject: INFINITE vs ARBITRARILY LARGE 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 1336; 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/2665/Tue Feb 27 11:26:03 2007 on ares.cse.buffalo.edu X-Virus-Status: Clean Status: RO Content-Length: 2031 There is a subtle but important difference between the term 'infinite' and the term 'arbitrarily large'. To say that a (U)TM has an 'infinite tape' would suggest that it begins any given computation with infinite memory. Several people might reject that such a model could be implemented by my Dell laptop because it has only gigabytes of memory OR my brain because it has [some large N] many neurons. To say that a (U)TM has an 'arbitrarily large tape' suggests (as Dr. Rapaport has mentioned) that at any given point in a computation we could always go to the store and add more squares to our *finite* tape to make a larger *finite* tape. There is some TM-computable function that my Dell laptop cannot compute because it requires terabytes of memory and not just gigabytes. If you then augmented my laptop with terabytes of memory then it could not compute a function requiring petabytes of data. But assuming that you could always add more memory is kind of like saying a UTM is a model of the (perpetually changing) latest and greatest laptop :) Notice that the human brain case is very similar. Suppose that you could store more memory by taking one of those memory fitness courses (just google "improve your memory" and please don't take this post as an endorsement to sign up for any of these...they are probably scams :)) OR augment your memory by using external resources (see extended cognition posts). The bottom line is, a close reading of Turing (1936) would indicate that a (U)TM has an "arbitrarily large" tape not an "infinite" tape. At any given moment of a computation there are a finite number of symbols on a finite number of squares. This is the case even when a TM is computing the digits of pi! Note that a (U)TM will never *finish* computing pi, but that fact doesn't make pi uncomputable (remember, Turing was originally interested in the computable *numbers*). A (U)TM that computes pi knows exactly how to produce each next digit of pi...it just has to make very frequent trips to the store.