kestas.kuliukas.com

Could Conway's Game of Life host life

This essay is about Conways Game of Life; its implications, applications, and whether it can host life.
Conways Game of Life was a breakthrough in mathematics, it opened up a new field; cellular automata.1 The playing board for the Game of Life is a two dimensional grid. Each cell in the grid can be in two states; alive or dead.

The rules are simple:

From these three rules complex behaviors emerge. Conways Game of Life (or rather cellular automata generally) can be applied to cryptography. You can exploit the fact that its computationally expensive to go back from a given pattern to the pattern which its derived from, in the same way that asymmetric cryptography at the moment exploits the fact that its computationally expensive to find the prime factors of a semi-prime. The reason cellular automata is being looked at as an alternative is that finding prime factors will become much easier with quantum computing, whereas theres no technology on the horizon which could make reversing cellular automata faster.2

In the Game of Life people have created pseudo-random number generator patterns, which output flyers unpredictably at a given interval.3
By counting the number of living cells at any given time mathematical functions can be modeled. The flyer gun given earlier grows in a linear fashion, but patterns have been made which grow at a logarithmic, exponential or polynomial rate.4
Conways Game of Life can even host Universal Turing Machines, which means theyre capable of performing any computation.5 All from three simple rules.

If such complex behaviors arise from simple rules perhaps our universe is also built upon simple rules. This emergent complexity shows on a smaller scale how complex phenomenon like life and consciousness can arise from simple physical rules, and perhaps life can arise from Conways Game of Life too.

Recently the first ever living organism was simulated in a supercomputer; a simple potato virus.6 It could only be simulated for a vanishingly small period of time (a few nanoseconds of simulated time), because the processing:simulated time ratio is massive. The laws of quantum physics take very long for our processors to work through, and until quantum computers become a reality this isnt going to change. Perhaps Conways Game of Life would be an environment in which life could exist, but which would be easier and faster for us to simulate with our binary based hardware; the very first incarnations of cellular automata by Von Neumann were designed to be able to host self replicating patterns.

Conways Game of Life pre-dates modern computers; originally it was done on paper and pen, taking hours to do computations which take us a fraction of a second now. As the rules and data structure are so simple computers were ideal for implementing the Game of Life, and the Game of Life was one of the most widely explored uses for computing power used when computers first became accessible.
Despite being much faster than doing it by hand, the original computers were relatively slow simulating the Game of Life. For each cell you have to fetch the status of the surrounding cells, process the cells, and store the results. These fetch and store operations are relatively slow, and when you have a grid of 100x100 (a very limiting grid) you have 10,000 cells to process each turn.

These days with the immense size and low latencies of on-die cache, and out of order execution, these problems dont matter for the sorts of patterns typically run. But if youre attempting to find which pattern results in a given pattern, or try as many random patterns as possible in the hope of seeing life emerge, speed is important and even our fast general purpose modern processors fall short.

Using a dedicated processor these goals are more realistic. The Game of Life grid easily translates into a processor; each cell would have a single flip-flop to store its state, it would transmit its state to each of the adjacent cells, and receive their state; and have a simple combinational circuit to detect how many adjacent cells are alive, and on the start of the cycle save the next state to its flip-flop.
Using a dedicated processor such as this you could process an entire grid in a single clock cycle, and the simplicity of the combinational circuit would mean that the cycle could be very small. Going at its fastest a Game of Life program on a modern x86 processor can process around 100,000 generations per second, on a dedicated processor clocked at 1 GHz 1,000,000,000 generations could be processed per second.

But how can we tell whats alive within a Game of Life simulation, how can we even tell whats alive in the physical world we live in. Some would argue a biological virus isnt alive, because if a biological virus is alive, why not a computer virus or chain mail. They both rely on other systems to replicate; the only difference is the systems they exploit.

Life in a 2D grid wouldnt be complex, it wouldnt have to be. Theres no competition over materials on the Game of Life grid as living cells can create more living cells. Life would have to replicate, but it would also have to defend itself. When dealing with man-made patterns just changing one cell from alive to dead, or visa versa, will almost certainly bring the whole pattern into disorder. A life form would have to have an outer wall to defend itself from a barrage of flyers and other colliding patterns, in the same way that we have a skin to defend ourselves from radiation and bacteria etc.
In this sense a life pattern would be similar to a bacterium. Unfortunately the chance of one randomly forming is practically zero, and its safe to assume an equivalent in a Game of Life wouldnt be much less complex. In our world DNA based life evolved from earlier RNA based life, which itself evolved from an earlier form.

Mutations are necessary for this process to take place, but how would this happen within a game of life Random errors while copying cant happen in the Game of Life without an external influence because the rules dont leave any room for chance like the rules of our universe. External patterns may cause mutations, but an external pattern is more likely to completely destroy a pattern than subtly change it. Perhaps mutation could be caused by firing electromagnetic radiation into the chip, which will occasionally change a flip-flops state (similar to how mutation works for physical life).

Despite the hurdles above we have yet to think of a reason why life cannot occur within the Game of Life. Searching for artificial life with processors may be like searching for intelligent life on other planets with radio telescopes; it seems likely that it exists somewhere but finding it in the vast expanse of space, or vast numbers of possible patterns within a grid, may be impossible.

References:
1 http://en.wikipedia.org/wiki/Cellular_automaton#History
2 http://cell-auto.com/publickey/index.html
3 http://www.bignell.demon.co.uk/life.htm
4 http://pentadecathlon.com/lifenews/2006/03/by_gosper_and_by_golly_1.html
5 http://web.archive.org/web/20030210114324/http://www.rendell.uk.co/gol/tm.htm
6 http://www.redherring.com/Article.aspxa=16092