As a further example of how the game can "compute" in the same way that a traditional computer and programming language can be used to execute programs that compute, I loaded up the recently created seed pattern by Jason Summers for a new type of "Primer" pattern. These patterns in the game will in some fashion "output" the sequence of prime numbers. This particular pattern emits the type of prime number most familiar to us: 2, 3, 5, 7, 11,13... ad infinitum.
Start the video, and observe the area where the "gate" is in the lower left middle. Passing through it will be Life "Spaceships" spaced precisely as the sequence of primes.
Stephen Wolfram, polymath extraordinaire and creator of the widely used mathematical, programming, and graphing workbench Mathematica has written extensively on the subject of cellular automata in his book A New Kind of Science.
In all fairness, while well received overall the book was the target of some rather excoriating reviews by experts in the various related fields, and accusations of intellectual thievery have been raised. Perhaps the most scathing of these and an interesting read on its own can be found in Quantum Information & Computation with the review by Scott Aaronson, a theoretical computer scientist and member of the MIT Electrical Engineering and Computer Science department.
The book is good read nonetheless for a view into the wide applicability of cellular automata, and the five pound nearly 1300 page tome will make a fine doorstop if you find it not to your fancy.
Wolfram extensively discusses the relationship of these objects to nature, modeling complex behaviors and results with simple basic starting seeds. A good example is that of certain seashells, where the complex patterns of their shell is generated by natural cellular automata.
Wolfram's central point in the book is that complex behaviors and results do not require a complex system for their production.
This culminates in the core of his "new science", the "Principle of computational equivalence".
As eloquently described in the Wikipedia entry for the book, "The principle states that systems found in the natural world can perform computations up to a maximal ("universal") level of computational power. Most systems can attain this level. Systems, in principle, compute the same things as a computer. Computation is therefore simply a question of translating inputs and outputs from one system to another. Consequently, most systems are computationally equivalent. Proposed examples of such systems are the workings of the human brain and the evolution of weather systems."
To get your own hands-on feel for how simple systems can generate incredibly complex results, get yourself a copy of the most excellent Golly cellular automata application where you can explore Conway's Game of Life and other types of cellular systems.
You may find yourself as addicted and fascinated as I am!
Posts
OK, so there is a set of rules. 4 of them.
ReplyDeleteAre we supposed to expect/choose a certain answer, and then mathematically determine what the starting pattern should be? I really don't see how that has anything to do with computer programming or mathematics.
Personally, Conways game if life is just a set of rules that allow some random starting pattern to evolve into something approaching a finished answer... such as 100/3 = 33.333333...
Good question.
ReplyDeleteThe game is provably irreversible in most cases. This can clearly be demonstrated by making a pattern where all the cells die: information is lost, you have no way of determining from a blank board what might have been there.
So you really can't in most cases take the desired result and built the pattern from that.
On the other hand, you can combine patterns with known behaviors, and build interactions between them that accomplish your goals.
If you build say a pattern that does the AND operation, another that does the OR operation, etc., you can combine these into a 'circuit' that computes, much in the same way a CPU is made of very trivial basic operations done with transistors and other electronic components.
So the behavior of these cellular automata has everything to do with programming: the rules by which they act are in themselves a simple algorithm, and the behaviors you can build from patterns can 'execute' any algorithm.
Of course, the concept of 'algorithms' is most basic to programs and programming.
Thanks for the comment!