Hi–just looking for a reference for the “Garden of Eden” problem in the context of cellular automata.
Translation: this is from the Game of Life, which most people who’ve spent time programming a computer have probably fiddled with at some point (thumbnail sketch: a two-dimensional array of cells which can be on or off is transformed between ticks of the clock by a simple set of rules that only makes reference to the condition of the immediately surrounding cells. I spent a lot of time fiddling with Life & fractal-generators in my teenage years). The Garden of Eden problem is: find an array of cells for which there is no possible preceding state.
I remember seeing one solution to this problem in some textbook of mine from years ago, but would like a fresh reference or fresh information (my occasion being that, believe it or not, the Game of Life & the Garden problem turn up in the late Ed Dorn’s poem Gunslinger). In particular I’d like to know who proposed the problem & when; who solved it & when; & what its theoretical significance, if any, is.
The earliest reference I could find to the problem (by a quick Google search) is
Martin Gardner’s “On cellular automata, self-reproduction, the Garden of Eden and the game ‘Life.’”, published in the February 1971 issue of Scientific American. Martin Gardner is one of the big figures in cellular automata, so it wouldn’t surprise me if he invented it.
Here we go (from http://www.math.niu.edu/~rusin/known-math/99/eden):
I can’t speak to the theoretical significance of the problem, or even how one would go about solving it. But there you have it.
(And what textbook was this? I’m very interested in cellular automata, so if you’ve got a good textbook on the subject, I’d really like to know about it.)
This is pure mathematics: The problem is its own theoretical significance. The existance of a Garden of Eden pattern in the cellular automaton Life doesn’t mean that we’ll be able to cure cancer, or crack encryption, or anything like that. It just means that there exists a Garden of Eden pattern.
The thread title is a bit misleading; I was expecting to see a Biblical discussion. Should I add the words “Cellular automata” to the title, to draw in a few more of our resident nerds?
For what it’s worth, I think you should; I was just about to hunt down this thread and suggest that.
Chronos: thanks: yes, please do change the title of the thread.
Hm: I guess my point re: “theoretical significance” was whether it was, so to speak, an important problem with further ramifications, or just one of those loose ends that it’s nice to get tidied up. Though I suppose the real question isn’t so much proving an individual pattern is a Garden of Eden (simple enough to do with a computer) as trying to come up with an algorithm to generate a G of E of a specified dimension, or to demonstrate a regular pattern in the disposition of Gardens. – The solution I saw (it was a long time ago in some kind of computer programming book) was probably the 33x9 pattern mentioned in the link provided by ultrafilter…certainly not the 16x16 pattern given there, as I remember it as being much wider than it was long.
Ah, Life–I remember wasting many hours on gliders & glider-guns & the like. Much better than computer solitaire…
What little reading I did last night suggested that it hasn’t proven to be important yet.