A Brief Background
Cellular Automata (CA) can be constructed in one, two, three, or more dimensions and can best be explained by giving an example utilizing Conway’s rule. Start with an infinite grid of squares. Each square has 8 touching neighbors; typically these neighbors are treated the same (a “Moore neighborhood”), whether they touch a candidate square on a side or at a corner. We now fill in some of the squares; we shall say that these squares are “alive”. Discrete-time units called generations to evolve; at each generation, we apply a “rule” to the current configuration to arrive at the configuration for the next generation; in our example, we shall use the rule below
- If a live cell is touching 2 or 3 live cells (called “neighbors”), then it remains alive next generation, otherwise, it dies.
- If a non-living cell is touching exactly 3 live cells, it comes to life next generation. Figure 1.1 depicts the evolution of a simple configuration of filled-in (“live”) cells for the above rule.
There are many notations for describing CA rules; these can differ depending upon the type of CA. For CA of more than one dimension, and in our present discussion, we shall utilize the following notation, which is standard for describing CA in two dimensions with Moore neighborhoods.
Move across the grid as they change from generation to generation. Such forms are called translating oscillators, or more commonly, gliders. Conway’s rule popularized the term; in fact, a flurry of activity began during which a great many shapes were discovered and exploited. These shapes were named whimsically — “blinker” (Fig. 1.1), “boat”, “beehive”, and an unbelievable myriad of others. Most translating oscillators were given names other than the simple moniker “glider” — there were “lightweight spaceships”, “puffer trains”, etc. Of course, rule 2,3/3 is not the only CA rule (even though it is the most interesting). Configurations under some rules always die out, and other rules lead to explosive growth. (We say that rules with expansive growth are unstable.)
The Original Glider Gun
Conway’s rule 2,3/3 is the original golden rule and is unquestionably the most famous CA rule known. A challenge put forth by Conway was to create a configuration that would generate an ever-increasing quantity of live cells. This challenge was met by William Gosper in 1970 — back when computing time was expensive and computers were slow by today’s standards. He devised a form that spits out a continuous stream of gliders — a “glider gun” so to speak. Interestingly, his gun configuration was displayed not as nice little squares, but as a rather primitive typewritten output (Fig. 1.5); this emphasizes the limited resources available in 1970 for seeking out such complex structures. Soon a “cottage industry” developed — all kinds of intricate initial configurations were discovered and exploited. Such research continues to this day and has pretty.
Other gol Rules in the Square Grid
Rule 2,4,5/3 is also a golden rule and sports the glider shown in Fig. 1.6. It has not been seriously investigated and will probably not reveal the vast array of interesting forms that exist under 2,3/3. Interestingly, 2,3/3,8 appears to be a golden rule which not surprisingly supports many of the constructs of 2,3/3. This ability to add terms of high neighbor counts onto known gol rules, obtaining other jail rules, seems to be easy to implement — particularly in higher dimensions or in grids with large neighbor counts such as the triangular grid, which has a neighbor count of 12.
Why Treat All Neighbors the Same?
A fascinating challenge was proposed by Conway in 1970 — he offered $50 to the first person who could devise a form for 2,3/2 that would generate an infinite number of living cells. One such form could be a “glider gun” — a construct that would create an endless stream of gliders. The challenge was soon met by William Gosper, then a student at MIT. His glider gun is illustrated here. At the top, testifying to the primitive computational power of the time is an early illustration of Gosper’s gun. At the bottom we see the gun in action, sending out a new glider every thirty generations (here it has sent out two gliders). Since 1970 there have been numerous such “guns” that generate all kinds of forms — some gliders and some stationary oscillators. Naturally, in the latter case, the generator must translate across the grid, leaving its intended stationary debris behind
Summary
Specialized” neighborhoods — e.g. Treat as neighbors only those cells that touch on sides, or touch only the left two corners and nowhere else, or touch anywhere, but the state in our rule that two or more live neighbors of a subject cell must not touch each other, etc. Consider the following rule for finding the next generation. 1. A living cell dies. 2. A dead cell comes to life if and only if its left side touches a live cell. If we start, say, with a single cell we will obtain a “glider” of one cell that moves to the right one cell each generation! Such rules are easy to construct, as are more complex glider-producing positional rules. So we shall not investigate them further.
Tech advancements impact society by shaping communication, commerce, and innovation. As technology evolves, businesses must adapt to meet changing consumer needs and expectations while staying competitive in the market.
From enhancing productivity to providing new avenues for growth,
technology plays a critical role in driving progress and transformation across industries. By embracing digital tools and solutions, companies can revolutionize their operations, streamline processes, and reach a wider audience. In today’s fast-paced digital landscape, staying ahead of the curve is essential for long-term success and sustainability.
