Talk:Garden of Eden (cellular automaton)

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science (Rated Low-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
 ???  This article has not yet received a rating on the project's quality scale.
 Low  This article has been rated as Low-importance on the project's importance scale.


Eric119 added "Actually, all non-bijective automata possess Garden of Eden patterns." This is clearly true if it were "non-surjective", but consider a CA which is surjective but not injective. Thus it is not bijective, but would not have GoE states as the CA is surjective.

Is non-bijective what was meant, and that I'm wrong somehow, or was non-surjective the desired description? Dysprosia 23:24, 5 Jun 2005 (UTC)

All non-injective automata must be non-surjective, according to Cellular automaton#Reversible cellular automata. Eric119 23:55, 5 Jun 2005 (UTC)
How does that section say that? I think I see that consequence now, regardless... Dysprosia 00:51, 6 Jun 2005 (UTC)

I think the "non-injective leads to garden of eden" deserves a reference. Looking at weissteins page, it's probably that theorem by Edward Moore, but I havn't been able to track down the paper — Preceding unsigned comment added by (talkcontribs) 3 October 2006


I don't understand this sentence: "Garden of Eden patterns are necessarily unique." Unique per automaton? That can't be the case, since the page lists more than one GOE pattern for the Game of Life. So in what sense are they unique? --Eriatarka 11:45, 17 March 2007 (UTC)

Until recently that sentence said, "not necessarily unique". Someone removed the word "not", which I have restored. Eric119 17:31, 17 March 2007 (UTC)
Okay... but now the fact that they're not necessarily unique seems about as noteworthy as the fact that they're not necessarily square, or not necessarily symmetrical. Some version of this sentence has been in there from the beginning (and a previous attempt to remove it was reverted, I see.) The sentence started out as "Garden of Life [sic] patterns are not unique." However, the original article was specific to Game of Life patterns and only one example of a Garden of Eden was shown -- so the sentence made sense in that context, but it no longer seems necessary (or meaningful). If no one objects in the next week or two, I think I'll take that line out again. Dave Greene 19:02, 27 March 2007 (UTC)

surjective, injective[edit]

We have these two sentences: "The class of surjective cellular automata and those which are injective over finite configurations coincide." and "However, note that surjective cellular automata do not need to be injective." Do these not seem contradictory? If indeed they are not, I think a bit more description here would be good. —Preceding unsigned comment added by (talk) 08:59, 7 February 2009 (UTC)

No contradiction. Surjective CA are injective when restricted to the set of finite configurations, but do not need to be injective in general. Algernon (talk) 10:35, 7 February 2009 (UTC)

Garden of Eden patterns and Gödel numbers[edit]

Ok. It is rather hard for me to formulate myself here, so I will just write it down in dots :)

  1. There are discrete values for the cells in cellular automates. Every row could thus be written as a number (In the case of Game of Life: black=0, white=1). Combining rows, we get 2D-pictures representing our pattern. Pictures can be represented as numbers (as they are in computers): These numbers are our Gödel numbers.
  2. The algorithm that chooses the next picture is plain and simple an algorithm that generates statements. It generates new well-formed Gödel numbers each new iteration.
  3. Kurts incompleteness theorems proves that there are always true, well-formed statements in all forms of logic that we cannot reach, as long as the logic is "powerful enough". (Read some text about the incompleteness theorems for a definition of power.)
  4. Pseudo-conclusion: These statements are Garden of Eden patterns. If garden of eden patterns cannot be formed, the logic is also not "powerful enough."

Or what do you think? This is obviously not an attempt to prove anything. I just thought it was soo damn cool :D (And if you believe in something like Digital philosophy, this also says something about our own universe.) -- Crakkpot (talk) 12:36, 12 April 2008 (UTC)

Re. #2 above: Why would the next generation be a well-formed Gödel number, necessarily? Seems like you'd have to have some scheme that reliably converts every integer into a well-formed mathematical statement, or the trick won't work. You could find a scheme that would work for some particular GOE and its successor, maybe, but it would be about as difficult (and as significant) as finding a GOE-and-successor that could be interpreted as lines of Shakespeare. Dave Greene (talk) 13:47, 12 April 2008 (UTC)

That is a seriously overbroad description of Gödel's theorem. "All forms of logic" should be replaced by "all sufficiently powerful forms of logic". Here "sufficiently powerful" usually is taken to mean, capable of coding Peano arithmetic. Game of Life isn't really a logic system, but might qualify anyway due to its Turing completeness. But Gardens of Eden exist for much simpler automata that are not sufficiently powerful for Gödel to apply, and their existence can be proven in Life much more simply than the proof of Turing completeness. —David Eppstein (talk) 15:17, 12 April 2008 (UTC)

