Monthly Archives: November 2010

The Surprising Truth About Cellular Automata and You

Cellular automata is a way of modeling complex systems by focusing on simple, independent entities called automatons. These automatons are not simple by design but rather by definition; because they are each a tiny, tiny part of a massive system, and because the number of possible interactions between these automatons rises exponentially with each automaton added to the system, there is no possible way that a single automaton can possibly understand the complexity of its own system.

Here’s are some of the things a cellular automaton DOES know:

  • It knows what it wants. An automaton is independent and has goals of its own that it wishes to satisfy.
  • It interacts with the world. This varies depending on the model of the system and the goals of the automaton, but often an automaton will consume resources, attempt to obtain more, and may expel waste.
  • It interacts with other automata. I originally wrote “its neighbors” but “neighbor” is too restricted a term. An automaton may communicate with automata at great distances, or may receive summaries of the behavior of groups of automata, in much the same way that you or I can send an email or watch the news.
  • It has a staggering amount of hubris. The automaton cannot possibly understand the system in which it lies, but in spite of this limitation, it will attempt to interact with the world and other automata and attempt to achieve its goals.

The complexities of the system are beautiful and staggering. Readers of “The Land of Lisp” will recognize this example: consider a world in which resources are scarce everywhere except in a tight jungle area, where resources are very rich. Now consider an automaton which has only one choice in life: to move straight ahead or turn. The automaton consumes a resource if it finds one, and it will die if it goes for too many turns without finding a resource. Each automaton will have a random tendency towards turning or going straight. Now let’s say that every so often, the surviving automata create offspring with tendencies similar to its own.

In even this simple an example, the automata will VERY quickly–in just a few dozen generations–specialize into two different species. One species adapts to living in the jungle. It almost always turns, trying to keep itself from wandering away from the jungle. The other species almost always goes straight, trying to cover as much distance as possible to find resources in the desert.

With regard to the title of this post, that’s “The Suprising Truth About Cellular Automata”. What about the “And You” part?

Take a deep breath, and reread the rules of cellular automata. Now turn your head and look out the window. Stare off into the distance and think for a long time. Now say these words aloud:

“This is why I don’t understand politics or economics.”

Of course, the hubris rule still applies. Just because we don’t understand it, doesn’t mean we aren’t going to try and it definitely doesn’t mean we’re not going to manipulate it. But for me, this is a perfectly adequate explanation for why economic theory makes so much sense on paper and yet the world economy can be in the tank. It explains why I get offended when someone reminds me to unit test my code, even while my unit tests reveal so many defects in my code.

The scale of complexity explains why terrorist bombings and economic collapse don’t necessarily have to be the work of conspiracies, and hubris explains why I would much rather believe that they are. Conversely, hubris explains why campaigning politicians look good denouncing the ails of the system, and complexity explains why incumbent politicians look incompetent trying to fix them.

Palindromic Powers of Two

Huh, that’s odd.

Just farting around, reducing the set of Integers to their prime factors—typically Friday-night stuff, amirite?—and I noticed an interesting pattern.

  1. Start with a keyspace of 0 and all of the integers in order as your available keys.
  2. Write a 0.
  3. You’ve exhausted the keyspace, so get another key, 1.
  4. Write the entire series so far, add the new key, and write the series (minus the new key) again. You should have 010.
  5. You’ve exhausted the keyspace again, so get another key, 2.
  6. Repeat: 010, 2, 010 -> 0102010.
  7. Repeat with 3: 010201030102010.
  8. Repeat with 4: 0102010301020104010201030102010.

And so on.

The “Huh!” moment is this: you’re writing the exponent of two in the prime factorization of the list of integers:

1 20
2 21
3 20 * 3
4 22
5 20 * 5
6 21 * 3
7 20
8 23
9 20 * 32
10 21 * 5
11 20
12 22 * 3
13 20
14 21 * 7
15 20 * 3 * 5
16 24