From owner-cse584-sp07-list@LISTSERV.BUFFALO.EDU Fri Mar 9 11:12:52 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 l29GCqWo002632 for ; Fri, 9 Mar 2007 11:12:52 -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 l29GClps053848 for ; Fri, 9 Mar 2007 11:12:47 -0500 (EST) Received: (qmail 26018 invoked from network); 9 Mar 2007 16:12:47 -0000 Received: from mailscan7.acsu.buffalo.edu (128.205.6.158) by front2.acsu.buffalo.edu with SMTP; 9 Mar 2007 16:12:47 -0000 Received: (qmail 26003 invoked from network); 9 Mar 2007 16:12:46 -0000 Received: from deliverance.acsu.buffalo.edu (128.205.7.57) by front2.acsu.buffalo.edu with SMTP; 9 Mar 2007 16:12:46 -0000 Received: (qmail 22148 invoked from network); 9 Mar 2007 16:12:31 -0000 Received: from listserv.buffalo.edu (128.205.7.35) by deliverance.acsu.buffalo.edu with SMTP; 9 Mar 2007 16:12:31 -0000 Received: by LISTSERV.BUFFALO.EDU (LISTSERV-TCP/IP release 14.5) with spool id 3731897 for CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU; Fri, 9 Mar 2007 11:12:31 -0500 Delivered-To: cse584-sp07-list@listserv.buffalo.edu Received: (qmail 29978 invoked from network); 9 Mar 2007 16:12:31 -0000 Received: from mailscan6.acsu.buffalo.edu (128.205.7.95) by listserv.buffalo.edu with SMTP; 9 Mar 2007 16:12:31 -0000 Received: (qmail 7825 invoked from network); 9 Mar 2007 16:12:31 -0000 Received: from castor.cse.buffalo.edu (128.205.32.14) by smtp2.acsu.buffalo.edu with SMTP; 9 Mar 2007 16:12:31 -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 l29GCU0k002626 for ; Fri, 9 Mar 2007 11:12:30 -0500 (EST) Received: (from rapaport@localhost) by castor.cse.Buffalo.EDU (8.13.6/8.12.9/Submit) id l29GCUmI002625 for cse584-sp07-list@listserv.buffalo.edu; Fri, 9 Mar 2007 11:12:30 -0500 (EST) X-UB-Relay: (castor.cse.buffalo.edu) X-PM-EL-Spam-Prob: : 7% Message-ID: <200703091612.l29GCUmI002625@castor.cse.Buffalo.EDU> Date: Fri, 9 Mar 2007 11:12:30 -0500 Reply-To: "William J. Rapaport" Sender: "Philosophy of Computer Science, Spring 2007" From: "William J. Rapaport" Subject: HYPERCOMPUTATION AND UNNAMEABLE REAL NUMBERS 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 1336; 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/2786/Fri Mar 9 07:35:44 2007 on ares.cse.buffalo.edu X-Virus-Status: Clean Status: R Content-Length: 793 ------------------------------------------------------------------------ Subject: HYPERCOMPUTATION AND UNNAMEABLE REAL NUMBERS ------------------------------------------------------------------------ In class today, we discussed the similarities of the argument that an interaction machine can be simulated by a finite number of TMs to the argument that there are an infinite number of real numbers, hence that there are unnameable reals. If you're interested in following up on some of these ideas, here's an interesting and even readable(!) paper by a well-known theoretician of computation: Chaitin, Gregory (2006), "How Real Are Real Numbers?", International Journal of Bifurcation and Chaos PDF: http://www.cs.auckland.ac.nz/CDMTCS/chaitin/olympia.pdf html: http://tinyurl.com/2eh7tj From owner-cse584-sp07-list@LISTSERV.BUFFALO.EDU Fri Mar 9 13:38:45 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 l29Icjkg008668 for ; Fri, 9 Mar 2007 13:38:45 -0500 (EST) Received: from front3.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 l29IcdBZ067905 for ; Fri, 9 Mar 2007 13:38:39 -0500 (EST) Received: (qmail 9706 invoked from network); 9 Mar 2007 18:38:39 -0000 Received: from mailscan3.acsu.buffalo.edu (128.205.6.135) by front3.acsu.buffalo.edu with SMTP; 9 Mar 2007 18:38:39 -0000 Received: (qmail 24386 invoked from network); 9 Mar 2007 18:38:38 -0000 Received: from deliverance.acsu.buffalo.edu (128.205.7.57) by front1.acsu.buffalo.edu with SMTP; 9 Mar 2007 18:38:38 -0000 Received: (qmail 3189 invoked from network); 9 Mar 2007 18:38:37 -0000 Received: from listserv.buffalo.edu (128.205.7.35) by deliverance.acsu.buffalo.edu with SMTP; 9 Mar 2007 18:38:37 -0000 Received: by LISTSERV.BUFFALO.EDU (LISTSERV-TCP/IP release 14.5) with spool id 3735414 for CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU; Fri, 9 Mar 2007 13:38:37 -0500 Delivered-To: cse584-sp07-list@listserv.buffalo.edu Received: (qmail 17971 invoked from network); 9 Mar 2007 18:38:37 -0000 Received: from mailscan5.acsu.buffalo.edu (128.205.6.137) by listserv.buffalo.edu with SMTP; 9 Mar 2007 18:38:37 -0000 Received: (qmail 29741 invoked from network); 9 Mar 2007 18:38:36 -0000 Received: from castor.cse.buffalo.edu (128.205.32.14) by smtp4.acsu.buffalo.edu with SMTP; 9 Mar 2007 18:38:36 -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 l29IcaQK008659 for ; Fri, 9 Mar 2007 13:38:36 -0500 (EST) Received: (from rapaport@localhost) by castor.cse.Buffalo.EDU (8.13.6/8.12.9/Submit) id l29IcaSN008658 for cse584-sp07-list@listserv.buffalo.edu; Fri, 9 Mar 2007 13:38:36 -0500 (EST) X-UB-Relay: (castor.cse.buffalo.edu) X-PM-EL-Spam-Prob: : 7% Message-ID: <200703091838.l29IcaSN008658@castor.cse.Buffalo.EDU> Date: Fri, 9 Mar 2007 13:38:36 -0500 Reply-To: "William J. Rapaport" Sender: "Philosophy of Computer Science, Spring 2007" From: "William J. Rapaport" Subject: UNCOMPUTABLE REAL NUMBERS MAY BE HAZARDOUS TO YOUR HEALTH! 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 1029; 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/2786/Fri Mar 9 07:35:44 2007 on ares.cse.buffalo.edu X-Virus-Status: Clean Status: R Content-Length: 1616 ------------------------------------------------------------------------ Subject: UNCOMPUTABLE REAL NUMBERS MAY BE HAZARDOUS TO YOUR HEALTH! ------------------------------------------------------------------------ A student writes: | Section 3.1 gives an algorithm for finding an uncomputable real | number, but we could code up the algorithm, which itself would then be | part of the enumeration that it takes as input, and whatever digit it | output at its kth position, it would have to output something | different. In other words, it would have to predict its own output, | and then change it! | | I don't know what that means, but it made my head explode. | | | On 3/9/07, William J. Rapaport wrote: | > ------------------------------------------------------------------------ | > Subject: HYPERCOMPUTATION AND UNNAMEABLE REAL NUMBERS | > ------------------------------------------------------------------------ | > | > In class today, we discussed the similarities of the argument that an | > interaction machine can be simulated by a finite number of TMs to the | > argument that there are an infinite number of real numbers, hence that | > there are unnameable reals. | > | > If you're interested in following up on some of these ideas, here's an | > interesting and even readable(!) paper by a well-known theoretician of | > computation: | > | > Chaitin, Gregory (2006), | > "How Real Are Real Numbers?", | > International Journal of Bifurcation and Chaos | > | > PDF: http://www.cs.auckland.ac.nz/CDMTCS/chaitin/olympia.pdf | > html: http://tinyurl.com/2eh7tj | > |