Ok, so I obviously need to study some more logics and mathematics :) Thanks for the replies! Crakkpot (talk) 06:41, 5 June 2008 (UTC)


No mention is made of the fundamental difference between one and two dimensional CAs : in dimension one, it is decidable whether a CA is surjective, and orphans can be found "easily" (in polynomial time in the number of states). — Preceding unsigned comment added by (talk) 09:21, 6 April 2014 (UTC)

A good point. But the references I know about for testing this sort of problem on one dimensional CAs are for a slightly different problem: testing whether the automaton is globally reversible. For instance, they would say that Rule 90 is not reversible, even though it has no GoE. Do you know a good reference for the problem of testing local injectivity / finding gardens of eden in one dimensional CA? Or for the undecidability of the problem in two or higher dimensions? —David Eppstein (talk) 18:04, 7 April 2014 (UTC)
Never mind, I found it here. —David Eppstein (talk) 18:17, 8 April 2014 (UTC)

Clarity of lead[edit]

I made some changes to the lead, with the following motivation: explaining two things twice in the lead of an article is not clear or helpful to the reader. Saying "more precisely..." implies that your first explanation was imprecise; better to give a single clear and precise explanation than to leave the reader to choose between a precise and an imprecise statement. Similarly, saying "alternatively," and giving another way of defining what an orphan is is not useful.

A single explanation that a general reader can understand is all that is required. I am sure that what I wrote can be improved on, but I am also sure that offering double explanations is not a good way to start an article. (talk) 21:48, 29 May 2016 (UTC)

A single explanation will either be too technical for a general reader to understand (as is true of your attempts) or too simplified to tell the whole story. That's why we start with the simplified version and then expand later with more details. Redundancy is not a bad thing in this sort of writing. —David Eppstein (talk) 22:25, 29 May 2016 (UTC)
Nonsense. Redundancy is self-evidently a bad thing. A good writer can explain things once and well. Which version did you consider too technical? (talk) 23:32, 29 May 2016 (UTC)
The readability checker at rates your preferred first sentence, "In a cellular automaton, a Garden of Eden is a configuration of the whole lattice of the automaton (usually a one- or two-dimensional infinite square lattice), that cannot be reached by any other such configuration.", as 19.9, well past the top end of its score of 30 for university level material (smaller numbers = less readable). It evaluates this informally as "that's really hard going". In contrast, my preferred first sentence (with a little simplification from my previous edits), "In a cellular automaton, a Garden of Eden is a pattern that has no predecessor.", rates 50.6, approximately at the beginning high school level. It is not inaccurate as a definition of the subject, merely lacking in detail, something that is appropriate for a first sentence.
See also MOS:INTRO: "Avoid difficult-to-understand terminology and symbols. Mathematical equations and formulas should be avoided when they conflict with the goal of making the lead section accessible to as broad an audience as possible." and WP:LEADSENTENCE: "If its subject is definable, then the first sentence should give a concise definition: where possible, one that puts the article in context for the nonspecialist" (emphasis added) and "Try to not overload the first sentence by describing everything notable about the subject. Instead use the first sentence to introduce the topic, and then spread the relevant information out over the entire lead." Finally, re your persistent de-boldfacing of "orphan", see MOS:BOLDSYN: "significant alternative titles (which should usually also redirect to the article) are placed in bold".
David Eppstein (talk) 23:51, 29 May 2016 (UTC)
  1. Readability checkers are nonsense. They are simply formulae based on words per sentence and syllables per word, with no possible mechanism to tell if anything is actually readable or not. If I put your preferred text through ROT13, then apparently it's much more readable with a score of 90.1. Therefore, if we trust this readability checker, we should replace your preferred text with "Va n pryyhyne nhgbzngba, n Tneqra bs Rqra vf n cnggrea gung unf ab cerqrprffbe".
  2. Why on earth are you quoting all of these style guidelines to me as if I don't know them? They are exactly the reason that I edited the article. As I've explained several times, if you offer the reader a choice between a precise and and imprecise definition, you're not being clear and accessible to a broad audience, you're just being confusing. And if you define a thing one way, then say "alternatively" and define it another way, you're also just being confusing.
  3. On my first reading of the article, I assumed indeed that "orphan" was an alternative term for "garden of eden", because it was bolded. But someone told me "no, GoE and orphan are subtly different." Do you know who told me that? (talk) 08:18, 30 May 2016 (UTC)
