In a cellular automaton (i. e. John Conway's Game of Life), a Garden of Eden is a configuration that cannot be reached from any other configuration (assuming, of course, that one follows the rules of the game). This means that a Garden of Eden is a configuration that must be specifically created as such (in "the zeroth turn") and will never exist again.
Even if it's a relatively simple concept in theory, it's hard to come up with such a configuration. Indeed, even proving that this configuration exists in a given lattice and with a fixed set of rules is an undecidable problem. A computer is able to reverse-search every possible parent (or predecessor) of a given configuration and if none exist, to decide that it is, in fact, an orphan. However, this brute force approach is not efficient, as the number of potential parents grows exponentially with the area of the pattern.
Currently As of May 13 2014, the smallest known Garden of Eden in a regular Game of Life is was known as Garden of Eden 6, found by Marijn Heule, Christiaan Hartman, Kees Kwekkeboom, and Alain Noels. It's worth mentioning that defining the "smallest" Garden of Eden is somewhat tricky and—for the time being;— outside of the scope of this writeup. You can read more about this pattern here, along with an updated record of record-holding Gardens of Eden. I reproduce the actual pattern below:
□ □ □ □ □ □ □ □ □ □ □ □
□ □ ■ □ ■ ■ ■ □ ■ □ □ □
□ □ □ ■ □ ■ □ ■ □ □ ■ □
□ ■ □ ■ ■ ■ □ □ ■ ■ □ □
□ □ ■ □ ■ ■ ■ ■ ■ □ ■ □
□ ■ □ □ ■ □ □ ■ ■ ■ ■ □
□ ■ ■ ■ ■ □ □ ■ □ □ ■ □
□ ■ □ ■ ■ ■ ■ ■ □ ■ □ □
□ □ ■ ■ □ □ ■ ■ ■ □ ■ □
□ ■ □ □ ■ □ ■ □ ■ □ □ □
□ □ □ ■ □ ■ ■ ■ □ ■ □ □
□ □ □ □ □ □ □ □ □ □ □ □
However, the concept of a configuration with no parents is not exclusive to cellular automata.
A few years ago, yours truly had the pleasure of reading Michael Ende's The Mirror in the Mirror (original title: Der Spiegel im Spiegel). It's a collection of 30 short stories inspired by some illustrations made by Edgar Ende, surrealist painter and Michael's father. The stories are connected to each other in spirit ("by the use of literary leitmotivs"), but are otherwise independent.
Several of these stories feature impossible scenarios. One, for instance, speaks of a soloist dancer, waiting for his cue. He is standing in the middle of the stage with only a spotlight above him so that the only thing he can see is the heavy black curtain in front of him. He recalls that the curtain will begin to rise just as the orchestra starts playing and he must start his routine just as the music reaches his ears; otherwise he will fall behind and will never be able to recover, making a fiasco of the whole performance.
He waits and waits and waits. He's waited for so long that he wonders if his manager has forgotten about him. Maybe the manager hurried him to the stage and the performance has been delayed. Maybe the whole event has been canceled and no one bothered to tell him. The darkness around him is so deep that he can't see anything beyond a few steps away; maybe the sceneshifter is giving him a visual cue from the sides, but is completely invisible.
He thinks that it might be a good idea to go and ask what's happening, but he can't do it without risking his perfect execution. What if the music starts just as he moves away from the spotlight? He doesn't remember how long the stage is, maybe he'll never make it on time. The only thing he can do is to slightly alter his position to shift his weight from one leg to the other.
Scenes like the one above are only possible by creating them as such. We see a dancer who has been waiting for what seems to be an infinite time and it will apparently stay there waiting for an infinite time. The timeline of the event extends infinitely on both directions of time and we're only seeing one point of it, a cross-section.
Arguably, there was a moment in the past where he was not on stage but even he can't remember it. There's no logical way of how he got into this situation without a creator (the writer) putting him in the middle of it.
I admit that this exegesis might be a stretch of my imagination and maybe I'm reading it completely wrong. Still, I like the idea that creative works (writing, in my case) are able to create configurations that are possible only by design and not by evolution of the ruleset. Please note that the concept of a Garden of Eden does not, in any way, imply that creationism and intelligent design are valid scientific theories.
History
- 2020.01.29
- Corrected and updated information about the smallest Garden of Eden
- Added information on record-holding Gardens of Eden