From mimsy!haven!uvaarpa!mcnc!rti!talos!mckenney Fri Oct 7 02:26:05 EDT 1988 Article 93 of comp.theory.cell-automata: Path: mimsy!haven!uvaarpa!mcnc!rti!talos!mckenney >From: mckenney@talos.UUCP ( APL Consultant) Newsgroups: comp.theory.cell-automata Subject: Re: CAM-6 (Systems Concepts) Keywords: CAM-6, Toffoli, Margolus, hardware, Systems Concepts Message-ID: <313@talos.UUCP> Date: 25 Sep 88 03:31:04 GMT Reply-To: mckenney@talos.UUCP (Frank McKenney - APL Consultant) Distribution: na Organization: McKenney Associates, Richmond, Virginia Lines: 78 >Article 77 of comp.theory.cell-automata: >Path: talos!rti!mcnc!gatech!ukma!husc6!linus!philabs!sbcs!dji >From: dji@sbcs.sunysb.edu (the dirty vicar) >Subject: CAM-6 (Systems Concepts) >Date: 19 Sep 88 16:14:39 GMT >Organization: State University of New York at Stony Brook > >Could someone please fill me in on the CAM-6 board from Systems Concepts >as described in CELLULAR AUTOMATA MACHINES by Toffoli and Margolus?? >Specifically, how much does it cost, and what is the address/phone of >the company?? I imagine posting would be best since I'm probably not >the only person interested. Thanks. >-- >Dave Iannucci Computer Science, SUNY at Stony Brook, Long Island, New York >************* UUCP: {allegra, philabs, }!sbcs.sunysb.edu!dji >* 4 months! * BITNET: dji%sbcs.sunysb.edu@SBCCVM.BITNET >************* Internet or CSnet: dji@sbcs.sunysb.edu The book didn't give you much to go on, did it? I finally tracked Systems Concepts down, and asked them to send me any information they had on the CAM-6. What came was a one-page technical summary and price list, along with a cover letter from a gentleman named Oliver Graves (dated 30 June 88). Prices were as follows: CAM-6 Hardware and technical manual $1,400.00 CAM-6 Software, for one computer, and user's manual $ 150.00 Package price for hardware, software, programming, and user's manual $1,500.00 Book, "Cellular Automata Machines" $ 30.00 Sales Tax applied for California residents. The CAM-6 board is described as fitting into an IBM PC, PC/XT, PC/AT, or compatible computer. Nothing about speed limitations is mentioned, but if I were thinking about adding it to a 20MHz '386 machine, I might do some further checking before throwing my money at them. It does have its own video connector, with a pass-through when the board is not operational. The Tech sheet says it will drive an "IBM standard color monitor, or compatible (or enhanced monitor in non-enhanced mode)". Video in/out are via a "standard" 9-pin plug and socket (one presumes a DB-9 connector). Power is 1.5 amps at 5V (7.5 watts). For further information, get in touch with either Oliver Graves or Steve McClure at: Systems Concepts 55 Francisco Street San Francisco, California 94133 (415) 984-1000 It looks like a wonderful instrument for research into cellular automata, but a little beyond my current budget limit for AI projects for this year. Fortunately, most of the programs in the book look like they wouldn't be too hard [translation: too hard for the mythical "someone"] to implement in C. Hopes this helps. For those listening in who haven't read the book ("Cellular Automata Machines" by Toffoli and Margolis, MIT Press), I highly recommend borrowing a copy from someone. Frank McKenney ---------------------------------------------------------------------- "Please summarize responses to the appropriate newsgroup" Frank McKenney, President | {uunet,rti}!talos!mckenney | McKenney Associates | guest account - access | 3464 Northview Place | provided as a courtesy by | Richmond, Virginia 23225 | Philip Morris USA | USA (804) 320-4887 ---------------------------------------------------------------------- From mimsy!tank!uwvax!rutgers!mailrus!cornell!batcomputer!itsgw!rpi!rpics!hiebeler Sat Dec 24 15:09:17 EST 1988 Article 130 of comp.theory.cell-automata: Path: mimsy!tank!uwvax!rutgers!mailrus!cornell!batcomputer!itsgw!rpi!rpics!hiebeler >From: hiebeler@rpics (Dave Hiebeler) Newsgroups: comp.theory.cell-automata Subject: Re: Brain and Trip Message-ID: <39@rpi.edu> Date: 24 Dec 88 04:54:21 GMT References: <4040@cheviot.newcastle.ac.uk> Sender: usenet@rpi.edu Reply-To: hiebeler@turing.cs.rpi.edu (Dave Hiebeler) Organization: RPI CS Dept. Lines: 24 In article <4040@cheviot.newcastle.ac.uk> M.J.Elphick@newcastle.ac.uk (Michael Elphick) writes: > > " John Conway's Life [obviously!] ... and Brian Silverman's > recently discovered Brain. > [mention of an algorithm which merges Life and Brain] > ...which he calls Trip. This microworld > spontaneously segregates itself into 'land' areas where Life's > rules apply, and 'sea' areas where the rules are those of Brain." > > Does anyone in this newsgroup (and/or those named) have a concise > specification of these last two models? Sounds very interesting. I don't have any info on it, and haven't seen the article you refer to; but I'm wondering about that Brain thing. Is that the same Brain algorithm that's given in Toffoli's & Margolus's _Cellular Automata Machines_ book? I too would be very interested in hearing more about this strange merge of Life and Brain (hm.. I think that would sound awfully strange out of context :-) ). ---- Dave Hiebeler Internet: hiebeler@cs.rpi.edu (preferred address) R.D. Box 225A userfrzk%mts@itsgw.rpi.edu Chatham, NY 12037 Bitnet: userfrzk@rpitsmts.bitnet "xue zai xao" "...I can't remember what I was going to say..." From mimsy!tank!uxc!csd4.milw.wisc.edu!mailrus!cornell!batcomputer!rpi!rpics!hiebeler Mon Feb 20 16:50:42 EST 1989 Article 154 of comp.theory.cell-automata: Path: mimsy!tank!uxc!csd4.milw.wisc.edu!mailrus!cornell!batcomputer!rpi!rpics!hiebeler >From: hiebeler@rpics (Dave Hiebeler) Newsgroups: comp.theory.cell-automata Subject: Future Cellular Automata Machines Summary: CAM-8 in a year or 2 perhaps Keywords: cellular automata, CAM, MIT Message-ID: <669@rpi.edu> Date: 20 Feb 89 02:46:19 GMT References: <519@maths.tcd.ie> <668@rpi.edu> Sender: usenet@rpi.edu Reply-To: hiebeler@turing.cs.rpi.edu (Dave Hiebeler) Organization: RPI CS Dept. Lines: 57 Well, I had the pleasure of visiting the Information-Mechanics group at MIT a few days ago. I spoke with Tom Toffoli, Norman Margolus, and Mark Smith there. Perhaps some people would be interested in knowing what they're up to, as far as the next generation of CAM machines goes. Margolus summarized the CAM-8 as it is currently expected to perform: o Between 4 million and 16 million cells (compared to CAM-6's 65536 cells) o 16 bit cells, 16-bit lookup table, as opposed to CAM-6's 4-bit cells and 12-bit lookup table. o Cell-updates should be done 5 or 6 times faster than CAM-6. However, since there are many more cells, the simulation will actually go slower. But CAM-8 is supposed to allow you to use a smaller grid and run much faster, or use the larger grid but run slower, depending on what kind of stuff you are doing. This is a nice feature, because sometimes you want speed, other times you want size. (And of course sometimes you want both. Too bad. :-) ) The price on CAM-8 will be higher than CAM-6. I don't know just how much more, but it will "be under $10,000" I was told. Perhaps a lot less than that. I guess we'll just have to wait and see. Systems Concepts will _NOT_ be producing CAM-8. They caused a disaster with CAM-6 (_HUGE_ delays, many problems, etc.) I don't know who will be producing the machines. They are still considering what machine should serve as the host for the machine. I think Sun workstations would be nice, and they said that was one possibility. But that is not decided yet, so who knows. I doubt we'll see the machine within 2 years, although they will probably have prototypes running by then. I think they said they hoped to have some early versions functional by the end of the year? In general, the CAM-8 will certainly expand some of the limitations of the CAM-6. It's really inconvenient to always play the game of "how few bits can I possibly squeeze this algorithm into" when you want to use CAM-6. The 16-bit lookup-table of CAM-8 will still be somewhat inconvenient, but certainly better then CAM-6. And the larger grid will be nice. The speedup will also be nice, although I never really had any complaints about CAM-6's speed... Disclaimer: all of this is just a bunch of rumors, based upon an afternoon informally chatting with Toffoli and Margolus and Smith. The CAM-8 is still being developed and designed, so who knows how many changes will take place between now & production-time. It could be significantly better than what I've described, or it could be worse. I will certainly be keeping an eye open for the next couple of years to see what comes out of MIT as far as cellular automata machines go. -Dave ---- Dave Hiebeler Internet: hiebeler@cs.rpi.edu (preferred address) R.D. Box 225A userfrzk%mts@itsgw.rpi.edu Chatham, NY 12037 Bitnet: userfrzk@rpitsmts.bitnet "xue zai xao" "Off we go, into the wilds you ponder..." From mimsy!tank!ncar!boulder!sunybcs!rutgers!mit-eddie!mit-amt!mit-caf!grnberg Fri Mar 31 02:03:41 EST 1989 Article 178 of comp.theory.cell-automata: Path: mimsy!tank!ncar!boulder!sunybcs!rutgers!mit-eddie!mit-amt!mit-caf!grnberg >From: grnberg@mit-caf.MIT.EDU (David R. Greenberg) Newsgroups: comp.theory.cell-automata,sci.misc,comp.misc Subject: Re: Are companies interested in cellular automata? Summary: TI seems to be Keywords: automata Message-ID: <2105@mit-caf.MIT.EDU> Date: 29 Mar 89 20:19:02 GMT References: <968@rpi.edu> Reply-To: grnberg@mit-caf.UUCP (David R. Greenberg) Organization: Microsystems Technology Laboratories, MIT Lines: 15 Xref: mimsy comp.theory.cell-automata:178 sci.misc:3602 comp.misc:6076 In article <968@rpi.edu> hiebeler@turing.cs.rpi.edu (Dave Hiebeler) writes: > > I am wondering how far cellular automata has crept into "the >real world", so to speak. Recently, Texas Instruments gave a talk here at MIT. They presented their long term "roadmap" for taking high speed, high density integrated circuits into the future. This roadmap revolves around work they have been doing in quantum effect devices. At the talk, TI claimed that the future of microelectronics was in computing via cellular automata, using tiny quantum wells to implement the individual cells. Very few details were given, however. For instance, TI did not make it very clear how the quantum wells were to communicate with one another. - David From mimsy!haven!ames!uakari.primate.wisc.edu!aplcen!ginosko!gem.mps.ohio-state.edu!rpi!rpi.edu!hiebeler Sat Sep 23 18:53:36 EDT 1989 Article 227 of comp.theory.cell-automata: Path: mimsy!haven!ames!uakari.primate.wisc.edu!aplcen!ginosko!gem.mps.ohio-state.edu!rpi!rpi.edu!hiebeler >From: hiebeler@turing.cs.rpi.edu (Dave Hiebeler) Newsgroups: comp.theory.cell-automata Subject: Re: CAM-6 Message-ID: Date: 19 Sep 89 17:35:13 GMT References: <1989Sep16.030457.12635@psuvax1.cs.psu.edu> Distribution: na Organization: RPI CS Dept, and LANL Center for Nonlinear Studies Lines: 45 In-Reply-To: bralick@psuvax1.cs.psu.edu's message of 16 Sep 89 03:04:57 GMT In article <1989Sep16.030457.12635@psuvax1.cs.psu.edu> bralick@psuvax1.cs.psu.edu (Will Bralick) writes: > Does anybody know whether the CAM-6 is actually being produced? If so > does anybody have any price/availability information? Systems Concepts is in fact producing the CAM-6. The problem is, they are generally VERY slow to deliver. Most of the people I've talked to had to wait between 6-12 months, and my advisor had to wait well over a year for his (fortunately we were able to borrow one from someone else during that waiting period). Systems Concepts also unfortunately does not provide consulting services or much support of the product. However, another company is going to be producing a slightly upgraded version of CAM-6, which will be fully compatible with the previous versions. I know they are still designing the hardware, but I'll bet they can finish designing it and start manufacturing it, and get one to you, before System Concepts would get one to you. The name of the company is Automatrix; here is the address: Automatrix, Inc. P.O. Box 196 Rexford, NY 12148 You can send them a letter asking for info about the product, and the various other services that will be provided (CA software library, CAM consulting service, etc). I have been using CAM-6 for a couple of years now, by the way. I feel I had better add a hefty disclaimer here. I am associated with Automatrix, and indeed own a small part of the company, and will be working full-time for them during the spring of 1990. I do feel that my statements above are not at all exaggerated, and I would have made them even if I were not associated with Automatrix. If you like, I can give you the e-mail address of a couple of other people who have dealt with System Concepts who are not associated with Automatrix, and you can get their opinions. Sometime within a few weeks or so, I will probably post a summary of the products/services Automatrix will be providing, in this newsgroup. -- Dave Hiebeler hiebeler@cs.rpi.edu Computer Science Dept. hiebeler@cardinal.lanl.gov Amos Eaton Bldg. "xue zai shao" -- Huang Ying Ying Rensselaer Polytechnic Institute / Troy, NY 12180-3590 From mimsy!haven!purdue!tut.cis.ohio-state.edu!bloom-beacon!fermat.UUCP!r Sat Oct 28 05:05:59 EDT 1989 Article 242 of comp.theory.cell-automata: Path: mimsy!haven!purdue!tut.cis.ohio-state.edu!bloom-beacon!fermat.UUCP!r >From: r@fermat.UUCP (Richard Schroeppel) Newsgroups: comp.theory.cell-automata Subject: Some recent Life results Message-ID: <8910262210.AA11053@rhmr.com> Date: 26 Oct 89 22:10:38 GMT Sender: daemon@bloom-beacon.MIT.EDU Distribution: inet Organization: The Internet Lines: 46 Some recent new stuff in (Conway) Life: Dean Hickerson at Penn State University wrote an Apple II program to look for oscillators and spaceships. (The guts are in 6502 assembly code.) His program models a small rectangle (say 6*10) for a few time steps (typically 4). The number of layers is one more than the number of time steps. Usually the first and last layers are connected by a mapping relationship. This can be identity, a reflection, rotation, or a shift (for spaceships). He supplies initial values for a few cells and the border, and sets the search code loose, filling in cells and making inferences about adjacent cells, and about successor and predecessor cells. He frequently intervenes in the searches, since the program can only search small configurations to exhaustion. He has turned up some amazing stuff: A set of spaceship construction parts: There are about a dozen parts, typically fitting in an 6*10 rectangle. Each part is period 2 and moves orthogonally at speed c/2. The parts can be strung together to make spaceships of arbitrary width; the minimum is about 25 cells. The spaceships look like a row of threshers harvesting a field of wheat; the thickness in the direction of motion is only about 10 cells. There is a set of rules for the assembly, similar to a finite state machine. [Start with part A on the left. Part A may be followed with either B, D, or I; ...] He also has a period 3, speed c/3 spaceship construction kit. He has turned up a number of new oscillators of periods 2,3,4,5,6, & 8. Robert Wainwright (of Lifeline) has studied Hickerson's oscillators (by hand!) and taken them apart into useful pieces, coming up with a potpourri of new oscillators. An example: ..oooo.. ..o..o.. ooo..ooo o......o o......o ooo..ooo ..o..o.. ..oooo.. Gosper has also found new, improved glider guns & logic gates, probably leading to a smaller proof of Turing Machine equivalence. Rich Schroeppel rcs@la.tis.com From mimsy!haven!aplcen!ginosko!samsung!gem.mps.ohio-state.edu!uwm.edu!mailrus!jarvis.csri.toronto.edu!utgpu!watmath!watdragon!dahlia!sasingh Mon Oct 30 04:46:34 EST 1989 Article 243 of comp.theory.cell-automata: Path: mimsy!haven!aplcen!ginosko!samsung!gem.mps.ohio-state.edu!uwm.edu!mailrus!jarvis.csri.toronto.edu!utgpu!watmath!watdragon!dahlia!sasingh >From: sasingh@dahlia.waterloo.edu (Sanjay Singh) Newsgroups: comp.theory.cell-automata Subject: Navier-Stokes Equations & CA & AutoCAD Keywords: n-s eqns, ca approx of..., acad file structure Message-ID: <17629@watdragon.waterloo.edu> Date: 28 Oct 89 18:07:54 GMT Sender: daemon@watdragon.waterloo.edu Distribution: na Lines: 38 I have just pulled Cellular Automata Machines out of the library, and see an opportunity to challenge a friend who works with finite elements for compressible fluid flow. I don't feel that the FEM is quite right in that it assumes a continuum and proceeds to discretize it. I like the idea of CA better. Firstly, if someone is familiar with the Toffoli and Margolus book, or citations from it to Wolfram's Theory and Applications of CA, regarding approximations of fluid flow, please get back to me, with some sort of psuedo-code that embodies the cellular-automaton laws. Once I have the laws for imcompressible flow down pat, the other problem would be to alter the laws to model compressible flow, since that is what airflow is all about. Air can be compressed, water cannot. So it would seem that a simulation of incompressible flow, which is what is documented in the book, cannot model such phenomenon as a sonic boom, or air patterns at Mach 3. Since I am primarily interested in optimizing bicycle frames, these perhaps could be safely neglected. I would like to proceed from the design phase to the testing phase as smoothly as possible. So to understand how AutoCAD stores its drawings would be a benefit. Software does exist that can take an AutoCAD drawing and proceed to do furthur work. Could anyone kindly refer me to third-party publications which would explain this furthur? The final problem involves the computation of drag. Indeed, how _does_ one actually abstract the results of millions of particles hitting an object into a nice, neat drag coefficient. No books on CA thus far elaborate on this. Perhaps the notion of fractal dimension could be invoked, whereby, the more a particle deviates from a straight line, the higher the fractal dimension of the path of the particle in space, and the more energy required to make the particle move in a straight line. Anyhow, thanks for your consideration in reading this. Any assistance would be greatly appreciated. Sanjay A Singh. sasingh@dahlia.waterloo.edu From mimsy!tank!ncar!mailrus!tut.cis.ohio-state.edu!snorkelwacker!ai-lab!ang Thu Nov 23 02:56:29 EST 1989 Article 267 of comp.theory.cell-automata: Path: mimsy!tank!ncar!mailrus!tut.cis.ohio-state.edu!snorkelwacker!ai-lab!ang >From: ang@wheaties.ai.mit.edu (William S. Ang) Newsgroups: mit.bboard,ne.jobs,misc.jobs.offered,comp.theory.cell-automata Subject: Research programmer needed at MIT Message-ID: <4965@rice-chex.ai.mit.edu> Date: 15 Nov 89 01:48:22 GMT Reply-To: tt@hx.lcs.mit.edu (Tom Toffoli) Distribution: usa Organization: The MIT Lab for Computer Science, Cambridge, MA Lines: 53 Xref: mimsy misc.jobs.offered:4521 comp.theory.cell-automata:267 Position: Research Programmer at the MIT Laboratory for Computer Science, in Cambridge Massachusetts. Description: The Information Mechanics Group is looking for an experienced, imaginative programmer to design and implement control software for the first massively parallel cellular automata machine---which, for a range of simulation tasks of scientific interest, will be by far the fastest computer in the world. This is a small, dedicated group; it is looking for a partner ready for responsibility and involvement, willing to make the group's goals and challenges his/her own. The machine will be controlled by a conventional workstation. Major tasks will include the design of low-level drivers and the development of a higher-level environment for running and analyzing computational experiments (this will involve acquiring a thorough familiarity with cellular automata simulations of physical systems). The early stages of the project may entail participation in software aspects of hardware design, such as VLSI simulation and testing. Qualifications: The most essential technical requirement is a solid and broad-scoped competence in software design using conventional languages (such as C or LISP) and environments (such as UNIX). Experience with real-time programming, parallel computation, physical simulation, language design, and user interface design is desirable. Contact: Please send resumes and any other information you deem appropriate directly to: Tom Toffoli MIT Lab for Computer Science 545 Technology Square Cambridge, MA 02139. or send email to tt@hx.lcs.mit.edu From mimsy!nems!ark1!uakari.primate.wisc.edu!samsung!cs.utexas.edu!mailrus!iuvax!jwmills Fri Dec 22 16:43:32 EST 1989 Article 288 of comp.theory.cell-automata: Path: mimsy!nems!ark1!uakari.primate.wisc.edu!samsung!cs.utexas.edu!mailrus!iuvax!jwmills >From: jwmills@iuvax.cs.indiana.edu (Jonathan Mills) Newsgroups: comp.theory.cell-automata Subject: Cellular Automata Laboratory Message-ID: <31980@iuvax.cs.indiana.edu> Date: 22 Dec 89 10:31:12 GMT Reply-To: jwmills@iuvax.cs.indiana.edu (Jonathan Mills) Organization: Indiana University, Bloomington Lines: 39 EduCalc catalog #46 carried an announcement for what appears to be an IBM PC program, "Cellular Automata Laboratory." designed by Rudy Rucker and implemented by John Walker (who developed AutoCAD). Quoting from the ad: "The latest computer graphics craze -- real-time, self-generating movies! "Use these visible computations to simulate turbulence, heatflow, gas mixing, predator-prey ecologies, eorosion, crystallization -- or just for fun. "...CA Lab offers you a great variety of visual feasts plus applications to predicting biological systems and physical phenomena, as well as the design of massively parallel computers." End quote. Now, has anyone used this program? If so could you post a brief description of features such as PC compatibility, memory required, speed, number of planes or cell resolution, programming language (CAM-Forth?, CA-BASIC?), compatibility with the CAM-6, and so forth? The program comes on four 5 1/4" floppies, but how much of this is program and how much is the "visual feast" isn't stated -- but those "movies" are no doubt a large part. The cost is $59 US, EduCalc's number for ordering is 1-800-633-2252 Ext 536, or 1-714-582-2637. They are located in California. Anyway, it would be useful to find out how good this program is before purchasing it. Rudy Rucker has written a number of books popularizing mathematics and logic; and also, if I recall correctly, written some amusing "recursive" comics ("Wheelie Willie" comes to mind), and described his conversation with Kurt Godel during Godel's later years. So CA Lab may have some interesting slants. Thanks in advance, Jonathan Indiana University, Bloomington IN 47405-4101 USA (812) 855-6486 From mimsy!brillig.umd.edu!don Fri Dec 29 13:03:18 EST 1989 Article 292 of comp.theory.cell-automata: Path: mimsy!brillig.umd.edu!don >From: don@brillig.umd.edu (Don Hopkins) Newsgroups: comp.theory.cell-automata Subject: SimCity Summary: Urban development simulation where it belongs: in a video game! Message-ID: <21436@mimsy.umd.edu> Date: 26 Dec 89 13:37:09 GMT Sender: news@mimsy.umd.edu Reply-To: don@brillig.umd.edu (Don Hopkins) Organization: U of Maryland, Dept. of Computer Science, Human Computer Interaction Lab, Coll. Pk., MD 20742 Lines: 28 I just got a chance to play SimCity! It's like a drawing program that lets you build cities, by zoning districts, putting down power plants and football stadiums, wiring up the power grid, laying down roads and railroads. The simulation is actually running *while* you're constructing it! It acts like cellular automita with very high level rules -- it keeps track of each cell's population, land value, pollution, and many other factors, and the rules that govern how the zones develop are based on the state of neighboring zones, and other global factors (tax rate, etc). Districts that you've zoned don't come online and start developing until they're hooked into the power grid, by being connected through power line cells or adjacent buildings. Buildings seem to "feed" off of people brought in by roads and railroads. Residential zones in busy districts grow into high-rise apartment buildings. Traffic patterns develop on the roads, and you can see little cars zooming around based on the population of the area, and the flow of the roads! Once you build an airport, a helicoptor flies around the city and reports on heavy traffic, encouraging you to redesign the roads in that area! You may wonder what traffic copters have to do with cellular automita. You just have to play it yourself to understand. SimCity is absolutely the most amazing game I've seen on the Macintosh to date! (It's available on other computers like the Amiga, as well.) The graphics and animation are beautiful. I'll leave it at that -- mere text cannot do it justice. -Don From mimsy!haven!purdue!tut.cis.ohio-state.edu!cs.utexas.edu!swrinde!ucsd!ogicse!emory!hubcap!ncrcae!usceast!park Mon Jan 8 02:00:28 EST 1990 Article 298 of comp.theory.cell-automata: Path: mimsy!haven!purdue!tut.cis.ohio-state.edu!cs.utexas.edu!swrinde!ucsd!ogicse!emory!hubcap!ncrcae!usceast!park >From: park@usceast.UUCP (Kihong Park) Newsgroups: comp.theory.cell-automata Subject: S. Wolfram and computational irreducibility Message-ID: <3035@usceast.UUCP> Date: 7 Jan 90 22:27:42 GMT Reply-To: park@usceast.uucp.UUCP (Kihong Park) Organization: University of South Carolina, Columbia Lines: 67 Steven Wolfram has coined a term called "computational irreducibility" to mean(to the best of my interpretation) that for cellular automata capable of universal computation, there exist problems concerning their behavior which are undecidable. That is, to compute the global configuration of a CA at the n'th iterative step, in general, an algorithm has no recourse but to compute(i.e., simulate) all the intermediate steps to arrive at the outcome. This is all dandy and fine since the undecidability of the halting problem and other undecidable problems have been known for some time. But here is the problem that I have: He seems to very well know that the concept of undecidability is applicable only to problems which have an infinite number of instances. This means that IN GENERAL, there does not exist an algorithm, i.e., a halting turing machine which solves the halting problem for any turing machine / input word pair. But in some of his writings where he uses the term "computational irreducibility"(a listing is appended), he makes statements strongly suggesting(this is my subjective impression) that even for individual problem instances, one has no recourse but to explicitly simulate a computational process(e.g. CA) to compute its outcome. Based on this, he makes "matter of fact" claims that many physical systems are of such character and hence their exact behavior predictable by observation through explict simulation only. It annoys me that he uses undecidability results in such a free and rather misleading fashion. Undecidability, and hence computational irreducibility(as he uses it) are results of a very general character and hence not applicable to everyday problem instances. One should not confuse problems having infinite instances with "one-instance" problems. Here is a problem where the term "computational irreducibility" takes on a more comprehensive meaning, but totally different in its implication and interpretation from what Steven Wolfram has used: One can write a procedure for computing the decimal expansion of root of 2 which at every interative i'th step outputs the i'th digit of the expansion. One can then ask a question such as, "will the one-way infinite sequence associated with this non-halting procedure contain a finite substring of some specified pattern?". To the best of my knowledge, there do not exist known short-cuts to answering this question without peforming the computation ad infinitum in case the answer to the question is "no". For this question, and for any other one-instance problems, undecidability results are of no use. This is so because undecidability of the halting problem does not imply that there exist halting problem instances for which the answer cannot be obtained by effective means. Hence a valid question and more interesting usage of the term "computational irreducibility" would be its association with one-instance problems. Thus, a generalization of the root of 2 problem would be as follows: Does there exist a non-halting procedure with its corresponding infinite sequence such that to compute the n'th symbol of the sequence, the n-1 preceding output symbols have to be computed, i.e., there does not exist a short-cut? If indeed this can be proven, then one has good occasion to use the term "computational irreducibility" to describe this situation. Moreover, one can modify the infinite procedure so that it halts if and only if the associated infinite sequence contains a finite subsequence satifying a certain computable condition. In addition, if one can show that there must exist computable properties of the associated infinite sequence that are false, one has a proof of the halting problem. I would be thankful for comments regarding a proof for the redefined "computational irreducibility" concept as illustrated above. Here are some references to Steven Wolfram's articles: 1. S. Wolfram "Origins of randomness in physical systems", Phys.Rev.Lett.55, 1985,449. 2. S. Wolfram "Undecidability and intractability in theoretical physics", Phys.Rev.Lett.54,1985,735. 3. S. Wolfram "Twenty Problems in the Theory of Cellular Automata", Physica Scripta, Vol.T9,170-183,1985. From mimsy!haven!rutgers!ucsd!ucrmath!x!baez Wed Jan 10 00:25:46 EST 1990 Article 299 of comp.theory.cell-automata: Path: mimsy!haven!rutgers!ucsd!ucrmath!x!baez >From: baez@x.ucr.edu (john baez) Newsgroups: comp.theory.cell-automata Subject: Re: S. Wolfram and computational irreducibility Message-ID: <3231@ucrmath.UCR.EDU> Date: 8 Jan 90 06:56:00 GMT References: <3035@usceast.UUCP> Sender: news@ucrmath.UCR.EDU Reply-To: baez@x.UUCP (john baez) Organization: University of California, Riverside Lines: 96 In article <3035@usceast.UUCP> park@usceast.uucp.UUCP (Kihong Park) writes: >Here is a problem where the term "computational irreducibility" takes on a >more comprehensive meaning, but totally different in its implication and >interpretation from what Steven Wolfram has used: >One can write a procedure for computing the decimal expansion of root of 2 >which at every interative i'th step outputs the i'th digit of the expansion. >One can then ask a question such as, "will the one-way infinite sequence >associated with this non-halting procedure contain a finite substring of >some specified pattern?". To the best of my knowledge, there do not exist >known short-cuts to answering this question without peforming the computation >ad infinitum in case the answer to the question is "no". > >For this question, and for any other one-instance problems, undecidability >results are of no use. This is so because undecidability of the halting >problem does not imply that there exist halting problem instances for >which the answer cannot be obtained by effective means. Hence a valid >question and more interesting usage of the term "computational irreducibility" >would be its association with one-instance problems. Thus, a generalization >of the root of 2 problem would be as follows: >Does there exist a non-halting procedure with its corresponding infinite >sequence such that to compute the n'th symbol of the sequence, the n-1 preceding >output symbols have to be computed, i.e., there does not exist a short-cut? >If indeed this can be proven, then one has good occasion to use the term >"computational irreducibility" to describe this situation. Moreover, one can >modify the infinite procedure so that it halts if and only if the associated >infinite sequence contains a finite subsequence satifying a certain computable >condition. In addition, if one can show that there must exist computable >properties of the associated infinite sequence that are false, one has a proof >of the halting problem. > >I would be thankful for comments regarding a proof for the redefined >"computational irreducibility" concept as illustrated above. It seems that you are working your way towards the concept of algorithmic randomness, closely tied to Kolmogorov complexity. References include: Li, M. and Paul Vitanyi, Kolmogorov Complexity and Its Applications, in Handbook of Theoretical Computer Science, (J. van Leeuwen, Ed.) North-Holland, 1989. A preliminary version of the same work is in the Proceedings of the 3d IEEE Structure in Complexity Theory Conference, 1988. The same authors have a book out by Addison-Wesley, An Introduction to Kolmogorov Complexity and its Applications (1989). Chaitin has developed the idea of algorithmic randomness: Chaitin, G.J., "Randomness and Mathematical Proof" Scientific American, 232 (May 1975), pp47-52 Chaitin, G.J., "Algorithmic Information Theory", IBM J. Res. Dev. 21, 350-359 (1977) Chaitin, G.J., Information, Randomness and Incompleteness. (World Scientific Pub, 1987) other surveys are: Zvonkin, A.K. and L.A. Levin, "The complexity of finite objects and the development of the concepts of information and randomness by the means of the Theory of Algorithms", Russ. Math. Survey 25, 83-124 (1970) Schnorr, C.P., "A survey of the theory of random sequences", in Basic Problems in Methodology and Linguistics (Butts, R.E. Ed.) 1977, pp. 193-210. If Wolfram hasn't defined `computational irreducibility', he may have some of these concepts in mind, more or less vaguely (I haven't read the references you cite). Perhaps even more relevant is the notion of `logical depth' due to Charles Bennett, which grew out of the above work. I have a preprint of his entitled "On the logical "depth" of sequences and their reducibilities to incompressible sequences". (The title should indicate the relation to `computational irredubility'.) It's late here, so rather than try to explain how I think these notions could address your (very valid, in my opinion) complaints, I'll just quote a bit from the Bennett paper: `Roughly speaking, a finite object's information content is the size of its most concise description, and its "logical depth", or stored mathematical work, is the time required to reconstruct it from that description [he gives precise definitions].... A "deep" or dynamically complex object would then be one whose most plausible origin, via an effective process, entails a lengthy computation.' One could hope to prove that certain INDIVIDUAL states or histories of certain cellular automata are logically deep. object ' From mimsy!haven!aplcen!uunet!tut.cis.ohio-state.edu!ucbvax!pasteur!helios.ee.lbl.gov!ucsd!ogicse!emory!hubcap!ncrcae!usceast!park Wed Jan 10 00:26:17 EST 1990 Article 301 of comp.theory.cell-automata: Path: mimsy!haven!aplcen!uunet!tut.cis.ohio-state.edu!ucbvax!pasteur!helios.ee.lbl.gov!ucsd!ogicse!emory!hubcap!ncrcae!usceast!park >From: park@usceast.UUCP (Kihong Park) Newsgroups: comp.theory.cell-automata Subject: Fo:S. Wolfram and computational irreducibility Message-ID: <3038@usceast.UUCP> Date: 8 Jan 90 18:02:31 GMT Reply-To: park@usceast.uucp.UUCP (Kihong Park) Organization: University of South Carolina, Columbia Lines: 65 Here are the results that I have corresponding to the problem of revised definition of "computational irreducibility" which I posted. Results from algorithmic information theory are utilized to deduce the results: computational irreducibility of (1) finite sequences Given a finite sequence w over some alphabet set, let w be algorithmically random, i.e., the size of the minimum program generating w on some standard universal turing machine is approximately |w|. Then any such minimal program P capable of generating w will more or less "copy" w to the output from an internal storage, or from its input. No compaction is possible. Since P is the most compact representation of w, to generate the whole of w, the amount of computation done by P is the minimum one, and hence "computationally irreducible". The above generalizes straightforwardly to algorithmically non-random sequences. If w is any such sequence then its minimum program P(need not be unique) is its most compact representation, and hence to generate the whole of w, again the amount of computation required by P is "computationally irreducible". (2) infinite sequences Given an infinite sequence(one-way) w and a minimal program P which generates it, by the same reasoning as above, the amount of computation needed by P to produce w is "computationally irreducible". By the definition of infinite random sequences, no such program, i.e., a finitely specifiable procedure can correspond to an infinite random sequence. We are implicitly implying that the turing machines acting as generators be deterministic. As the above definitions show, there exist programs whose corresponding sequences to generate in full, the amount of work required by the program is minimum, and hence computationally irreducible. But here is a problem that even the above given definition carries: although to faithfully produce a given sequence w in full, the amount of computation needed by a corresponding minimal program is "computationally irreducible", this definition is a more or less obvious observation. When one investigates "one-instance" problems, one asks questions pertaining to the properties of the problems, and in case of the root-of-2 problem described in the previous posting(the question asks whether in the decimal expansion of root-of-2 there exists a finite substring of some specified pattern), the definition given above does not imply that to answer this question one has theoretically no recourse but to explicitly simulate the algorithm ad infinitum to obtain the answer. As far as I know, knowledge about the properties of root-of-2 is still meager, but this does not mean that a better understanding of this infinite sequence is not possible. Hence, in general, when one asks questions about properties of infinite sequences and their associated generators, these properties are independent of the generating mechanism, and thus the definition given above is of little use. By properties of infinite sequences, I will mean computable functions on the subsequences of the sequence. If we call the above definition a "weak" computational irreducibility then a "strong" definition would say that there exist sequences with their generators such that there are properties of the sequence which can be computed only by explicitly generating the whole sequence. I am investigating these issues basically because I am trying to understand infinite sequences from a computational point of view. Questions arising in chaos theory deal with infinite processes(iterative equations) whose behavior one wants to analyze. Hence, understanding the nature of interesting infinite sequences(a subset of the computable irrational numbers) seems to be a core problem at hand. I would appreciate any suggestions corresponding to the definitions and problems cited above. From mimsy!haven!ames!think!mintaka!bloom-beacon!LANL.GOV!cgl%cardinal Fri Feb 2 18:48:33 EST 1990 Article 315 of comp.theory.cell-automata: Path: mimsy!haven!ames!think!mintaka!bloom-beacon!LANL.GOV!cgl%cardinal >From: cgl%cardinal@LANL.GOV (Chris Langton) Newsgroups: comp.theory.cell-automata Subject: CAM-6 availability Message-ID: <9002010235.AA03796@cardinal.lanl.gov> Date: 1 Feb 90 02:35:05 GMT Sender: root@athena.mit.edu (Wizard A. Root) Distribution: inet Organization: The Internet Lines: 54 Well, well, well...somebody finally asked...here goes... FLAME-ON! The company producing the CAM-6 does not give a flying &*%%$ about the CAM-6, selling it, customer satisfaction, or the customer, for that matter. I ordered mine in Sept 86 and was told "30 days". After 12 monthly episodes of "30-days..." with some lame excuse or another, I threatened to get up in fron of a conference of 150 people I had organized and needed the board for and tell them never to do any business with System's Concepts. The president told me to go ahead and hung-up on me, but the next day I received the board by FED-EXP. Forget System's concepts, but don't forget the board - it is really a nicely done piece of equipment, and Toffoli and Margolis deserve a lot of credit for designing it. They have realized that they made a mistake in letting Systems Concepts produce it and have essentially severed relations with them. A newer version of the board will be produced shortly by Automatrix, a newly formed company in New York. Contact David Hiebeler at "hiebeler@turing.cs.rpi.edu" for further information. It took a threat to get it after a year when System's Concepts was promising 30 days - imagine how long it will take - and what kinds of threats will be required - to get it if they are claiming 1 year. Although there were some good, civil people working for the company, ost of them have been driven off, and the president - Mike Leavet - is just not worth the trouble... Dollars to donuts that an order to Automatrix will come through before an order to System's concepts, and - hey - we might as well support people who care about their customers rather than butt-holes who couldn't care less about us... FLAME-OFF... guess that button was waiting to be pushed for a while! Yours in livelier computing... Cheers! Chris Langton Center for Nonlinear Studies Phone: 505-667-1444 MS B258 Email: cgl@LANL.GOV Los Alamos National Laboratory Los Alamos, New Mexico, USA 87545 From mimsy!tank!ux1.cso.uiuc.edu!brutus.cs.uiuc.edu!jarthur!uunet!snorkelwacker!bloom-beacon!THINK.COM!bmb Fri Feb 2 18:52:23 EST 1990 Article 318 of comp.theory.cell-automata: Path: mimsy!tank!ux1.cso.uiuc.edu!brutus.cs.uiuc.edu!jarthur!uunet!snorkelwacker!bloom-beacon!THINK.COM!bmb >From: bmb@THINK.COM Newsgroups: comp.theory.cell-automata Subject: flocking behavior Message-ID: <9002011402.AA06402@aldebaran.think.com> Date: 1 Feb 90 14:02:49 GMT References: Sender: root@athena.mit.edu (Wizard A. Root) Distribution: inet Organization: The Internet Lines: 72 Date: 1 Feb 90 04:19:08 GMT From: zaphod.mps.ohio-state.edu!rpi!hiebeler@Think.COM (Dave Hiebeler) I am interested in learning some basics about flocking behavior, for example in birds and fish. I'm not interested in how the physiology of particular animals drives flocking. What I am more interested in is phenomenology of flocking, that is, classifications of different types of flocking behavior, some relevant parameters, and maybe some mathematical models of such behavior. I am most interested in "homogeneous" flocking, that is, where there is no "leader", although that is not a strong requirement. ... Hi Dave This is going to sound bizarre, but it's something I've noticed for some time now and haven't mentioned to anybody (perhaps out of fear of having people think that I've truly gone off the deep end...) I've spent quite a bit of time over the last year and a half experimenting with the Rothman-Keller lattice gas for two-phase Navier Stokes flow (two immiscible fluids with a surface tension interface). If you start out with a homogeneous mixture of the two phases, you can watch them separate like oil and water. The model is basically an FHP-type lattice gas where the particles can have one of two colors, say red and blue. Red particles, blue particles, and total momentum are conserved. Collisions involving particles of the same color are exactly FHP collisions; collisions involving particles of different color are chosen to preferentially send each particle toward neighboring sites that are dominated by like color particles. (This rule is carefully quantified in the paper by Rothman and Keller.) It is this affinity of particles for other particles of the same color that gives the fluids cohesion and gives the interface surface tension. Once two fluids separate, it is interesting to look at their interface. Though it is quite stable, there are microscopic fluctuations: Occasionally a particle of red fluid will break away and wander into the blue fluid, and vice versa. When this happens, these "vapor" particles execute Brownian motion in the foreign fluid until they hit the interface again and stick there. Thus, there is some small equilibrium level of foreign particles. This is identical to the physical phenomenon of vapor pressure. Once in a great while, two individual vapor particles will come near each other in the foreign fluid. When this happens, there is a bit of a tendency for them to stay together, according to the above rules. I've watched this happen on Connection Machine simulations on large grids at a few frames per second. The two particles execute a fascinating little dance. They come together, dance about, split apart, come back together, dance some more, etc. I find it incredibly reminiscent of the way that butterflies and moths flutter about together while mating. The biochemistry of mating butterflies and moths is governed by attractant chemicals called pheromones. (A neighbor of mine once experimented with using pheromones to keep gypsy moths out of our neighborhood. A few drops on a rag hanging from a tree will keep a flock of butterflies about for quite some time.) In any event, it may be possible that the cohesion between like particles moving in an incompressible Navier-Stokes background fluid in the Rothman-Keller model is sufficiently similiar to the pheromone-induced attraction of mating butterflies and moths moving through air (well approximated by an incompressible Navier-Stokes fluid under most meteorological conditions) to capture their motion in some qualitative way. Just a suggestion. Best regards, Bruce M. Boghosian (617)-876-1111 Thinking Machines Corporation bmb@think.com 245 First Street Cambridge, Massachusetts 02142-1214 From mimsy!tank!ux1.cso.uiuc.edu!brutus.cs.uiuc.edu!wuarchive!uunet!snorkelwacker!bloom-beacon!megalon.UUCP!rudy Fri Feb 2 18:53:52 EST 1990 Article 319 of comp.theory.cell-automata: Path: mimsy!tank!ux1.cso.uiuc.edu!brutus.cs.uiuc.edu!wuarchive!uunet!snorkelwacker!bloom-beacon!megalon.UUCP!rudy >From: rudy@megalon.UUCP (Rudy Rucker) Newsgroups: comp.theory.cell-automata Subject: Who needs CAM-6 anymore? Message-ID: <9002011758.AA00742@megalon.acad.com> Date: 1 Feb 90 17:58:16 GMT Sender: root@athena.mit.edu (Wizard A. Root) Distribution: inet Organization: The Internet Lines: 35 A bit of hype for my product: CA Lab, the Rudy Rucker Cellular Automata Laboratory from Autodesk For $59.95, CA Lab gives you a pure software CA simulator. On a fast 386, the speed can hit about 10 updates a second, as compared to the CAM-6's 30 updates a second. But speed isn't everything. CA Lab uses 8 bits of state per cell as opposed to CAM-6's 4 bits per cell, meaning that in CA Lab you can create considerably more complex rules. Would you believe a 3 species game of Wator with shrimps, fish, and sharks each keeping track of how old they are and how hungry? Create rules how? Not in Forth, for God's sake, in C, Pascal or even Basic. Yes, CA Lab allows you to write a short program in one of these languages calling on language specific include files that we provide. For the doughtier, we have the option of changing the inner loop where each cell picks up 16 bits of info from itself and its neighbors. Program runs on ANY kind of PC or clone, taking advantage of whatever graphics are available. Preferred mode is 256 color 320 x 200 as available on PS/2s or clones with VGA. CAM-6 is history, CA Lab is today! So get out your credit card and phone Autodesk to order today. (800)525-2763 Rudy Rucker Autodesk, Inc. 2320 Marinship Way Sausalito, CA 94965 From mimsy!haven!ames!apple!brutus.cs.uiuc.edu!rpi!hiebeler Sun Feb 4 17:07:09 EST 1990 Article 323 of comp.theory.cell-automata: Path: mimsy!haven!ames!apple!brutus.cs.uiuc.edu!rpi!hiebeler >From: hiebeler@cs.rpi.edu (Dave Hiebeler) Newsgroups: comp.misc,comp.theory.cell-automata,comp.theory.self-org-sys,comp.theory,comp.sys.ibm.pc Subject: Re: CA question Message-ID: Date: 4 Feb 90 02:09:56 GMT References: <486e5e96.20b6d@apollo.HP.COM> Organization: RPI CS Dept, and LANL Center for Nonlinear Studies Lines: 90 Xref: mimsy comp.misc:8552 comp.theory.cell-automata:323 comp.theory.self-org-sys:127 comp.theory:1332 comp.sys.ibm.pc:46926 In article <486e5e96.20b6d@apollo.HP.COM> nelson_p@apollo.HP.COM (Peter Nelson) writes: > [semi-negative comments about Autodesk's CA lab] You might want to check out Cellsim, it is a public-domain cellular automata program (written in C), which runs under SunView. I realize you want something for the PC, but the inner loops for Cellsim are just pure C, and can be run on pretty much anything. It lets you get up to 8 bits from each of 9 neighbors at most, in addition to a couple of 8-bit "global" parameters. Rather than tell you how to get Cellsim, I'd prefer to wait, as I'm currently working on version 2.5, which is substantially better than previous versions. If you're *really* desperate to get the old versions, send me an e-mail note, although I hate to tell people where to get the old version, since the new one will be so much better. :-) > Conway's Life - types of simulations > are static, i.e., nothing moves from one cell to the next. > I was kind of hoping I could use my new utility to simulate > systems where "stuff" (information or state or something) does > move from one cell to another. This might be useful in simulating > fluid flow or ecological systems. Well, in Conway's life (as well as things like the HPP and FHP lattice gas rules), *information* moves from one cell to another. That is, a "particle" might be represented as an active cell; an empty cell that sees a neighbor with a particle moving toward it, will "create" a new particle while its neighbor "destroys" its particle. The net effect is an information transfer, or a particle "transfer". > But when stuff moves between cells "collisions" may occur. The > problem is not resolving the collision (that's relatively easy). > The problem is propagating the effects of that resolution through > the matrix, and doing so in a way which is not dependent on the > order-of-evaluation. > [stuff about following the results of possible collisions...] You should check out the HPP lattice gas model, this has a simple example of how to get around this. The basic solution (on a square lattice), is as follows (I'll describe it in terms of particles, since that's the terminology associated with the HPP model): 1. Each cell can hold up to 4 particles 2. There cannot be 2 or more particles in the same place moving in the same direction. So a "full" (4-particle) cell would have 1 particle moving in each direction: up, down, left, right. 3. If you think about the "worst-case" collision, this would be a cell that is full and whose neighbors are all full. In that case, the cell would "destroy" its 4 particles (knowing its neighbors would get them), and it would get 1 particle from each of its 4 neighbors. That is, the exclusion principle in item 2 above prevents you from having more than 4 items try to come into the same cell. Since each cell can hold at most 4 particles, you're safe. Three sources of information about HPP, which will clarify what I'm trying to say above are: J. Hardy, Y. Pomeau, and O. de Pazzis, ``Time Evolution of a Two-Dimensional Model System. I. Invariant states and time correlation functions'', J. Math. Phys. [14] (1973). J. Hardy, O. de Pazzis, Y. Pomeau, ``Molecular dynamics of a Classical Lattice Gas: Transport Properties and Time Correlation Functions,'' Physical Review A, [13] (1976) 1949. T. Toffoli and N. Margolus, Cellular Automata Machines: A New Environment for Modeling, (MIT Press, 1987). > Thanks in advance for any observations or comments. I'm new > at much of this so if I'm making lots of stupid assumptions > feel free to tell me, but be nice, please. 8-) I've been at this for years, and I still make lots of stupid assumptions and ask stupid questions. :-) Note that I'll be away at the 2nd Artificial Life conference next week, so I'll probably be slow to reply to e-mail queries until Feb 11th or so. I'll try to post a summary of interesting stuff I see at the ALife conference, probably in the following newsgroups: comp.theory.cell-automata, comp.theory.self-org-sys, comp.bio and maybe a couple of other groups, so watch at least one of those newsgroups around Feb 11-15 or so, if you're interested. -- Dave Hiebeler Internet: hiebeler@turing.cs.rpi.edu (preferred) Computer Science Dept. Bitnet: userF3JL@rpitsmts (last resort) Amos Eaton Bldg. Rensselaer Polytechnic Institute / Troy, NY 12180-3590 From mimsy!haven!ames!think!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!cica!iuvax!maytag!watcsc!death Sun Feb 25 13:05:39 EST 1990 Article 354 of comp.theory.cell-automata: Path: mimsy!haven!ames!think!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!cica!iuvax!maytag!watcsc!death >From: death@watcsc.waterloo.edu (Trevor Green) Newsgroups: comp.theory.cell-automata Subject: Wireworld patterns Keywords: long, wireworld Message-ID: <1990Feb25.050118.7912@watcsc.waterloo.edu> Date: 25 Feb 90 05:01:18 GMT Reply-To: death@watcsc.waterloo.edu (Trevor Green) Organization: University of Waterloo Computer Science Club Lines: 299 George Phillips, thank you for posting the source for your wireworld programme. When I can drag myself away from creating new patterns I might try to make it more efficient. I've been doing wireworld all day and my mind is a haze of =#-===s, but here are my revisions on George's patterns: (Note: I have slightly edited George's patterns for legibility's sake.) > '=' wire > '.' space > '#' electron head > '-' electron tail > (write 0) > ..I.... > .===... > .=.=... > ..=.=.. >O=.=.=.. > .=.===. > ....I.. > (write 1) >A six-cycle memory cell. I tried making a 4-cycle memory cell but failed. Anybody else care to give it a shot? Anyone got a 3-cycle memory cell? (-: > ... > .=. > I=I > .O. >A much improved "OR" gate. Thank you. It makes wireworld that much easier to use. > ....... >I-#==... > ....=.. > ...===. > ....=.. > ..==.==O > .=.=... > .=.-... > ..#.... > ....... > A NOT gate. The fastest NOT gate of this design is a 5-cycle NOT gate; the gate takes 5 cycles to clear following an input of 0. The 6-cycle NOT gate is, however, smaller. I include both of them here. Should you require a longer-cycle NOT gate, just replace the pulsar in either of the gates below with the pulsar of the desired cycle. (Note: with every diagram I post I include the vital statistics. Transit is the number of cycles it takes for a signal to propagate through the device, IBI (interval between inputs) is the number of cycles the device needs between inputs so that the output is guaranteed correct, and the size is the X and Y dimensions of the device. I is an input line and O is an output line (note: there may be more than one of either.)) ......... .=.O..=.. I==..=.-. .=.==..#. ...#...=. ....-==.. ......... ........ .=.O.... I==..... .=.===.. ...#..=. ....-=.. ........ Transit: 3 IBI: (5-cycle) 5 (6-cycle) 6 Size: (5-cycle) 9x7 (6-cycle) 8x7 > ....... > .==.... >I==.==.O > .==..=. > ....==. > .==.=.. > I=.=... > .==.... > ....... > An XOR gate. The main drawback of this particular XOR gate is that you have to stagger your pulses. I have come up with a symmetric XOR gate that also has a lower IBI: ....... .==.... I=.=... .==.==. .....=O .==.==. I=.=... .==.... ....... Transit: 6 IBI: 11 Size: 7x7 >........... >..=.....=.. >.=.=...=.=. >.=.#...#.=. >..-.=.=.-.. >....=.=.... >..=.=.=.=.. >.I==...==I. >..=.=.=.=.. >....=.=.... >...=...=... >...=.=.=... >....===.... >.....O..... > A NAND gate. A better NAND gate (5- and 6-cycle versions): ........... ...-#==.... ..=....=... ...==.-.... .....#..... ....=.=.... .=.=...=.=. I==..=..==I .=.=====.=. .....O..... ........... .....=..... ....=.=.... ....=.-.... .....#..... ....=.=.... .=.=...=.=. I==..=..==I .=.=====.=. .....O..... Transit: 6 IBI: (5-cycle) 5 (6-cycle) 6 Size: 11x10 As with NOT, this NAND has a minimum clearing time of 5, but can have any cycle greater than 4. The next 2 diagrams were a clocked AND gate (ugh!) and a NAND-gate set up for testing patterns, so I deleted them. > ................... > ..............=.O.. > ...........=======. > ..........=...=.=.. > .........=......==. > ...======.......=.. > ..=........===..=.. > .=........=...=.=.. >I=.........=..===... > ..........=...=.... > .....I=...====..... > .......===......... > An AND gate. This is quite elegant, if a little sloppy. I cleaned it up and this seems to be the optimum: ..I........ ...=====... ........=.. ..==...===. .=..=...=.. .=.======O. .=..=.=.=.. .===....... I.......... Transit: 9 IBI: 8 Size: 13x10 I tried another design for an AND gate, incorporating the XOR gate above, but it's larger and slower: .............. ....==........ ...==.=....... I==.==.==..... ........===... I.=.==.==..=.. .=.==.=...===. .=..==.....=.. .=.....====.O. ..=====....... .............. Transit: 14 IBI: 11 (same as XOR) Size: 14x11 >Some pulsars of rates from 3 to 9. (Patterns deleted) The minimum-size pulsars: .... ..... .#.. 3. 4x4 ..#.. 4. 5x5 .-=. .-.=. .... ..=.. ..... ...... ..-#.. 5. 6x7 .=..=. 10. 6x7 (just remove an electron) .=..=. .=..=. ..#-.. ...... > Notice that the >rate 5 pulsar is really a rate 10 pulsar with 2 electrons. I don't think it >is possible to build a loop which takes 5 generations to traverse. I think you're right. ..... ...... ...... ...... ..#.. 6. 5x6 ..-#.. 7. 6x6 ..-#.. 8. 6x6 ..-#.. 9. 6x7 .-.=. .=..=. .=..=. .=..=. .=.=. .=.=.. .=..=. .=..=. ..=.. ..=... ..==.. .=.=.. ..... ...... ...... ..=... ...... >Some attempts at wire crossing. As the diagrammes were rather large, I edited them out. However, I shall make a comment about all of them: they allowed individual signals to cross fine, but when 2 signals were sent simultaneously they'd cancel each other out. To the end of rectifying this, I came up with this rather ugly hack: .............. .....==.=..... .=====.==O.... I....==.=..... ........=..... I....==.=.=... .=..==.===.=.. .=.=.==.=..=.. .=.=......=... .=..==...=..O. .=....=.=...=. ..====...===.. .............. Transit: 22 (ugh!) IBI: 22 (double ugh!) Size: 14x13 Note the pair of delay loops at the bottom to prevent the signals from interfering with one another. It is rather inelegant, but it's the best I've come up with in two nights of wirehacking. Anybody got a *real* wire- crosser out there? For people attempting a wire-crosser, here's another design I came up with, with the idea of preventing the signals from colliding while they're in the device rather than delaying one beforehand and the other afterward. If someone can come up with a better bypass, you'll get a better wire-crosser out of this: ............ ..==..=..... .I=.===O.... ..==..=..... .....=====.. ....=.=...=. ...=.....=.. ..=.=...=... ..===...=... ...=...===.. ..=....=.=.. .=......=... ..===.=.=... .....===.... ..==..=..... .I=.===O.... ..==..=..... ............ Transit: 19 IBI: 24 Size: 12x18 (aack!) Have fun! >George Phillips phillips@cs.ubc.ca {alberta,uw-beaver,uunet}!ubc-cs!phillips Trevor Green death@csc.waterloo.edu watmath!maytag!watcsc!death From mimsy!haven!uflorida!mailrus!iuvax!maytag!watcsc!death Tue Feb 27 01:38:05 EST 1990 Article 356 of comp.theory.cell-automata: Path: mimsy!haven!uflorida!mailrus!iuvax!maytag!watcsc!death >From: death@watcsc.waterloo.edu (Trevor Green) Newsgroups: comp.theory.cell-automata Subject: Wireworld: a better wire-cross Keywords: wireworld, not quite so long Message-ID: <1990Feb26.045139.11904@watcsc.waterloo.edu> Date: 26 Feb 90 04:51:39 GMT Reply-To: death@watcsc.waterloo.edu (Trevor Green) Organization: University of Waterloo Computer Science Club Lines: 45 Kudos goes to Rich Schroeppel (rcs@la.tis.com) for suggesting a "conceptually simpler" wire-cross design which I managed to convert into a practically simpler wire-cross. I actually came up with two designs - the first is smaller and has a shorter transit time, but the second has a *much* lower IBI. Here they are: ........... .....==.... .==.=..=... I=.===..==. .==.=....=O .....==.==. ......==... .....==.==. .==.=....=O I=.===..==. .==.=..=... .....==.... ........... Transit: 10 IBI: 19 Size: 11x13 .............. .....==.==.... .==.=..==.=... I=.===..==.==. .==.=.......=O .....==.==.==. ......===.=... .....==.==.==. .==.=.......=O I=.===..==.==. .==.=..==.=... .....==.==.... .............. Transit: 13 IBI: 13 Size: 14x13 The three diodes that are the difference between the top and bottom diagram catch electrons that "bounce" back out of the final XORs sooner, clearing the device for input six cycles sooner. Trevor Green death@csc.waterloo.edu watmath!maytag!watcsc!death From mimsy!haven!uflorida!uakari.primate.wisc.edu!zaphod.mps.ohio-state.edu!van-bc!ubc-cs!phillips Fri Mar 2 01:12:10 EST 1990 Article 359 of comp.theory.cell-automata: Path: mimsy!haven!uflorida!uakari.primate.wisc.edu!zaphod.mps.ohio-state.edu!van-bc!ubc-cs!phillips >From: phillips@cs.ubc.ca (George Phillips) Newsgroups: comp.theory.cell-automata Subject: Wireworld: better cross, xor and and Message-ID: <6937@ubc-cs.UUCP> Date: 28 Feb 90 09:06:33 GMT Sender: news@cs.ubc.ca Reply-To: phillips@cs.ubc.ca (George Phillips) Organization: UBC Department of Computer Science, Vancouver, B.C., Canada Lines: 45 About a week ago, Ian Woollard sent me a wonderful XOR gate he created: ........= ........= .......=== .......=.= ===-#===.===#-== .......=== And then used (A^B)^A == B to do a very good wire crossing. BTW: my wire crossings _do_ work, but who cares with this around: ...=.....= ...=.....= ..===...=== ..=.=...=.= .==.==.==.== =.===.=.===.= =.....=.....= =....===....= .=...=.=...= ..=.==.==.= ...=.===.= ...#.....# ...-.....- While trying to understand the XOR gate, I realized that one of the tricks was to make each incoming pulse cancel themselves. I used this idea to make a faster AND gate: ............== ...........=..=#-====-===#- ......==..=== .....=..=..=..=.=#-===#-====- ....===..==.==.= ....==.........= ====..========= I don't know if it's me or wireworld, but none of the AND gates are symmetric. Hmmmm. Maybe someone will surprise me -- getting new patterns from the net is almost as much fun as building them yourself. George Phillips phillips@cs.ubc.ca {alberta,uw-beaver,uunet}!ubc-cs!phillips From mimsy!tank!ux1.cso.uiuc.edu!brutus.cs.uiuc.edu!usc!snorkelwacker!bloom-beacon!LANL.GOV!cgl%cardinal Fri Mar 2 01:15:53 EST 1990 Article 360 of comp.theory.cell-automata: Path: mimsy!tank!ux1.cso.uiuc.edu!brutus.cs.uiuc.edu!usc!snorkelwacker!bloom-beacon!LANL.GOV!cgl%cardinal >From: cgl%cardinal@LANL.GOV (Chris Langton) Newsgroups: comp.theory.cell-automata Subject: Cellsim 2.5 available! Message-ID: <9002281130.AA05858@cardinal.lanl.gov> Date: 28 Feb 90 11:30:09 GMT Sender: daemon@athena.mit.edu (Mr Background) Distribution: inet Organization: The Internet Lines: 124 **************************************** ANNOUNCING The Availability of Cellsim version 2.5 **************************************** by Chris Langton (cgl@lanl.gov) and Dave Hiebeler (hiebeler@heretic.lanl.gov) Version 2.5 of Cellsim is a SunView-based cellular automata simulator allowing interactive specification, editing, running, and analysis of 1- and 2-D CA's. It will run on Sun-3's, -4's, and Sparc stations, color or B&W. You can also use Cellsim to attach to a Connection Machine, and use either the CM Frame Buffer or the Sun to display your images; you can do this either directly from a CM front-end, or remotely through the network. Cellsim on the CM allows you to use arbitrarily complex update-functions and "cells". With these recent enhancements, Cellsim is now becoming a tool flexible enough to use for the exploration of lattice-based systems in general. Besides running traditional CAs, you can also do things such as run computed functions of up to 256 states per cell, use floating-point values, or run large ensembles of 1-D systems. Running on the Connection Machine also give you the ability to do complex data-analysis on the fly, in parallel. Since version 2.0 was never "officially" released, the changes since version 1.5 are listed below: 1) 256-state "computed-function" rules can now be used, in addition to lookup-tables, on both the Sun and CM. This greatly expands the range of rules you can investigate. 2) You can now invoke Cellsim once, and change the neighborhood or number of states or image size, without having to call up a new Cellsim. Cellsim will also automatically switch into the proper neighborhood when you load a rule, or the proper image size when you load an image, unless you disable that feature. 3) The "general" random image-generation routine is much more general now. 4) You can create lookup-tables using "Lambda" or "Rho" parameters. The Lambda parameter is described in the article "Studying Artificial Life with Cellular Automata" by Chris Langton, in Physica 22D (1986), and more recently in "Computation at the Edge of Chaos: Phase Transitions and Emergent Computation" by C. Langton, in the proceedings of the "Emergent Computation" conference, to be published in a special issue of Physica D, 1990. 5) The middle mouse-button can be used to reselect the last item selected from any of the menus in the control-panel. 6) You can save images in Sun raster format. 7) The process of writing C code to generate lookup tables has been made easier. 8) Tilde-expansion is now performed on filenames. For example, you can now specify names such as "~/Images/xyz.64x" when loading or saving images, transition tables, colormaps, etc. 9) You can attach to a Connection Machine, and run the actual computations on the CM, using either the CM frame-buffer or the Sun to display the images. 10) A new "defaults" menu which lets you change some of the behaviors of Cellsim. 11) There are 5 user-definable "sequences" which you can "teach" series of button-presses or menu-item selections. So if there is some sequence of commands you routinely use, you can define a sequence to hold those commands, and call them up with the single press of a mouse-button. 12) You can now draw lines and circles in the array, from the "Draw" menu. (The "Draw" menu now contains the "random" image-generation routines). 13) The maximum possible image-size is now 512x512, instead of 256x256 **************************************** You can obtain Cellsim via anonymous FTP to cardinal.lanl.gov (128.165.96.120). Use the login "anonymous", and your e-mail address as password. Then, do the following commands: cd pub bin get cellsim_2.5.tar.Z That will transfer the tar file in binary mode. Once you've obtained the tar file, you should uncompress it and extract its contents as follows: uncompress cellsim_2.5.tar.Z tar xvf cellsim_2.5.tar Once you've done that, go to the "V2.5" directory, and follow instructions in the "README" and "Installation" files there. If you are unable to use FTP, then send either a 1/4" or 1/2" tape to: Chris Langton Theoretical Division T-13, MS B213 Los Alamos National Laboratory Los Alamos, NM 87545 USA If you send 1/2" tape, please specify the density to use. For those of you in Europe or Japan, we are sending copies of Cellsim to people who have agreed to serve as distribution sites there (tapes are on the way, guys!) We'll follow-up with information on how to get it from them, once they have received the tapes and verified that they have working copies. If you obtain Cellsim via FTP, please send Chris Langton (cgl@lanl.gov) a message, so that you can be placed on a distribution mailing-list for announcements of bug-fixes, new releases, announcement of new libraries, and so on. This is very important, so that you can be kept up-to-date with Cellsim as it evolves. Cheers! Chris Langton Dave Hiebeler From mimsy!haven!uflorida!rex!samsung!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!cica!iuvax!maytag!watcsc!death Fri Mar 2 01:15:57 EST 1990 Article 361 of comp.theory.cell-automata: Path: mimsy!haven!uflorida!rex!samsung!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!cica!iuvax!maytag!watcsc!death >From: death@watcsc.waterloo.edu (Trevor Green) Newsgroups: comp.theory.cell-automata Subject: Re: Wireworld: better cross, xor and and Keywords: wireworld Message-ID: <1990Feb28.171512.16633@watcsc.waterloo.edu> Date: 28 Feb 90 17:15:12 GMT References: <6937@ubc-cs.UUCP> Reply-To: death@watcsc.UUCP (Trevor Green) Organization: University of Waterloo Computer Science Club Lines: 136 In article <6937@ubc-cs.UUCP> phillips@cs.ubc.ca (George Phillips) writes: >About a week ago, Ian Woollard sent me a >wonderful XOR gate he created: ..I... .====. .=..=O .====. ..I... Transit: 3 IBI: 5 Size: 6x5 I like it. This is "the" XOR gate. >And then used (A^B)^A == B to do a very good wire crossing. >BTW: my wire crossings _do_ work, but who cares with this around: The first half of that BTW is still open to debate. The second half is unconditionally true and makes the debate irrelevant. ........... .....==.... ....=..=... ...=..====. .I=...=..=O ..=...====. .====..=... .=..===.... .====..=... ..=...====. .I=...=..=O ...=..====. ....=..=... .....==.... ........... Transit: 9 IBI: 5 Size: 11x15 I tried to "simplify" this (it still looks too open for me) and replaced the final XORs with much simpler structures. This also entailed adding two diodes and I wound up upping the IBI to 11 with the size and transit time remaining about the same. This appears to be an excellent design. I'll see if I can improve on it, but I think that this is *the* A^B^A design. It'll be a completely different design that beats it. >While trying to understand the XOR gate, I realized that one of the >tricks was to make each incoming pulse cancel themselves. I used this >idea to make a faster AND gate: > >............== >...........=..=#-====-===#- >......==..=== >.....=..=..=..=.=#-===#-====- >....===..==.==.= >....==.........= >====..========= Now, George, you're making me feel like a tinker to your artist. This one looked a little sloppy again, so I "fixed" it. (Believe it or not, the design below is "topologically" identical to the one above, except for one inconsequential change.) .I..... ..=.... .===... ..=.... I=.=... .=..=.. .=.===. .=..=.. ..==.O. Transit: 7 IBI: 5 (again!) Size: 7x9 >I don't know if it's me or wireworld, but none of the AND gates are >symmetric. Hmmmm. Maybe someone will surprise me -- getting new >patterns from the net is almost as much fun as building them yourself. My original AND gate was symmetric - double each input, XOR the middle two and then XOR again for the final output (more or less). ................ ..=====......... .=.....====.==.. .=..==.....=..=. .=.==.=...===.=. I.=.==.==..=..=. ........===..==O I.=.==.==..=..=. .=.==.=...===.=. .=..==.....=..=. .=.....====.==.. ..=====......... ................ Then I realised I could do without one of the doubled lines. ............. ...==........ ..==.=....... I=.==.==..... .......===... I..==.==..=.. .===.=...===. .=.==.....=.. .=....====.O. ..====....... ............. With the better XOR posted above, I have improved it once again, but it doesn't hold a candle to George's: .I........ ..=....... .====..... .=..===... .====..=.. ..=...===. .I.=...=.. ...=..=.O. ....=.=... .....=.... .......... Transit: 9 IBI: 5 Size: 10x11 The reason for the inefficiency compared to George's AND is that the XOR can be replaced by the other doohickey (the "implication" one (a&~b)...what'll we call it?) for an increase in through speed and decrease in size (amazing how often one follows the other in wireworld). >George Phillips phillips@cs.ubc.ca {alberta,uw-beaver,uunet}!ubc-cs!phillips Trevor Green death@csc.waterloo.edu watmath!maytag!watcsc!death From mimsy!tank!ux1.cso.uiuc.edu!uwm.edu!cs.utexas.edu!uunet!mcsun!sunic!dkuug!freja.diku.dk!torbenm Fri Mar 2 01:17:16 EST 1990 Article 363 of comp.theory.cell-automata: Path: mimsy!tank!ux1.cso.uiuc.edu!uwm.edu!cs.utexas.edu!uunet!mcsun!sunic!dkuug!freja.diku.dk!torbenm >From: torbenm@diku.dk (Torben [gidius Mogensen) Newsgroups: comp.theory.cell-automata Subject: Re: Wireworld patterns Keywords: long, wireworld Message-ID: <1990Mar1.142537.29778@diku.dk> Date: 1 Mar 90 14:25:37 GMT References: <1990Feb25.050118.7912@watcsc.waterloo.edu> Organization: Department Of Computer Science, University Of Copenhagen Lines: 85 death@watcsc.waterloo.edu (Trevor Green) writes: > I have come up with a symmetric XOR gate that also has a lower IBI: > ....... > .==.... > I=.=... > .==.==. > .....=O > .==.==. > I=.=... > .==.... > ....... >Transit: 6 >IBI: 11 >Size: 7x7 How about: ..I.... .====.. .=.==O. .====.. ..I.... Transit: 3 IBI: 5 you can add another output opposite the O, which will be the OR'ed signal. >For people attempting a wire-crosser, here's another design I came up with, >with the idea of preventing the signals from colliding while they're in the >device rather than delaying one beforehand and the other afterward. If >someone can come up with a better bypass, you'll get a better wire-crosser >out of this: > ............ > ..==..=..... > .I=.===O.... > ..==..=..... > .....=====.. > ....=.=...=. > ...=.....=.. > ..=.=...=... > ..===...=... > ...=...===.. > ..=....=.=.. > .=......=... > ..===.=.=... > .....===.... > ..==..=..... > .I=.===O.... > ..==..=..... > ............ >Transit: 19 >IBI: 24 >Size: 12x18 (aack!) You can make a wire-crosser with 3 EOR gates: .....==..... ...==..=.... ..=...====.. .I....=.==O. ..=...====.. .====..=.... .=.====..... .====..=.... ..=...====.. .I....=.==O. ..=...====.. ...==..=.... .....==..... Transit: 9 IBI: 5 (as the EOR gate) I have not tried these except on paper, so there might be some bugs, but I believe not. >Trevor Green death@csc.waterloo.edu watmath!maytag!watcsc!death Torben Mogensen (torbenm@diku.dk) From mimsy!nems!ark1!uakari.primate.wisc.edu!zaphod.mps.ohio-state.edu!think!snorkelwacker!bloom-beacon!TURING.CS.RPI.EDU!hiebeler Fri Mar 2 01:19:44 EST 1990 Article 366 of comp.theory.cell-automata: Path: mimsy!nems!ark1!uakari.primate.wisc.edu!zaphod.mps.ohio-state.edu!think!snorkelwacker!bloom-beacon!TURING.CS.RPI.EDU!hiebeler >From: hiebeler@TURING.CS.RPI.EDU (Dave Hiebeler) Newsgroups: comp.theory.cell-automata Subject: wireworld on CAM and Cellsim Message-ID: <9003020006.AA23688@turing.cs.rpi.edu> Date: 2 Mar 90 00:06:30 GMT Sender: daemon@athena.mit.edu (Mr Background) Distribution: inet Organization: The Internet Lines: 132 Here's Wireworld for CAM and for Cellsim. I only spent a few minutes writing them, so I won't say they're great, but they seem to work. Actually, I'd like to issue a challenge for CAM-users: if you have a better (which I guess means "more interesting and/or compact") way of implementing this, I'd like to hear about it! The Cellsim version of the rule is easier to read, but the nice thing about CAM is you can run 60 generations/sec on a 256x256 array, so you can do large circuits pretty quickly if you want. Cellsim will go pretty fast for smaller arrays. You can't run this rule on the Connection Machine using Cellsim, because the lookup-table would be too large for a CM with 8Kbytes/processor (that's what I use now). Of course, if you were to re-write it in Paris, it would run at several hundred generations/sec, if you turn off the display! I'm not really motivated to write it in Paris at the moment though.. (Paris is the Parallel Instruction Set, a semi-low-level language on the CM that you can call from C, Lisp and Fortran, for those who don't know.) ===== CAM version of Wireworld Wires are on plane 1, electron heads on plane 0, and I store electron tails on CAM-B. To non-CAM users, this might look a little scary. It's written in Forth, a stack-based language. If you've used an HP calculator, Forth is nothing fundamentally new. Plus, you only have to know a little Forth to use CAM. So here's the rule. I hope I didn't make a typo; I am not able to transfer files from my PC to Sun right now, so I just scribbled it down on paper from the PC screen and typed it in here. \ Wireworld, simple logic-circuits as described in \ A.K. Dewdney's "Computer Recreations" column in the \ January 1990 Scientific American. NEW-EXPERIMENT N/MOORE &/CENTERS CAM-A : 8SUM NORTH SOUTH EAST WEST N.WEST N.EAST S.WEST S.EAST + + + + + + + ; : EH 1 ; \ Electron Head : W 2 ; \ Wire : WIRERULE 8SUM { W EH EH W W W W W W } ; : WIREWORLD \ If not E-Tail, do normal rule, else become wire &CENTER IF W ELSE CENTERS { 0 W WIRERULE 0 } THEN >PLNA ; MAKE-TABLE WIREWORLD CAM-B N/MOORE &/CENTERS : ET-RULE &CENTERS EH = IF 1 ELSE 0 THEN >PLN2 ; MAKE-TABLE ET-RULE ===== Cellsim version of Wireworld Here it is for Cellsim. It uses the "m4" neighborhood, so it generates a lookup-table rather than running in computed-function mode. This form of the rule is fairly portable, and should be very easy to plug into CA Lab and other packages, I think. Of course, this rule is so simple, it's no big feat to rewrite it for other systems. /* * File: wireworld.m4.c * By: Dave Hiebeler * hiebeler@heretic.lanl.gov * February 1990 * * Wireworld CA rule, as described in A.K. Dewdney's Jan 1990 "Computer * Recreations" column, in Scientific American. */ #include "nborhood.h" byte wireworld_rule(); #define EMPTY 0 #define EHEAD 1 /* electron heads on plane 0 */ #define WIRE 2 /* wires on plane 2 */ #define ETAIL 3 /* electron tail is a 1 in both planes */ /* Little boolean macro, equals 1 if cell is e-head, otherwise equals 0 */ #define ehead(cell) ((cell==EHEAD) & 0x01) void init_function() { update_function = wireworld_rule; } byte wireworld_rule(nbors) moore_nbors *nbors; { int eightsum; Get_moore_nbors; eightsum = ehead(tl) + ehead(l) + ehead(bl) + ehead(t) + ehead(b) + ehead(tr) + ehead(r) + ehead(br); switch (center) { case EMPTY: return EMPTY; break; case EHEAD: return ETAIL; break; case ETAIL: return WIRE; break; case WIRE: if ((eightsum == 1) || (eightsum == 2)) return EHEAD; else return WIRE; break; } } If someone out there using CAM or Cellsim would like me to crank out a little program to convert those text-diagrams we've been seeing into CAM or Cellsim image-format, let me know. It's easy enough to draw stuff in both systems, that I haven't bothered writing a program to convert. It would only take a couple of minutes to do, though. Dave Hiebeler hiebeler@turing.cs.rpi.edu Computer Science Dept hiebeler@heretic.lanl.gov Amos Eaton Bldg. hiebeler@rpitsmts.bitnet Rensselaer Polytechnic Institute Troy, NY 12180-3590 From mimsy!haven!purdue!decwrl!shelby!portia!portia.stanford.edu!bugboy Fri Mar 9 05:50:47 EST 1990 Article 377 of comp.theory.cell-automata: Path: mimsy!haven!purdue!decwrl!shelby!portia!portia.stanford.edu!bugboy >From: bugboy@portia.Stanford.EDU (Michael Frank) Newsgroups: comp.theory.cell-automata Subject: Wireworld memory units Message-ID: <9937@portia.Stanford.EDU> Date: 8 Mar 90 12:16:03 GMT Sender: USENET News System Reply-To: bugboy@portia.Stanford.EDU (Michael Frank) Organization: Stanford University Lines: 86 Hi, I just started reading this group and noticed the wireworld discussion, and I wondered whether anyone had seen before a design that I came up with for a memory gate. Here it is: ...=..... ...=..... ..===.... ...=..... ..=.=.... ..=.=.... ====.==== ..=...... ......... The wire on the left is the SET input, the wire on top the CLEAR input, and the wire on the right is the output. The inputs and outputs are supposed to be pulsed at 6-cycle intervals. Here's a run-through: Initially there are no electrons in the loop. At a tick which we'll number 0, an electron enters the device as shown: ...=..... ...=..... ..===.... ...=..... ..=.=.... ..=.=.... -#==.==== ..=...... ......... 6 cycles later, it leaves the output, and a duplicate rounds the bottom of the loop for another cycle, so that the memory will continue outputing the pulse: ...=..... ...=..... ..===.... ...=..... ..=.=.... ..=.-.... ===#.#=== ..=...... ......... But, if at this time (or any multiple of 6 cycles afterwards) a pulse arrives in the CLEAR input, ...#..... ...=..... ..===.... ...=..... ..=.=.... ..=.-.... ===#.#=== ..=...... ......... Then two cycles later, the gate will look like this: ...=..... ...-..... ..###.... ...=..... ..#.=.... ..-.=.... ==-=.=-#= ..-...... ......... And the pulse in the loop will go away, and pulses will stop coming out the output. What do you guys think? Anyone seen a memory unit this small before? Note the use of the tiny OR gate within it, and the NOT gate at top. OR gate: .=. === .=. ... Anyway, hope I didn't use too much bandwidth. Bye! Mike Frank bugboy@portia.stanford.edu bugboy%portia@stanford.bitnet From mimsy!tank!ncar!mailrus!uunet!mcsun!ukc!stc!stl!irw Sat Mar 24 08:13:12 EST 1990 Article 381 of comp.theory.cell-automata: Path: mimsy!tank!ncar!mailrus!uunet!mcsun!ukc!stc!stl!irw >From: irw@stl.stc.co.uk (Ian Woollard) Newsgroups: comp.theory.cell-automata Subject: Re: Wireworld memory units Message-ID: <2864@stl.stc.co.uk> Date: 22 Mar 90 14:11:36 GMT References: <9937@portia.Stanford.EDU> Sender: news@stl.stc.co.uk Reply-To: irw@larch.UUCP (Ian Woollard) Organization: STC Technology Limited, London Road, Harlow, Essex, UK Lines: 76 In article <9937@portia.Stanford.EDU> bugboy@portia.Stanford.EDU (Michael Frank) writes: >Hi, I just started reading this group and noticed the wireworld discussion, >and I wondered whether anyone had seen before a design that I came up with >for a memory gate. Here it is: > >...=..... >...=..... >..===.... >...=..... >..=.=.... >..=.=.... >====.==== >..=...... >......... > >Description of operation removed< That's neat! I like it! Small and perfectly formed... I can't offer anything that small. However, I'd like to submit my entry for the fastest IBI memory gate in the wireworld 'competition'... The following is a negative going edge-triggered flip flop. (Using this circuit, you can construct counters, dividers and things- though the Transit time does pose a bit of a problem...) ...O......... ...=...===... ...=.===.==.. ....=..=.=.=. ...===.===.=. ...=.=..=..=. ..==.===..=.. .=.===...=... .=......=.... ..======..... .......=.=... ........===.. .....===.=.=. ....=......=. .....=======. ...........I. Transit: 21 (measured from entry of entry of a 'missing' electron) IBI: 5 Size: 16x13 This is essentially made up of two parts: A flip flop that toggles with every electron sent in: ...O......... ...=...===... ...=.===.==.. ....=..=.=.=. ...===.===.=. ...=.=..=..=. ..==.===..=.. .=.===...=... .=......=.... ..======..... .......I..... Transit: 14 IBI: 5 Size: 11x13 This circuit is based on two exclusive-or gates back to back, giving a fast IBI time. And the edgifier circuit (left as an exercise to the reader to cut out!). This emits an electron every time a stream of electrons stops entering it. __ o __. ____ Ian Woollard (0279) 29531 x2384 <_(_/|_/ / <_ irw@stl.stc.co.uk (STC Technology Ltd.) Extremely long and witty saying reduced to a microdot --> . From mimsy!haven!aplcen!uakari.primate.wisc.edu!zaphod.mps.ohio-state.edu!rpi!hiebeler Fri Apr 13 00:55:50 EDT 1990 Article 404 of comp.theory.cell-automata: Path: mimsy!haven!aplcen!uakari.primate.wisc.edu!zaphod.mps.ohio-state.edu!rpi!hiebeler >From: hiebeler@cs.rpi.edu (Dave Hiebeler) Newsgroups: comp.theory.cell-automata Subject: Cellsim2.5 FTP change and bugfixes Message-ID: Date: 9 Apr 90 17:56:23 GMT Organization: RPI CS Dept, and LANL Center for Nonlinear Studies Lines: 106 Two pieces of news for Cellsim users. The FTP site for obtaining Cellsim has changed, and some bugs in V2.5 have been fixed. ================ Anonymous FTP is no longer available on the machine that Cellsim was previously being distributed from, so we have moved the distribution files to another site. You can now obtain Cellsim (the current version is V2.5) via anonymous FTP to turing.cs.rpi.edu (128.213.1.1). Use "anonymous" as username, and your e-mail address as a password. All Cellsim files are in the directory "pub/cellsim". The current V2.5 tarfile has had the bugfixes applied to it already. If you got Cellsim before April 8, 1990, you should read below to see how to fix your version. ***NOTE*** Be sure to transfer files in binary mode (type "bin" at the FTP prompt to set binary mode). Also, please try to restrict your FTP's to the non-business hours (e.g. after 7pm, before 8am, Eastern time zone). ********** If you've never heard of Cellsim before, this is briefly what it is: a SunView-based cellular automata simulator that runs on color and B&W Sun-3's, Sun-4's, and Sparcstations. It can run 1-D and 2-D CA, on array-sizes of up to 512x512, using up to 256 states/cell. It can also attach to a Connection Machine either locally or through the network, and perform the computations there much more quickly. A copy of the Cellsim V2.5 announcement, which has some more information including details on how to obtain the package, is in the FTP directory as the file "cellsim_2.5.announcement". If you obtain Cellsim for the first time, please send a message to one of the authors, so you will be added to the mailing-list to be notified of future releases or bug fixes. If you already got Cellsim V2.5 when it was first announced, then you don't need to generate lots of network traffic by getting the entire distribution again. You only need to get a few files through anonymous FTP: 1. Get the file "2.5fixes.patch.Z". 2. If you use Cellsim with a Connection Machine, get the file "2.5CMfixes.patch.Z". 2. Get the file "2.5fixes.README", which explains how to apply the patches to V2.5. If you can't FTP, then send a message to hiebeler@turing.cs.rpi.edu, I will probably be able to mail the files to you (I think they're small enough). The following bugs were reported in V2.5, and have been fixed: 1. When you did "Run/bound" when attached to CM, the current time was not updated in the control panel after running. 2. When you changed the CMFE host in the CM defaults popup, it wouldn't take effect until you closed the popup (similarly for CMFE port). Now it takes effect immediately, so you can leave the CM defaults popup open if you like. 3. Couldn't turn off CMFB display while running on the CM. 4. When running skip/bounded on CM, it didn't update Sun display at the end, even if the Sun display was enabled. 5. "B" wasn't defined in the distributed CMnborhood.h, so if you wanted to write a Paris rule that needed B, it wouldn't compile. 6. When you tried to dump a raster image while running on a Sun-3, it complained that it was in closeup mode (even when it wasn't!) 7. "Run/bounded" didn't work right in 1-D (it acted like "screenful"). "Run/skip" and "Run/skip-bound" also didn't work right in 1-D Also, the following two features have been added: 1. Added ability to load/save 2-d images, when in 1-d mode. Previously, only the bottom ("current") line of the array would be saved or loaded when in 1-D mode. Now, there is a toggle in the "Image" defaults popup which you can toggle so that load/save will operate on the entire 2-D image. 2. When running on a Sun, you can now use any array size (up to a maximum of 512) that is a multiple of 4. Previously, the only allowed sizes were 64, 128, 256 and 512. Note that if you're attached to the CM, the only allowed sizes are still 128, 256, and 512. In a future release, we hope to have truly arbitrary array-sizes working on the Sun (not just multiples of 4), and perhaps even on the CM although that may not be practical. Note that these two new features are *not* mentioned in the V2.5 documentation. They weren't going to be available until the next version, but a user needed these features quickly, so I put them in early. Thanks to everyone who has notified us of bugs in Cellsim V2.5. If you notice a bug that is not listed here, please let us know. We also appreciate suggestions for new features to incorporate into Cellsim; many of the new features in V2.5 were suggested by the user community! Chris Langton Dave Hiebeler Theoretical Division hiebeler@heretic.lanl.gov T-13, MS B213 or hiebeler@turing.cs.rpi.edu Los Alamos National Laboratory Los Alamos, NM 87545 USA cgl@lanl.gov -- Dave Hiebeler / Computer Science Dept. / Amos Eaton Bldg. / Rensselaer Polytechnic Institute / Troy, NY 12180-3590 USA Internet (preferred): hiebeler@turing.cs.rpi.edu Bitnet: userF3JL@rpitsmts "Off we go, into the wilds you ponder..."