It should be obvious that sarcastic and rhetorical questions about who asked what when are not going to get anywhere. Are you trying to make progress with improving the article or are you trying to win debating points? Anyway, to me the fact that you were confused and thought that the "orphan" definition repeated the GoE definition is an argument that we need more clarity and simplicity, not more technicality. —David Eppstein (talk) 21:02, 30 May 2016 (UTC)
Oh, stop trolling. You're the one who apparently thinks it's impossible to write a clearly worded lead. I believe we can, if we set our minds to it, write a clear definition of the article that does not require the reader to choose between two different definitions for two different concepts. You don't. I tried to improved the article in several different ways; you simply undid any changes I made in their entirety. It's clear to me that you are not interested in improving the article but merely getting your own way. (talk) 21:15, 30 May 2016 (UTC)
That is a mischaracterization of my position. I do not believe it to be impossible to write a clear lead. In fact, I think my preferred first sentence is perfectly satisfactory as a lead. Where I differ from you is that I think the lead should provide a gentle introduction to the subject, and that repeating the same definition in multiple different ways can be helpful to readers, while you seem to believe in pushing them off into the deep end immediately with no assistance. —David Eppstein (talk) 21:39, 30 May 2016 (UTC)
Repeating the same definition would obviously be redundant. What you seem to want to do is present the reader with choices, one precise and one imprecise. How you imagine that is helpful, I cannot comprehend. And why you pretend that wanting a clear introduction is like "pushing them off into the deep end" is also a mystery. Do you seriously not believe it's possible to write a clear introduction with a single definition of each concept? (talk) 20:17, 31 May 2016 (UTC)

RfC on which version of lead to use[edit]

The consensus is that the version that starts more simply and is deliberately redundant is preferable to the the irredundant version. Cunard (talk) 22:27, 3 July 2016 (UTC)

The following discussion is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

Which version of the lead (specifically, the first part of the lead, giving the definitions of a Garden of Eden and of an orphan) is better: the irredundant version or the version that starts more simply and is deliberately redundant? Secondarily, it would also be useful to get more opinions on whether the other cellular automaton terminology introduced in the lead and primarily covered by this article ("orphan", "twin", and/or "Garden of Eden theorem") should be boldfaced. —David Eppstein (talk) 20:19, 31 May 2016 (UTC)

  • My own preference (per the above discussion) is for the deliberately redundant version. —David Eppstein (talk) 20:25, 31 May 2016 (UTC)
