herraiz.org | Blog
Main | Blog | Research papers | PhD thesis | GnuPG (PGP)
Subscribe to this blog in a reader
Main | Blog | Research papers | PhD thesis | GnuPG (PGP)
When I read The Recursive Universe I discovered that there was much more than I thought behind the Conway's game of life. The game itself is very simple: draw a diagram in a 2D matrix where each cell can have only one of two different states (dead and alive), and let it evolve according to the following rules:
The rules are applied again to the resulting matrix, in a recursive manner.
With these simple four rules, you can obtain a large amount of patterns, some of them very complex. Some patterns are still forms, that is to say, static diagrams that do not change no matter how many iterations are executed. Some patterns oscillate. Some patterns move and live forever. Some of them just die after a few iterations (called generations in the terminology of the game).
The complexity that is obtained in some of the patterns is very surprising when someone first knows of the game of life. Yet it is just the consequence of the recursive algorithm.
The interesting point is that the game of life is a universal Turing machine, and the 2D diagrams are programs that are executed by the Turing machine. Therefore, the game of life can perform any computation that can be done by a Turing machine, that is to say, any computation that can be expressed in a Turing complete programming language.
Is there any relationship between the recursivity-born complexity of the game of life and the complexity and problems to estimate software in the real world? Some software engineering researchers (myself included) are trying to solve the holy grial of software estimation, to try to cope with the problems that complexity conveys in software management, planning and estimation (I call it holy grial because I doubt it will be ever solved, but if it is solved, it would have a big impact in the way we engineer software).
By looking at the complex patterns that the game of life produces, it is very difficult to infer the four simple rules that are behind the game. Are we doing that in software engineering research? Is software engineering trying to deduct the rules by just looking at the patterns produced by the software process? Is the programming activity a recursivity-born complex process? And if it is, how can we unroll this recursivity so we can discover the simple rules that are behind the programming process?
