  The Immigration Game (invented by Don Woods in 1971) extends the solitaire
Game of Life (invented by John Conway in 1970) to enable two-player
competition. The Immigration Game can be used in a model of evolution by
natural selection, where fitness is measured with competitions. The rules for
the Game of Life belong to the family of semitotalistic rules, a family with
262,144 members. Woods' method for converting the Game of Life into a
two-player game generalizes to 8,192 members of the family of semitotalistic
rules. In this paper, we call the original Immigration Game the Life
Immigration Game and we call the 8,192 generalizations Immigration Games
(including the Life Immigration Game). The question we examine here is, what
are the conditions for one of the 8,192 Immigration Games to be suitable for
modeling open-ended evolution? Our focus here is specifically on conditions for
the rules, as opposed to conditions for other aspects of the model of
evolution. In previous work, it was conjectured that Turing-completeness of the
rules for the Game of Life may have been necessary for the success of evolution
using the Life Immigration Game. Here we present evidence that
Turing-completeness is a sufficient condition on the rules of Immigration
Games, but not a necessary condition. The evidence suggests that a necessary
and sufficient condition on the rules of Immigration Games, for open-ended
evolution, is that the rules should allow growth.
