Xref: utzoo comp.theory.cell-automata:328 sci.math:15807 Path: utzoo!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!elroy.jpl.nasa.gov!ames!haven!umd5!newton.cs.jhu.edu!callahan From: callahan@cs.jhu.edu (Paul Callahan) Newsgroups: comp.theory.cell-automata,sci.math Subject: Re: How Intelligent are the Winning Ways? Message-ID: Date: 16 Mar 91 16:12:17 GMT References: <1991Mar5.171804.1429@zorch.SF-Bay.ORG> <5717@acorn.co.uk> <1991Mar12.155051.16488@zorch.SF-Bay.ORG> <4671@osc.COM> Reply-To: callahan@newton.cs.jhu.edu (Paul Callahan) Organization: JHU Computer Science Deparment, Baltimore MD Lines: 55 In article <4671@osc.COM> jgk@osc.COM (Joe Keane) writes: > [stuff about simulating a 1-D CA in Life] >How do we do this in Life? Actually, I thought I did a passable job of explaining how several postings ago. Basically, we know enough about Life to construct arbitrary finite state machines out of glider guns (usable as cells). And it is possible to develop specific constructors for arbitrary collections of glider guns. These constructors are **MUCH** simpler than universal constructors, and they propagate parallel to one of the coordinate axes leaving a trail of duplicate patterns at regular intervals. Gosper's famous breeder is a simple example of such a thing, but the generalization is easy, once you can make constructors with arbitrarily large spacing between patterns (I can show that this is possible). The finite initial configuration of the CA is placed by hand, and the infinite part is constructed at a rate faster than the propagation of logic in the CA. Hence, the result simulates an infinite 1-D CA. >It's not clear how to construct such control patterns in a direct way. Depending on how you define "clear," I guess. >In >general, two arbitrary patterns will not interact in a nice way, instead >they'll make a mess. But you could try a lot of possibilities for control and >tape patterns, and reject the ones that produce undesirable interactions. It >seems that if you try enough, you may be able to come up with a small subset >with only desirable interactions. As far as i know, no one has done this, but >i think it'd be a good area for Life hackers to explore. I would distinguish two approaches. The first is an "engineering" approach, in which we take all the small scale interactions that are already known (the collection is quite robust). We combine these in a structured way to get the desired effect. This is the approach I've taken above. The second is a "discovery" approach (which you've essentially outlined), in which we look for small scale interactions that do exactly what we want. The disadvantage to the first approach is that the construction is quite big. On the other hand, we know "why" it works. The disadvantage to the second approach is that the search may take an incredibly long time. However, the result will probably be much smaller than that of the former approach. I agree that it would be interesting to do a search for small CA cell simulators, and I don't know if anyone has worked on it. One thing I've considered is turning Life into a 1-D CA by restricting one of its dimensions to k cells and wrapping the space cylindrically. One interesting side effect is that gliders will propagate to adjacent cells. A natural question is how big does k have to be before the CA is universal. The construction of my previous posting shows k is finite. On the other hand, I doubt k is 1. Has anybody worked on this? -- Paul Callahan callahan@cs.jhu.edu