Double definitions don't help anyone. The previous version, which included one double definition introduced with "more precisely", and another introduced with "alternatively", was not helpful at all in explaining the concepts concerned. The current version of the text which the user now claims to prefer does not contain these redundancies, and thus the choice the user seeks comment on is not between an intro with redundancies and one without, but simply between different wordings of the intro. I do not see any issue with this introduction.
As for bold text, more opinions are not required to decide which words should be in bold. We have very clear guidelines, which tell us that only the first occurrence of the title and significant alternative titles (which should usually also redirect to the article) are placed in bold. Neither "orphan", nor "twin", nor "garden of eden theorem" are significant alternative titles, and thus they clearly shouldn't be in bold face. (talk) 20:54, 31 May 2016 (UTC)
  • The longer lead is better -- it does not read as redundant to me, and a non-mathematician might have some small chance of understanding it. I have no opinion on the bold. --JBL (talk) 13:44, 1 June 2016 (UTC)
  • The shorter lead is not very comprehensible to me (and I am a mathematician, albeit one that doesn't specialize in this area). The longer lead is a vast improvement. I have no strong opinions about the bold issue, but I lean slightly towards not bolding them. Sławomir Biały (talk) 14:38, 1 June 2016 (UTC)
I also think the Eppstein version is better than the one by "Staszek Lem". Lem's proposed revision brings some discussion of the lattice into the very first sentence, and overall dwells too much on the concept of lattices, which I do not think is very essential for describing the subject of the article. Sławomir Biały (talk) 12:47, 2 June 2016 (UTC)
  • (Answering the RFC call) - Definitions of both versions are bad. And I don't see why "long" version is "redundant", only a bit overly verbose in some places. I will not nitpick the problems which decrease comprehension of the text even for a person who vaguely remembers something about cellular automata; simply here is my version (with "modified" redundancy):

In a cellular automaton, a Garden of Eden is a pattern of the whole lattice of its cells that has no predecessor in any possible evolution of the automaton. John Tukey, who first conjectured existence of these patterns, named them after the Garden of Eden in Abrahamic religions, which was created out of nowhere.[2]

An finite subpattern of the whole (infinite) lattice is called an orphan if any pattern that contains the subpattern is a Garden of Eden. And conversely, it is proven that each Garden of Eden contains at least one orphan.

For one-dimensional cellular automata, orphans and Gardens of Eden can be found by an efficient algorithm, but for higher dimensions this is an undecidable problem. Computer searches have succeeded in finding these Gardens of Eden in Conway's Game of Life. The Garden of Eden theorem of Moore and Myhill states that a cellular automata on the square grid, or on a tiling of any higher dimensional Euclidean space, has a Garden of Eden if and only if it has twins, two finite patterns that have the same successors whenever one is substituted for the other.

Staszek Lem (talk) 17:12, 1 June 2016 (UTC)
  • Of the two alternatives, the longer lead is clearer and easier to understand for this non-expert. A little redundancy is fine if it helps explain concepts more clearly. Clarity and ease of understanding in the lead are priorities for technical articles like these, per WP:TECHNICAL. I am with Staszek in that I think the prose could be made even more explicit for the non-expert. Boldface should only be used to indicate alternative names for the main topic. Per MOS:BOLD, it is better to emphasize jargon or words being defined by using the HTML <em>...</em> markup. --Mark viking (talk) 21:15, 1 June 2016 (UTC)
  • I like Staszek's lead the best. The current one is okay, too. However, MOS:BOLD does suggest bolding terms in the first couple paragraphs if they are the names of redirects. So if Orphan (celluar automation) or something is a significant redirect here, it might make sense to bold it. That probably doesn't mean we should bold all possible terms which redirect here, though. Nat2 (talk) 04:22, 2 June 2016 (UTC)
  • Second, longer version It's just better, Like Sławomir, I am a mathematician, and found the first needlessly terse and an impediment to easy understanding. My preference is to keep this RfC about the two proposed alternatives, and sort out any further modifications later. SemanticMantis (talk) 14:40, 2 June 2016 (UTC)
  • Longer lead is clearly better. Can't decide about the bolding. EEng 04:30, 5 June 2016 (UTC)
  • I much prefer the irredundant version. It says everything that needs saying, clearly, concisely, and once. The redundant version rabbits on without ever coming to the point – it nowhere says what a Garden of Eden configuration is, it uses "pattern", which it does not define. The irredundant version also uses "pattern", but in a (different) sense that is clear from the context. Maproom (talk) 06:51, 14 June 2016 (UTC)
On further consideration ... a source of confusion, with both versions, is that a Garden of Eden is a state of the whole lattice, but the reader is led astray by seeing, right at the top of the article, an image captioned "A Garden of Eden in Conway's Game of Life ..." and showing something finite. The second image is much better – its cropping style hints that it shows only part of something. Maproom (talk) 07:21, 15 June 2016 (UTC)
In the corresponding French article, it's the finite component, the "orphan", that's said to be named "jardin d'Éden". Maybe we should reach agreement on what the term means, before deciding how best to express it. Maproom (talk) 22:01, 17 June 2016 (UTC)
  • Longer version. As someone who came here summoned by a bot, I had no idea what a Garden of Eden configuration was before reading the two versions of the lead. Understanding the shorter version was considerably harder. I suppose that for a reader who is well familiar with the subject the longer text will be redundant, but they will still be able to scan it easily (say, looking for a specific fact or link).WarKosign 07:26, 17 June 2016 (UTC)
  • Dissatisfied either way. Though I am in fact interested in cellular automata and do know what a garden of Eden is, I had not seen this article. I think the entire article needs some serious editing, and neither lede so far presented for approval is satisfactory. Given the current intensity of disagreement however, I am not inclined to interfere, as I do not expect to be able to satisfy all parties. If, against all expectations, I am requested to participate, I'll think again, but as things stand, I am not holding my breath. Good luck all. JonRichfield (talk) 17:58, 18 June 2016 (UTC)
JonRichfield: please don't let the discussion above deter you from improving the article. There's disagreement, but it has certainly not descended to anything personal. The article needs work, that's why there's a discussion. Maproom (talk) 22:48, 18 June 2016 (UTC)
Yes, I agree. More people identifying problems and finding ways to improve the article is surely better than fewer. —David Eppstein (talk) 22:53, 18 June 2016 (UTC)
Fair enough. I'll be back in a couple of days. JonRichfield (talk) 10:59, 19 June 2016 (UTC)

Maproom Sorry to be so long. (RL). I have made a start and will present something maybe tonight. Question: I cannot find any general use of teh term "quiescent" and the description in the body is opaque. Help anyone? JonRichfield (talk) 09:07, 21 June 2016 (UTC)

For Conway's Life it is the same as "dead". Basically, if you have a region of cells all in this state, then nothing happens there. Google scholar finds many uses of this term. —David Eppstein (talk) 12:28, 21 June 2016 (UTC)

Maproom and David Eppstein Thanks for assistance and patience, and apologies for being so long getting underway. I have begun some proposed material that, to avoid cluttering the present talk page, I have saved in User:JonRichfield/Garden of Eden (cellular automaton). You are welcome to visit and to edit if desired, or take parts of it, modified according to taste. Note that some of the changes amount to the same material reworded or redistributed. For example, the lede would be much smaller because it currently contains material that would be of no value to a reader unfamiliar with the topic who first wishes to know whether it looks worthwhile to read on. I have only the introductory sections so far (and as yet needing a lot of editing; I am a slow writer) because there is no point creating essentially a new article without knowing what its reception would be. JonRichfield (talk) 19:29, 22 June 2016 (UTC)

The discussion above is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

What is a Garden of Eden?[edit]

There are two things that may be meant by "Garden of Eden" in this context: A a configuration of the whole lattice that has no predecessor; B a configuration of a finite region that has no predecessor, sometimes called an "orphan".

Favoring A:

Favoring B:

  • The French version of this article
  • The caption "A Garden of Eden in Conway's Game of Life" on the first figure of the article, showing a clearly finite region


I have no idea which is "right", or even whether it matters. But while editors have different views on what the term means, we are unlikely to reach agreement on the best wording. Maproom (talk) 12:29, 19 June 2016 (UTC)

You are mistaken that the caption supports B. --JBL (talk) 12:59, 19 June 2016 (UTC)
You are right, it doesn't. It did yesterday. Thank you, David Eppstein, for correcting it. Maproom (talk) 15:16, 19 June 2016 (UTC)
Who cares what French Wikipedia says? That's not a reliable source, and it doesn't cite any reliable secondary sources that support this interpretation. If reliable sources can be found supporting a different definition, then it can be discussed. Sławomir Biały (talk) 13:25, 19 June 2016 (UTC)
If en:WP and fr:WP differ, I do not automatically assume that it's the French who are wrong. Maproom (talk) 15:16, 19 June 2016 (UTC)
Neither do I, and that isn't what I wrote anyway. I am not "assuming" that fr is unreliable, while en is reliable. Neither one is reliable. But en cites more than a dozen reliable secondary sources, and so can be verified, while the fr article cites none. And the opinion of whoever wrote the fr article is not relevant in determining what the appropriate focus of the en article should be. That should be determined by reliable sources. Sławomir Biały (talk) 08:07, 20 June 2016 (UTC)
More important to me is that a recent secondary source that we're relying on for a lot of material, Kari (2012), supports A. Also, the article will make no sense unless we have separate terminology for those two things, and this is the only consistent choice of terminology that I've seen in sources that clearly make this distinction. As for the image caption, I think that image was never intended to depict a finite region, at least in the sense that, as far as I know, the depicted subset of the plane is not an orphan. Rather, it depicts a configuration of the whole plane in which only the cells in that finite region are alive and the rest dead. —David Eppstein (talk) 17:36, 19 June 2016 (UTC)

A universal construction[edit]

There is a very easy construction of a universal Garden of Eden (a configuration that is a Garden of Eden for every cellular automaton on the same grid of cells and the same set of states that has a GoE). Just enumerate a sequence of patterns such that every finite pattern is contained in a translate of one of the patterns of the enumeration (for instance, list all patterns whose cells form an n × n box, for n = 1, 2, 3, ...) and make a configuration that contains every pattern in the enumeration (e.g. place the patterns disjointly in a spiral around the origin). For the same reason, every random configuration should be a GoE when there exists a GoE. Can anyone track down a source, or is this WP:OR? The phrase "universal Garden of Eden" doesn't turn up anything useful. On a definitional note, I suspect that the early searches for GoE in Life took it as a given that the GoE (or any other Life configuration) should have only finitely many live cells, something not true of this construction, but that restriction is specific to Life (or other automata with quiescent states), not something that makes sense for all cellular automata. But even for this restricted definition, this implies that if you have a bound on the size of an orphan, you can build from that information alone an explicit GoE with finitely many live cells, without having to do any searching. It surprises me that this doesn't seem to have occurred to the early life enthusiasts. —David Eppstein (talk) 17:56, 21 June 2016 (UTC)

PS While I'm asking for sources for things that should be worth mentioning in the article (but only if they can be sourced): when an orphan exists, every cylinder contains a Garden of Eden (just translate the orphan so that it is disjoint from the pattern determining the cylinder, and fill in the remaining cells arbitrarily) from which it follows that the Gardens of Eden are a dense subset of the space of configurations. —David Eppstein (talk) 22:25, 22 June 2016 (UTC)