- A Merkle with fewer than two neighbors dies from loneliness and disappears from the next generation.
- A Merkle with two or three neighbors lives on to the next generation.
- A Merkle with more than three neighbors dies from overcrowding.
- Any empty cell with exactly three live neighbors grows a Merkle.
For us databases guys, we know that this is where Dr. Codd started before he invented the Relational Model. If you want to read it, you can download it at http://ebookee.org/E-F-Codd-Cellular-Automata_2164601.html.
Did you ever hear of the an economist Thomas C. Schelling? He created a simple artificial neighborhood to study a generation ago. His observation was how real segregated neighborhoods behaved in his day.
His model world is a square grid and the citizens are either Red Merkles or Blue Merkles. Every square has a Merkle living there. We fill Merkleville randomly with an equal number Red Merkles and Blues. Dr. Schelling did not use a computer when he started playing with this model, but we have an advantage over him today.
We need a happiness rule for Merkleville. This rule is simpler than Life; every Merkle wakes up and looks North, South, East and West to see his neighbors. If he is in a corner or on a edge, do a wrap-round, making Merkle-world a torus. If a Merkle exits to the right, it reappears on the left, and if it exits at top, it reappears on the bottom.
Now, we need a the happiness rule. A Merkle is happy only if its four neighbors (this is called an Ulam neighborhood) include at least (n) Merkle of his own color. Any two unhappy Merkles can swap, if they both increase or maintain their happiness. There is no cost to moving, no restrictive covenants, no neighborhood associations (aka “Lawn Nazis”) or other examples of nosy neighbors running your life. This is a pure abstract model.
This actually gives us a way to model the net happiness of Merkleville by summing the score of all the Merkles. Another cute programming exercise!
We could start with ‘colorists’ Merkles that want to live in pure district where (n = 4) district. Very quickly, Red Merkles gravitate to solid red districts, and Blue Merkles gravitate to solid blue districts. Once the districts are established, the border between the districts shifts a little as Red Merkles and blue Merkles jockey to move away from the boundary. This feels right, so it is not a great surprise.
Let’s do some “Affirmatively Furthering Fair Housing” in this model. Let’s program perfectly tolerant Merkles who seek only ( n < = 2 ) neighbors of his own color. This is the Department of Housing and Urban Development’s magical population of Merkles who are free of any desire for segregation and discrimination. They seek an integrated district, half red, half blue. My Merkles seek mathematically pure diversity without a Federal Marshal pointing a gun at them or any economic restrictions.
Write and run your program. The individual preferences of your Merkles will produce a collective outcome indistinguishable from a colorist housing policy. The differences are the speed that it takes to get to the segregation.
You get discernible colored clusters, then the boundaries harden. The Merkles would be perfectly happy to be in the minority; they want only to avoid being completely alone.
You can see some QuickTime animations of Merkleville at these sites:
For (n = 2)
For (n = 1)