Important Notice: Our web hosting provider recently started charging us for additional visits, which was unexpected. In response, we're seeking donations. Depending on the situation, we may explore different monetization options for our Community and Expert Contributors. It's crucial to provide more returns for their expertise and offer more Expert Validated Answers or AI Validated Answers. Learn more about our hosting issue here.

Eden patterns exist in Conways Game of Life. Do they exist in other automata?

April 26, 2017automata conway Eden exist life patterns

0

Posted

Eden patterns exist in Conways Game of Life. Do they exist in other automata?

1 Answer

0

Posted

Harold McIntosh They exist for the great majority of cellular automata, and there is a considerable theory concerning the criteria according to which they exist or not, which in turn is related to the question of whether the automaton is reversible or not. A quick criterion is that the rule of evolution has to be “balanced” for an automaton to be reversible and thus not have Garden-of-Eden configurations. Life fails this, because many more neighborhoods lead to zeroes than to ones. A more precise criterion is one called “mutual erasibility” introduced by Edward F. Moore, to be found in books on automata theory. This state of affairs notwithstanding, several persons have programmed a search for Life GOE’s and found some; I think an example is shown in Poundstone’s book. So, of course, a Turing machine could undertake a similar calculation. As an aside, note that it is a Minsky register machine which has been shown to be a universal computer in Life, but that