Jump to content

Talk:Garden of Eden (cellular automaton)/Archives/2021

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia


non-bijective

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 129.241.252.14 (talk • contribs) 3 October 2006

unique

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

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 76.99.55.17 (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

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)

Dimension

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 109.190.110.171 (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

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. 83.61.155.91 (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? 83.61.155.91 (talk) 23:32, 29 May 2016 (UTC)
The readability checker at http://www.thewriter.com/what-we-think/readability-checker/ 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? 79.158.212.99 (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. 79.158.212.99 (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? 79.158.212.99 (talk) 20:17, 31 May 2016 (UTC)

What is a Garden of Eden?

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

Unclear:

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

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)

B-class assessment

  1. The article is suitably referenced, with inline citations.  Yes: Inline citations are present for major statements, excluding inferences that are demonstrated.
  2. The article reasonably covers the topic, and does not contain obvious omissions or inaccuracies.  Discussion ongoing: Referred to WP Computer science talkpage for input from a subject-matter expert.
      Yes: Confirmed by consultation at WP CompSci talk page.
  3. The article has a defined structure.  Yes
  4. The article is reasonably well-written.  Yes
  5. The article contains supporting materials where appropriate.  Yes: Illustrates both a Garden of Eden and an Orphan in Conway's Game of Life. Also added time-space diagram of Rule 90 to demonstrate an automaton with no Garden of Eden.
  6. The article presents its content in an appropriately understandable way.  Yes

Point 2 has been referred to the WP Computer science talkpage for input from a subject-matter expert, but all other points pass on B-class assessment. — Sasuke Sarutobi (push to talk) 18:53, 8 July 2018 (UTC)

GA Review

GA toolbox
Reviewing
This review is transcluded from Talk:Garden of Eden (cellular automaton)/GA1. The edit link for this section can be used to add comments to the review.

Reviewer: Reaper Eternal (talk · contribs) 13:47, 14 May 2019 (UTC)


Greetings! Over the next couple days, I will be reviewing this article and posting my thoughts, comments, and concerns here. I may make minor copyedits and fixes, but anything larger will be discussed here with you. Cheers! Reaper Eternal (talk) 13:47, 14 May 2019 (UTC)

Overall review status

Rate Attribute Review Comment
1. Well-written:
1a. the prose is clear, concise, and understandable to an appropriately broad audience; spelling and grammar are correct. This article is very well written.
1b. it complies with the Manual of Style guidelines for lead sections, layout, words to watch, fiction, and list incorporation. checkY, checkY, checkY, checkY, & n/a
2. Verifiable with no original research:
2a. it contains a list of all references (sources of information), presented in accordance with the layout style guideline.
2b. reliable sources are cited inline. All content that could reasonably be challenged, except for plot summaries and that which summarizes cited content elsewhere in the article, must be cited no later than the end of the paragraph (or line if the content is not in prose). Excellent sourcing work on this article!
2c. it contains no original research. All material is properly sourced—no synthesis of sources either.
2d. it contains no copyright violations or plagiarism. I do not have access to every source, but spot checks do not reveal any plagiarism.
3. Broad in its coverage:
3a. it addresses the main aspects of the topic. All major points appear to be well covered.
3b. it stays focused on the topic without going into unnecessary detail (see summary style). Clear & important examples only are given.
4. Neutral: it represents viewpoints fairly and without editorial bias, giving due weight to each. Not applicable.
5. Stable: it does not change significantly from day to day because of an ongoing edit war or content dispute.
6. Illustrated, if possible, by media such as images, video, or audio:
6a. media are tagged with their copyright statuses, and valid non-free use rationales are provided for non-free content.
6b. media are relevant to the topic, and have suitable captions. Issue discussed below resolved.
7. Overall assessment. This is one of the most well-written good articles I have ever reviewed. Great work!

Reviewer comments

For the Rule 90 image, it appears to be a 500 by 500 array of cells in a 2D plane, whereas the text correctly calls Rule 90 a 1D cellular automaton. I believe the image is a time-space diagram with time step increasing as you go down the y-axis. This is not readily apparent and may be confusing to users unfamiliar with the subject matter. Would it be possible to either (1) put axes on the image or (2) add a sentence or two to the caption describing what the image represents?

On another note, the Rule 90 image on the page is so compressed from the original that it appears grayscale and not binary. Do you think increasing it to its original size (500 by 500 pixels) would be better for the presentation in this article? I can also generate a smaller Rule 90 time-space diagram rather than 500 cells over 500 generations if needed.

Other than that, this article looks very good! Reaper Eternal (talk) 20:09, 17 May 2019 (UTC)

@Reaper Eternal: Ok, I replaced by a coarser image and copyedited the caption to clarify that it is a time-space diagram. —David Eppstein (talk) 23:29, 17 May 2019 (UTC)
Thanks! Reaper Eternal (talk) 15:09, 19 May 2019 (UTC)


Retrieved from "http://en.wiki.x.io/w/index.php?title=Talk:Garden_of_Eden_(cellular_automaton)/Archives/2021&oldid=1215887617"