Talk:Garden of Eden pattern

From Wikipedia, the free encyclopedia

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

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)

[edit] 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)