From owner-cse584-sp07-list@LISTSERV.BUFFALO.EDU Wed Feb 21 19:24:19 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 l1M0OJH1015900 for ; Wed, 21 Feb 2007 19:24:19 -0500 (EST) Received: from front1.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 l1M0OCVZ080877 for ; Wed, 21 Feb 2007 19:24:12 -0500 (EST) Received: (qmail 14889 invoked from network); 22 Feb 2007 00:24:11 -0000 Received: from mailscan5.acsu.buffalo.edu (128.205.6.137) by front1.acsu.buffalo.edu with SMTP; 22 Feb 2007 00:24:11 -0000 Received: (qmail 10398 invoked from network); 22 Feb 2007 00:24:11 -0000 Received: from deliverance.acsu.buffalo.edu (128.205.7.57) by front2.acsu.buffalo.edu with SMTP; 22 Feb 2007 00:24:11 -0000 Received: (qmail 9011 invoked from network); 22 Feb 2007 00:24:08 -0000 Received: from listserv.buffalo.edu (128.205.7.35) by deliverance.acsu.buffalo.edu with SMTP; 22 Feb 2007 00:24:08 -0000 Received: by LISTSERV.BUFFALO.EDU (LISTSERV-TCP/IP release 14.5) with spool id 3464644 for CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU; Wed, 21 Feb 2007 19:24:08 -0500 Delivered-To: CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU Received: (qmail 16892 invoked from network); 22 Feb 2007 00:24:07 -0000 Received: from mailscan4.acsu.buffalo.edu (128.205.6.136) by listserv.buffalo.edu with SMTP; 22 Feb 2007 00:24:07 -0000 Received: (qmail 29293 invoked from network); 22 Feb 2007 00:24:07 -0000 Received: from hadar.cse.buffalo.edu (128.205.32.1) by smtp3.acsu.buffalo.edu with SMTP; 22 Feb 2007 00:24:07 -0000 Received: from hadar.cse.Buffalo.EDU (ag33@localhost [127.0.0.1]) by hadar.cse.Buffalo.EDU (8.13.6/8.12.10) with ESMTP id l1M0O6O4006998 for ; Wed, 21 Feb 2007 19:24:06 -0500 (EST) Received: (from ag33@localhost) by hadar.cse.Buffalo.EDU (8.13.6/8.12.9/Submit) id l1M0O6Rq006997; Wed, 21 Feb 2007 19:24:06 -0500 (EST) MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-UB-Relay: (hadar.cse.buffalo.edu) X-PM-EL-Spam-Prob: : 7% Message-ID: Date: Wed, 21 Feb 2007 19:24:06 -0500 Reply-To: Albert Goldfain Sender: "Philosophy of Computer Science, Spring 2007" From: Albert Goldfain Subject: Conway's Game of Life as a model of computation To: CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU Precedence: list List-Help: , List-Unsubscribe: List-Subscribe: List-Owner: List-Archive: X-UB-Relay: (hadar.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/2623/Wed Feb 21 16:50:55 2007 on ares.cse.buffalo.edu X-Virus-Status: Clean Status: R Content-Length: 2317 Consider the following arguments: Argument #1 ----------- P1. A Turing Machine (TM) is a model of computation based on what a single human (i.e., a clerk) does. P2. Finite automata (FA) and push down automata (PDA) are models of computation that recognize regular languages and context free languages respectively. P3. Recognizing strings in a languages is also something individual humans do. C1. Thus TMs, FAs, and PDAs (cse396 formalisms :)) are all models of computation based on the abilities of individuals. Argument #2 ----------- Conway's "Game of Life" (GOL) is a cellular automata model (albeit a very simplistic one) of a society (if you missed recitation this week, see http://en.wikipedia.org/wiki/Conway_Game_of_Life for the rules of this game): P1. Conway's "Game of Life" can be implemented in Java. P2. Any Java program is reducible to a TM program. C1. Thus, Conway's "Game of Life" is TM-computable Argument #3 ----------- ???P1???. Conway's GOL can be thought of as a model of computation. P2. GOL is a model of the abilities of a society. P3. The abilities of a society exceed those of an individual. C1. The abilities of a model of computation based on a society will exceed the abilities of a model based on the abilities of an individual. ???C2???. It is not the case that every TM program could be translated to a GOL "computation". Probably some missing premises in those because I wrote them hastily :-\ Anyway, these may be interesting to think about as we get to the question "Is everything a computer". To my knowledge, no one has claimed that GOL is a model of computation (although I know people like Wolfram (from recommended readings) have proposed that *cellular automata* are models of computation). Think about what it would mean to "compute" with GOL: Given an integer input (b/c remember everything can be encoded :)), how would should this integer be represented as live cells on an initial grid? How might "stable" structures (remember a 2x2 grid has 3 neighbors each) be used as "memory"? How would an output be represented? The two recitations seemed to disagree whether or not TM programs could be reduced to GOL computations (once we define that) :-) Unfortunately, this is an open question that you won't get any additional course credit for solving :) Albert From owner-cse584-sp07-list@LISTSERV.BUFFALO.EDU Wed Feb 21 20:05:14 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 l1M15E1q016794 for ; Wed, 21 Feb 2007 20:05:14 -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 l1M15AeT082358 for ; Wed, 21 Feb 2007 20:05:10 -0500 (EST) Received: (qmail 24468 invoked from network); 22 Feb 2007 01:05:10 -0000 Received: from mailscan3.acsu.buffalo.edu (128.205.6.135) by front3.acsu.buffalo.edu with SMTP; 22 Feb 2007 01:05:10 -0000 Received: (qmail 24445 invoked from network); 22 Feb 2007 01:05:10 -0000 Received: from deliverance.acsu.buffalo.edu (128.205.7.57) by front3.acsu.buffalo.edu with SMTP; 22 Feb 2007 01:05:10 -0000 Received: (qmail 22621 invoked from network); 22 Feb 2007 01:05:01 -0000 Received: from listserv.buffalo.edu (128.205.7.35) by deliverance.acsu.buffalo.edu with SMTP; 22 Feb 2007 01:05:01 -0000 Received: by LISTSERV.BUFFALO.EDU (LISTSERV-TCP/IP release 14.5) with spool id 3465253 for CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU; Wed, 21 Feb 2007 20:05:01 -0500 Delivered-To: CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU Received: (qmail 6754 invoked from network); 22 Feb 2007 01:05:01 -0000 Received: from mailscan4.acsu.buffalo.edu (128.205.6.136) by listserv.buffalo.edu with SMTP; 22 Feb 2007 01:05:01 -0000 Received: (qmail 16638 invoked from network); 22 Feb 2007 01:05:00 -0000 Received: from castor.cse.buffalo.edu (128.205.32.14) by smtp2.acsu.buffalo.edu with SMTP; 22 Feb 2007 01:05:00 -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 l1M14xse016747 for ; Wed, 21 Feb 2007 20:04:59 -0500 (EST) Received: (from rapaport@localhost) by castor.cse.Buffalo.EDU (8.13.6/8.12.9/Submit) id l1M14x7Z016746 for CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU; Wed, 21 Feb 2007 20:04:59 -0500 (EST) X-UB-Relay: (castor.cse.buffalo.edu) X-PM-EL-Spam-Prob: : 7% Message-ID: <200702220104.l1M14x7Z016746@castor.cse.Buffalo.EDU> Date: Wed, 21 Feb 2007 20:04:59 -0500 Reply-To: "William J. Rapaport" Sender: "Philosophy of Computer Science, Spring 2007" From: "William J. Rapaport" Subject: Re: Conway's Game of Life as a model of computation 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.5 required=5.0 tests=AWL,BAYES_00 autolearn=ham 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/2623/Wed Feb 21 16:50:55 2007 on ares.cse.buffalo.edu X-Virus-Status: Clean Status: R Content-Length: 619 Albert wrote: | ... To my knowledge, no one has | claimed that GOL is a model of computation (although I know people | like Wolfram (from recommended readings) have proposed that *cellular | automata* are models of computation). First, GOL is a cellular automaton. BTW, the standard reference on CAs is: Burks, Arthur W. (ed.) (1970), Essays on cellular automata (Urbana, IL: University of Illinois Press SEL QA267.5 .S4 B87 1970 Burks was one of the people involved in the construction of ENIAC and EDVAC. Second, do a Google search on: "game of life" "turing machine" for some interesting results :-) From ag33@cse.Buffalo.EDU Wed Feb 21 21:46:06 2007 Received: from hadar.cse.Buffalo.EDU (root@hadar.cse.Buffalo.EDU [128.205.32.1]) by castor.cse.Buffalo.EDU (8.13.6/8.12.10) with ESMTP id l1M2k6Iq019286 for ; Wed, 21 Feb 2007 21:46:06 -0500 (EST) Received: from pollux.cse.buffalo.edu (root@pollux.cse.Buffalo.EDU [128.205.35.2]) by hadar.cse.Buffalo.EDU (8.13.6/8.12.10) with ESMTP id l1M2k5fH015313 for ; Wed, 21 Feb 2007 21:46:05 -0500 (EST) 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 l1M2k5xX022174; Wed, 21 Feb 2007 21:46:05 -0500 (EST) Received: (from ag33@localhost) by pollux.cse.buffalo.edu (8.12.10+Sun/8.12.8/Submit) id l1M2k55o022162; Wed, 21 Feb 2007 21:46:05 -0500 (EST) Date: Wed, 21 Feb 2007 21:46:05 -0500 (EST) From: Albert Goldfain To: "William J. Rapaport" cc: CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU Subject: Re: Conway's Game of Life as a model of computation In-Reply-To: <200702220104.l1M14x7Z016746@castor.cse.Buffalo.EDU> Message-ID: References: <200702220104.l1M14x7Z016746@castor.cse.Buffalo.EDU> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-DCC-Buffalo.EDU-Metrics: castor.cse.Buffalo.EDU 1335; Body=0 Fuz1=0 Fuz2=0 Status: R Content-Length: 1468 William J. Rapaport wrote: > Albert wrote: > | ... To my knowledge, no one has > | claimed that GOL is a model of computation (although I know people > | like Wolfram (from recommended readings) have proposed that *cellular > | automata* are models of computation). > > First, GOL is a cellular automaton. BTW, the standard reference on CAs > is: My mistake...what I was trying to get across was that GOL (like a TM) has a fixed set of "verbs" given by the generation update rules: 1. Any live cell with fewer than two live neighbours dies, as if by loneliness. 2. Any live cell with more than three live neighbours dies, as if by overcrowding. 3. Any live cell with two or three live neighbours lives, unchanged, to the next generation. 4. Any dead cell with exactly three live neighbours comes to life. Other cellular automatons may have different "verbs" (although I am not to familiar with them...this is the only one I know :( ) > Burks, Arthur W. (ed.) (1970), > Essays on cellular automata > (Urbana, IL: University of Illinois Press > SEL QA267.5 .S4 B87 1970 > > Burks was one of the people involved in the construction of ENIAC and EDVAC. > > > Second, do a Google search on: > > "game of life" "turing machine" > > for some interesting results :-) > Yikes! Someone did it: http://www.cs.ualberta.ca/~bulitko/F02/papers/tm_words.pdf Monday section: Cease all refutation attempts. Wednesday section: We've been scooped :-) Albert From ag33@cse.Buffalo.EDU Wed Feb 21 21:47:34 2007 Received: from hadar.cse.Buffalo.EDU (root@hadar.cse.Buffalo.EDU [128.205.32.1]) by castor.cse.Buffalo.EDU (8.13.6/8.12.10) with ESMTP id l1M2lYxB019345 for ; Wed, 21 Feb 2007 21:47:34 -0500 (EST) Received: from pollux.cse.buffalo.edu (root@pollux.cse.Buffalo.EDU [128.205.35.2]) by hadar.cse.Buffalo.EDU (8.13.6/8.12.10) with ESMTP id l1M2lYoA015484 for ; Wed, 21 Feb 2007 21:47:34 -0500 (EST) 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 l1M2lXxX001294; Wed, 21 Feb 2007 21:47:33 -0500 (EST) Received: (from ag33@localhost) by pollux.cse.buffalo.edu (8.12.10+Sun/8.12.8/Submit) id l1M2lXWO001274; Wed, 21 Feb 2007 21:47:33 -0500 (EST) Date: Wed, 21 Feb 2007 21:47:33 -0500 (EST) From: Albert Goldfain To: "William J. Rapaport" cc: CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU Subject: Re: Conway's Game of Life as a model of computation In-Reply-To: Message-ID: References: <200702220104.l1M14x7Z016746@castor.cse.Buffalo.EDU> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-DCC-Buffalo.EDU-Metrics: castor.cse.Buffalo.EDU 1335; Body=0 Fuz1=0 Status: R Content-Length: 76 ...also don't spell like me :) singular automaton plural automata Albert