From owner-cse584-sp07-list@LISTSERV.BUFFALO.EDU Tue Mar 20 21:26:04 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 l2L1Q4pc015356 for ; Tue, 20 Mar 2007 21:26:04 -0400 (EDT) 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 l2L1Q2tJ090689 for ; Tue, 20 Mar 2007 21:26:02 -0400 (EDT) Received: (qmail 424 invoked from network); 21 Mar 2007 01:26:02 -0000 Received: from mailscan3.acsu.buffalo.edu (128.205.6.135) by front2.acsu.buffalo.edu with SMTP; 21 Mar 2007 01:26:02 -0000 Received: (qmail 399 invoked from network); 21 Mar 2007 01:26:02 -0000 Received: from deliverance.acsu.buffalo.edu (128.205.7.57) by front2.acsu.buffalo.edu with SMTP; 21 Mar 2007 01:26:02 -0000 Received: (qmail 3555 invoked from network); 21 Mar 2007 01:26:00 -0000 Received: from listserv.buffalo.edu (128.205.7.35) by deliverance.acsu.buffalo.edu with SMTP; 21 Mar 2007 01:26:00 -0000 Received: by LISTSERV.BUFFALO.EDU (LISTSERV-TCP/IP release 14.5) with spool id 3977065 for CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU; Tue, 20 Mar 2007 21:26:00 -0400 Delivered-To: cse584-sp07-list@listserv.buffalo.edu Received: (qmail 18167 invoked from network); 21 Mar 2007 01:25:59 -0000 Received: from mailscan1.acsu.buffalo.edu (128.205.6.133) by listserv.buffalo.edu with SMTP; 21 Mar 2007 01:25:59 -0000 Received: (qmail 24333 invoked from network); 21 Mar 2007 01:25:59 -0000 Received: from castor.cse.buffalo.edu (128.205.32.14) by smtp1.acsu.buffalo.edu with SMTP; 21 Mar 2007 01:25:59 -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 l2L1PwIW015353 for ; Tue, 20 Mar 2007 21:25:58 -0400 (EDT) Received: (from rapaport@localhost) by castor.cse.Buffalo.EDU (8.13.6/8.12.9/Submit) id l2L1Pw6Y015352 for cse584-sp07-list@listserv.buffalo.edu; Tue, 20 Mar 2007 21:25:58 -0400 (EDT) X-UB-Relay: (castor.cse.buffalo.edu) X-PM-EL-Spam-Prob: : 7% Message-ID: <200703210125.l2L1Pw6Y015352@castor.cse.Buffalo.EDU> Date: Tue, 20 Mar 2007 21:25:58 -0400 Reply-To: "William J. Rapaport" Sender: "Philosophy of Computer Science, Spring 2007" From: "William J. Rapaport" Subject: BUSY BEAVERS: ANOTHER NON-COMPUTABLE PROBLEM 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/2883/Tue Mar 20 18:49:34 2007 on ares.cse.buffalo.edu X-Virus-Status: Clean Status: R Content-Length: 266 Some of you have inquired about other non-computable functions, including a famous one called "the busy beaver". Here's a website that explains it and gives some citations for further reading: Busy Beaver Turing Machine http://grail.cba.csuohio.edu/~somos/bb.html