Talk:Garden of Eden

Theorem

The last sentence in the section contradicts everything else, unless I'm mistaken: "However, surjective cellular automata do not need to be injective." implies that {surjective} > {injective} (and {injective} is contained by {surjective}), while previously it says stuff like "the class of surjective cellular automata and those which are injective over finite configurations coincide." which implies {surjective} = {injective}, which is further supported by "In other words, a cellular automaton has a Garden of Eden if and only if it has two different finite configurations that evolve into the same configuration in one step." and stuff. Although even if that last statement is right,the theorem still proves that Life has Gardens of Eden, so I'm not really sure whether it is or not. Elithrion 18:35, 14 February 2009 (UTC)

The important distinction is between simply injective and injective over finite patterns. The theorem says that injective over finite patterns iff surjective. Thus, surjective implies injective over finite patterns, but not injective overall (that is, there may be two *infinite* patterns that are mapped to by the same infinite pattern). This could perhaps be made more clear in the article. Anyway, yes, the "picture" is {surjective} = {injective over finite patterns} > {injective}. Nathaniel 19:07, 14 February 2009 (UTC)

Ah, thanks. I guess I overlooked that distinction. Elithrion 20:42, 14 February 2009 (UTC)

I managed to find a paper documenting the Garden of Eden theorem: [[1]]. (Mutually erasable is equivalent to being finitely non-injective.) Now that I understand the situation better, I'll try to detail a proof that finitely non-injective implies non-surjective, due to a proof in Conway's Winning Ways. FractalFusion 08:23, 25 March 2009 (UTC)

Records

What do you think about insertion of following-like table? --Mtve (talk) 10:20, 7 April 2016 (UTC)

(The table has been moved to main page)--Mtve (talk) 07:26, 23 April 2016 (UTC)

Hello, Mtve. I would just insert it into the article without attempting to discuss it. From my experience, nobody bothers to discuss anything anymore on this wiki. Posting it on talk pages only increases the chance that the information will never make it to the main page.

I would avoid using things like "C2dia" and "D4" as symmetries, because those labels might be ambiguous. FractalFusion (talk) 18:22, 8 April 2016 (UTC)

Thanks for the feedback, FractalFusion! I'm going to improve links and references and then move it to the main page as you've suggested. Meanwhile, Steven Eker has made another breakthru! --Mtve (talk) 16:31, 10 April 2016 (UTC)

Well, FractalFusion, I personally don't think you give good advice to Mtve, especially having in mind your recent careless renaming of Triple pseudo still life and Quad pseudo still life without discussion. Mtve, your table is great, but if you could provide references, it would be perfect. Codeholic (talk) 06:32, 20 April 2016 (UTC)

Thanks! Links added. Please help with wording to start the paragraph about records, I really can not write anything readable. Mtve (talk) 18:38, 20 April 2016 (UTC)

Wikipedia

Would link to the Wikipedia [[2]] be appropriate here?

It discusses more then only Game of Life, but has some interesting topics covered, also in Talk page --Mtve (talk) 16:16, 12 July 2016 (UTC)

I'd say having that link would be great. Apple Bottom (talk) 18:17, 12 July 2016 (UTC)

Merging all GoE examples into this article?

User:AwesoMan3000 has proposed on every GoE page that "pretty much none of these are extremely notable on their own, and would probably be better off merged into the main article". The broken templates with multiple parameters and the long red links are quite annoying, but it's not polite to solve the problem immediately by removing them as well.

Compared with the case of pure glider generator, a completely obsolete subject, Gardens of Eden are still partly of modern interest and it is encouraged to discover record-breaking GoEs. Yet both are lack of applications to some degree, and there isn't much to write about for each individual example other than the discovery information.

What do you think? GUYTU6J (talk) 10:28, 21 July 2020 (UTC)

Looking at the issue again, I suppose a new design of the table that could possibly replace the individual articles... (EDIT: moved to the main page)

Any suggestions? GUYTU6J (talk) 09:12, 7 December 2020 (UTC)

Added a line to the table above. Achim's page has been updated and therefore some references are missing, but I can't get access to Wayback Machine currently. GUYTU6J (talk) 16:11, 24 December 2020 (UTC)

What references do you need access to, exactly? Ian07 (talk) 16:19, 24 December 2020 (UTC)

Ooops, after checking the refs I didn't found any actually missing ones so never mind. Now I've completed constructing the table and thus the remaining job is to move it to the article and redirect the individual pages there. GUYTU6J (talk) 15:25, 26 December 2020 (UTC)

Two OEIS sequences related to a GoE

Of the known Gardens of Eden, which one is associated to Sloane's  A196447 and  A197734? How to label the cells by the successive order they are placed? (The question was asked on the forums but nobody noticed.) GUYTU6J (talk) 15:46, 16 May 2021 (UTC)

No absolute Garden of Eden

It has been proven that there are no finite patterns that appear to be Gardens of Eden in every outer-totalistic rule, for in rule B/S012345678 there is no Garden of Eden.

It has also been proven that there are no finite patterns that are not Gardens of Eden in any outer-totalistic rule, for in rule B012345678/S012345678 all finite patterns are Gardens of Eden.

According to the Garden of Eden theorem, Gardens of Eden are known to exist in Wireworld. The smallest known contains only 1 cell. ColorfulGalaxy (talk) 11:01, 31 July 2021 (UTC)

== Is it not obvious? ==

I felt similarly to xkcd 2042 when I read this, why is this referred to as a theorem instead of stating "It is a trivial property that Gardens of Eden exist in all non-reversible cellular automata (due to the process of mapping a set of states to itself with some repetitions causing there to be some unmapped to)"? Is something different in infinite planes? Is the fact that the proportion of states that are orphans (under a given condition in the cells adjacent to (but outside) the perimeter of a pattern's bounding box) grows hyperexponentially with respect to pattern size and that bounding box perimeters grow only exponentially enough to prove that there will exist an orphan under all perimeter conditions, given a sufficient size? Can we give a restatement of the proof itself instead of only its conclusion?

(Bear in mind, however, that I also thought that the conjecture in  A000105 that "Almost all polyominoes are holey. In other words,  A000104(n)/a(n) tends to 0 for increasing n." was trivial, before apg explained to me that it could be the case that they tend to fan out on average, so the statement's veracity isn't one of the intuitively obvious things that are hard to prove rigorously, but is nontrivial to think of intuitively as well (though the graph of the proportion is suggestive of an exponential decay and the sequences' logarithms seem to diverge linearly).)

Edit: I have thought about it some more, I don't think this idea would work.