David's Blague

Thanks in part to the Perl 6 Advent Calendar, in part to Ed showing me how easy it was to pop a subversion repo into github, and in part to whim, I dusted off some old Perl6 and got it running under Rakudo.  The gang on #perl6 was smart and fun as always, and to top it all off, there's a butterfly now.  Anyone who wants to see the code, it's on Github.

Labels: cellular automata, perl, perl6, programming

The image to the right was not created using processing. However, it did serve as an inspiration for the latest in my series of natural-looking patterns made with cellular automata and Processing 0135.

My latest masterpiece is called "zebra" and I bet you'll never guess what it looks like. I changed the colors around from "goo" and added a further limit that each pixel can only swap with the pixel horizontally adjacent to itself. I didn't start from scratch, so it's possible there's still some green goo behavior lurking in there somewhere, but the code is included behind that link.

Without further ado, I present zebra. I lifted the zebra image from here on Wikipedia, and it's GFDL, so to be on the fair side, feel free to copy anything in this post under the same terms as that image. Thanks, Miraceti!

(edit: as with previous installments, click to randomize, space-bar to start)

Labels: art, cellular automata, processing, programming

This post is a response to the "high level CPU" challenge found here. If you have comments for the public, post them to your own blog. If you have comments for me, send me an email: dbrunton@gmail.com.

It's hard to know where to start with yosefk's post. Perhaps a different post entirely. His definition of "high-level" is as good a place as any. The adjective high-level has meaning in exactly one context. If the behavior of some system differs significantly from the behavior of components of that system, the behavior of the system is high-level, and the behavior of the component is low-level.

The NAND Gate is a great example of this. A NAND Gate by itself is of limited usefulness- it has two inputs and returns 0 if both inputs are 1 otherwise, 1. Not hugely smart. However, it functionally complete. String together enough of them and you've got yourself a CPU. In other posts, I've called such behavior "emergence" though it's a dubious designation in the case of something engineered as much as such a CPU would need to be. Conway's Game of Life, Wolfram's Rule 30 (maybe), NOR gates, C-NOT gates, there are lots of these. Toffoli's CAM-8 was at least one attempt of fabbing automata theory into hardware.

However, yosefk's high-level CPU challenge included these two sentences: "I have images. I must process those images and find stuff in them." None of the machines in the previous paragraph are going to do that better than your current run-of-the-mill silicon wafer. However, yosefk, if you "process" those images by using your eyeballs to look at them, any semantic meaning you derive from them is "high-level". It cannot be predicted by the behavior of any pixel on the image or any one of the receptors on your retina, yet it's there.

Humanity's failure to replicate this kind of behavior in silicon does not in any way invalidate the architecture, and it may in fact be due in part to the bargain you're striking. Millimeters of Silicon? Hell, maybe you shouldn't even be using silicon!

I digress.

Let us go back to the problem of designing high-level hardware. Presumably, one of the reasons I would undergo such an exercise is for the pure joy of it. But I also think there could be some benefit to the architecture- for instance, high-level hardware might excel at solving problems for which low-level hardware is ill-suited. Or high level hardware might become easier for humans to interact with. Perhaps, high-level hardware will do things we haven't thought of yet (this last said with the understanding that if we haven't thought of them they may not be useful). Perhaps, high level hardware will be much like us- good at some tasks, bad at others, but profoundly interesting in both cases.

I digress again.

Here is the outline of my proposal:

1. High-level hardware is made from identical low-level components.
2. Low-level components:
• communicate with up to eight physically proximate neighbors.
  
• implement a truth table of up to eight bits.
• have a small, fixed memory, set at run time (ROM).
• can remember state over a fixed duration of cycles (RAM).
  
• can compare RAM and ROM bitwise for equality.
• can signal halt.
  
3. High-level language defines :
• the truth table currently in use.
  
• a "topology" for low-level components.
• state for low-level components.
• the halting state for low-level components.
4. An outside actor (e.g. Von Neumann computer) might watch what's going on.
   

Now, reading over this, I guess I've just rewritten a bunch of crap that I've written a lot of times before. It's a cellular automaton, with some cruft around it for deciding if it has done anything useful yet. Since it doesn't seem to have "stuck" in the past few cycles, I'll write some pseudo-code this time, so after I get my demo processor it will have something to do.

truth_table( bits: 3, endian: big, packed: 30)
topology(max cells: 40, neighbors: 2, unique: true)
state(default: 0; singularity: 1)
halting(0b1010000110)
run

This code loosely translated into English-ese:

The truth table takes three bits of input. Arrange all combinations of bits in decreasing sequence, and unpack the integer 30 from the big end to tell you the bit-truth value for each three-bit input. Wolfram rule 30.

Each cell acts as an input to two other cells, and receives input from two other cells. The two must be unique in both cases. Hopefully you can kind of see this makes a "ring" of cells. The ring can be a maximum of 40 cells.

The initial state is all zeros, and one 1. In this case, it doesn't matter where the 1 is, but there is only one (it is a singularity, duh).

If the most recent ten bits of state on any given cell are exactly the halting state, that cell signals halt. It notifies the high-level language of completion, and hopefully the high-level language remembers where the completion occurred.

Now, I have described a single instance of such a machine- and I have just riffed the details out of my big shiny brain. Other people have actually built such machines, and they are perfectly capable of performing particular tasks with faster clock time than good-ol x86 and friends.

I certainly haven't gotten it right, but I also firmly agree with all the huffing and puffing by the "C is for Von Neumann Architecture" crowd. Future programming languages are going to run on high-level hardware, they are going to be extraordinarily compact, they are going to perform very specific tasks for which Von Neumann computers are ill suited, and they're probably going to have some Von Neumann architecture watching them closely, since one of the things they'll be bad at is knowing if and when they got the right answer.

I guess they really are like us.

Labels: cellular automata, cpu, response

So, after reading dchud's post about the last applet, I got thinking about various mash-ups I could, well, mash.

I'm still playing around with some variations on clustering and obstacles (something he mentioned in conversation), but realized I needed to make the original a little bit dumber before making it any smarter. Thus, I have replaced the previous applet's behavior of moving cells that are over the threshold to a random location. Now, instead, they move Brownian style. Any cell over its threshold simply swaps with a random pick of the eight cells adjacent to it.

Interestingly, it results in a whole new class of pictures.

Actually, I adjusted the ratio of green/magenta cells to be exactly equal, and removed the "empty" cells, since theres no need of them in the Brownian motion context.

The results are here.

The applet works the same as the other- click to randomize, space to start. It takes a lot longer to settle into a fully stable state, but there are obvious structures only a few generations in. I think it looks kind of like an ant farm.

Labels: brownian motion, cellular automata, pretty, processing, programming, schelling

I've been getting asked a lot (at least twice) about why this site isn't updated more frequently. There are three reasons, really. The first is that I've been doing a lot of writing with a pencil, on paper. I know, shocking. The second is that I've been doing some work on physical things (e.g. soldering iron, circuits, and wood. Yes, the kind of wood that's made from trees). And the last is that it took me a while to figure out how to put Processing Applets on the site. I know, I'm supposed to be good with computers.

The applet I'm about to show you is inspired by a paper written in 1971 by Thomas Schelling, called Dynamic Models of Segregation. It turns out that Schelling's model is a great example of sociology (in which I have a degree) and cellular automata (about which I have an obsession) working together. I'm hardly the first person to notice this.

The basic gist of the program is: there are green cells, magenta cells, and "vacant" cells (white). Each of the green and magenta cells have what I deemed a "socially acceptable" preference for living nearby one another. Specifically, each green cell wants to be in a neighborhood (defined as the cells within three pixels radius) that is at least 1/3 green. Same goes for magenta. If any cell finds this preference violated, it moves to a random empty cell.

The behavior of the system is totally different than the (expected) behavior of an individual. The system segregates quite nicely into green and magenta regions, with a vacant white border in-between. This phenomenon is called emergence. A system displays emergence if its behavior differs from the behavior of its components. Equally as important as the philosophical lesson this applet can teach, is that it makes pretty pictures.

Click the mouse to randomize the picture, and press the space bar to get it going again. It will run on its own the first time through. If you're running Internet Explorer, you may need to click through a few dire warnings to get Java to run.

Without further ado, the Schelling Applet.

Labels: cellular automata, pretty, processing, programming, schelling, sociology

Up to this point, all the code presented here is running in sequence. This is not, however, by design, so much it is by accident. Theoretically, every cell of a cellular automaton has access to its own tiny little computer (e.g. XOR gate), and it's own tiny little memory (e.g. 2 bits). And when we do that, we can start running them in parallel.

A somewhat more realistic approximation of this theoretical model would be to run enough cells on any given processor to fill up its memory, and to have it communicate without any friction with the adjacent processors.

There is no reason that a few of these babies couldn't run a cellular automaton with a trillion or so cells.

The hardware limitation to what we can effectively learn is rapidly dwindling. The only limitation to how well a curve can be fit is how well the underlying slice correlates to the curve. This is a matter of achieving sufficient parallelism, tweaking our models, and brute-forcing our way through enough cell-space to figure out what classes of data are good fits:

• A game of Rock-Paper-Scissors?
• A really, really random screensaver?
• A Random Walk?
• An encrypted file?
• A compressed data stream?

One of the beauties of this field is that it's not really theoretical- at least not in the sense that math or physics is theoretical. Well, at least theoretical physics. It's practical: either our models will match experimental data, or they won't.

There are open questions worth additional scrutiny.

Should we model using infinite, or finite grids?

What is the optimal structure of grids for various problem sets?

The only way we can find answers to these questions is to dive in and start hacking. If you're interested, email me.

I've now started the questions- if any of you here know the answers, feel free to pop me an email. Otherwise, I've hopefully stimulated a few questions.

Labels: cellular automata, deusexautomatis, etech

Having arrived at Part Six of our series, I am now going to make a rash hypothesis:

The rule we've just described is computationally universal.

Just a hunch, though. Not getting into a proof yet.

Because if it is universal (as some cellular automata have proven to be), who cares? It's probably not a very efficient computer you want to do something like add 2 and 2 together and print the result on a screen. Besides, it doesn't need to be computationally universal to be useful.

So what might we do with such a model?

The short answer to that question is the entire point of my presentation at the emerging technology conference and this series: Fit Curves Better. Particularly curves that equations are bad at.

As a final point of clarification before diving into a bit more code, by "curve" I mean "series of 1's and 0's." As I assume any right-thinking modern programmer would mean by the word. Now on to our curve fitting:

class Fit {
  has Bool $.match     is rw = Bool::False;
  has Int  $.magnitude is rw = 0;

  method fit (:$model, :$sample) {
      if ($model == $sample) {
          $.match = Bool::True;
          $.magnitude++;
      }
      else {
          $.match = Bool::False;
      }
  }
}

This module is dead simple. It simply compares our model (a cellular automaton) to our sample (some so-called "random" data), and increments the variable magnitude if they are the same, and sets $fit.match() to true.

In real life, I don't use a module to do this, but it's easier to explain the principle of it before diving into any more detailed examples. At this point in the talk at ETech, I proceeded to run a script that matched an arbitrary string of 1's and 0's against my cellular automaton. Here's a version of that script:

my Bool @data = <001001000011111101101010100010001000010110100011000>.split("");

use Automaton;
use Fit;
my $diameter = 19;
for (0..$diameter-1) -> $slice {
   my Automaton $ca .= new(:diameter($diameter), :rule(6));  # initialize the CA
   $ca.next() for 0..30;                                    # "seed" the CA
   my Fit $compare .= new();
   for (0..@data.elems-1) -> $stage {
       $compare.fit(:model($ca.grid.state()[$slice]), :sample(@data[$stage]));
       $ca.next;
   }
   my $fit = $compare.magnitude()/@data.elems() * 100;
   say " - Slice $slice fits: " ~ floor($fit) ~ "%";
}

And here's the output of the script (finally!)

- Slice 0 fits: 50%
- Slice 1 fits: 52%
- Slice 2 fits: 47%
- Slice 3 fits: 52%
- Slice 4 fits: 58%
- Slice 5 fits: 52%
- Slice 6 fits: 60%
- Slice 7 fits: 47%
- Slice 8 fits: 49%
- Slice 9 fits: 66%
- Slice 10 fits: 62%
- Slice 11 fits: 66%
- Slice 12 fits: 60%
- Slice 13 fits: 56%
- Slice 14 fits: 64%
- Slice 15 fits: 50%
- Slice 16 fits: 45%
- Slice 17 fits: 50%
- Slice 18 fits: 45%

As you can see, the best fit is about 66%, which is only .16 above what we would expect from matching our arbitrary data to a totally random data set.

So where's the catch?

Tune in for the final segment soon!

Labels: cellular automata, deusexautomatis, etech

In our final segment of Part V, we tie together all the code into a single, cohesive whole, and run it. In the interest of getting it done more quickly, and in a literate programming style, I've noted some of the nice features of Perl 6 in the comments.

A simple Copy/Paste should get this code going for you in Pugs:

use v6-alpha;  # By Christmas, we should be able to say "use v6;"
class Rule {   # See Deus Ex Automatis Part V(a)
   has Int  $.number    is ro;
   has Int  $.neighbors is ro;
   has Bool %.lookup    is rw;
   submethod BUILD (:$.number, :$.neighbors) {
       for ( 0 .. (2 ** $.neighbors -1) ) -> $key {
           my $format = "\%0" ~ $.neighbors ~ "b";
           %.lookup{sprintf($format,$key)} = ?($.number +& (1 ~ 0 x $key) );
       }
   }
}

class Grid {
   has Int  $.diameter is rw;
   has Bool @.state    is rw;

   submethod BUILD (:$.diameter) {
       @.state = 1,;
       @.state.push( 0 xx ($.diameter-1) );
   }
}

class Automaton does Rule does Grid { # "does" gives us a mix-in pattern
   has Rule $.rule is rw; # the "Rule" is a reference to our own class
   has Grid $.grid is rw; # as is Grid

   submethod BUILD (:$diameter, :$rule) { # new() takes two arguments
       $.grid = Grid.new(:$diameter);
       $.rule = Rule.new(:number($rule), :neighbors(2));
   }

   method next { # The "guts" where we apply the rule to the grid
                 # Also, incidentally, our first method !!
       my @old = $.grid.state();
       for ( 0 .. $.grid.diameter-1 ) -> $i {
           $.grid.state[$i] = ~+$.rule.lookup{ @old[$i] ~ @old[$i-1] };
       }
       return Bool::True; # Lets us easily use this in a loop
   }
}

##
# The script!  This will print beautiful cellular automata on your screen.
my Automaton $ca .= new(:diameter(10), :rule(6));
say $ca.grid.state while $ca.next();

Whew!

I may come back later and edit this post to add a bit more commentary. In the meantime, note that this code (in a somewhat complicated, and somewhat slow manner) implements the class of cellular automata we've been discussing through this entire series.

I'm going to move on in the next segment to talking about why it's important.

Labels: cellular automata, deusexautomatis, etech

We've already got code for rules from last post. Now we need a grid.

class Grid {
  has Int  $.diameter is rw;
  has Bool @.state    is rw;

  submethod BUILD (:$.diameter) {
      @.state = 1,;
      @.state.push( 0 xx ($.diameter-1) );
  }
}

Fairly simple, takes one argument: diameter. Building a new grid is done like so:

pugs> my Grid $grid .= new( :diameter(10));
pugs> say $grid.state;
1000000000

Once again, we've taken some shortcuts. The grid code assumes a single dimension, with a second, emergent dimension (often called "time") that happens when you apply the rule.

Now that we've got a rule, and got a grid, we can put them together into a cellular automaton, and discover some more syntactic (and semantic) sugar from Perl 6.

Labels: cellular automata, deusexautomatis, etech

Now (finally!) for some code. I've had a bit of a hard time getting this to format correctly, so if there are problems, pop me an email, and I'll try again.

I have two reasons for presenting examples in Perl 6. Reason number one: Perl 6 is reasonably easy for native English speakers to read, even if you're not a hacker. Reason number two: it's fun.

Hopefully it also does something useful, such as compiling without errors.

class Rule {
 has Int $.neighbors = 2;
 has %.lookup =
  ( '11'=>'0', '10'=>'1', '01'=>'1', '00'=>'0' );
}

This code isn't particularly useful by itself, but if you wanted to try it, just copy and past that code into Pugs, a Perl 6 implementation, and call it like so:

pugs> my Rule $rule .= new();
pugs> say "Rule has $rule.neighbors() neighbors."
Rule has 2 neighbors.

Note that both $.neighbors and %.lookup have not one, but two punctuation marks at the beginning of the word. The first is a sigil. The sigil designates $.neighbor to be a scalar, and %.lookup to be a hash (e.g. lookup table). The second character (both have a period) tells the class to create accessors for each. So we can do things like "$rule.neighbors()"

One of the most satisfying parts of writing code in Perl 6, is that my spell checker doesn't raise a red flag (or underline) for most the code I write.

The code above is totally static, and could really have used just a built-in data structure. Perhaps a more useful rule could accept any number of neighbors (as an argument) and a rule number as are often used in constructing simpler cellular automata. That could be done like so:

class Rule {
 has Int  $.number    is ro;
 has Int  $.neighbors is ro;
 has Bool %.lookup    is rw;

 submethod BUILD (:$.number, :$.neighbors) {
   for ( 0 .. (2 ** $.neighbors -1) ) -> $key {
     my $format = "\%0" ~ $.neighbors ~ "b";
     %.lookup{sprintf($format,$key)} =
       ?($.number +& (1 ~ 0 x $key) );
   }
 }
}

Perl 6 gives us a built-in pretty way to overload the "new" method in a class with "submethod BUILD". What we've done here is add a method that unpacks the Wolfram-style rule into a lookup table when you create a rule.

As an exercise for the reader, here's how to make the same rule we've been talking about all along:

pugs> my Rule $rule .= new(:neighbors(2), :number(6));

Why?

Labels: cellular automata, deusexautomatis, etech

This may be the best thing in the world.

Ever.

Labels: cellular automata

When I got to this stage in the talk at the emerging technology conference, I glossed over a few of the finer points of mechanics, in hopes that diving right into code would be a better way for most the audience to understand what I was talking about. In retrospect, I think I would have been better served to dig a bit deeper into the mechanics, which is what this article will do.

The grid of cells we looked at in yesterday's segment is incomplete. There are cells of the grid that only have a single neighbor- namely those on the right and left. In fact, the top cell has no neighbors at all. Whereas the rule we outlined needs to look at two neighbors.

There are at least a half-dozen ways around this problem.

1. Make the grid of cells big enough that on need never reach the edge.
2. Simulate an infinite grid by doing lazy evaluation at the edges (more on this later).
   
3. "Wrap" each dimension of the grid, making an end neighbors with its opposite.
4. Use a lower-dimensional cellular automaton to specify values on the edges.
5. Assign a static value to every cell on the edge of the grid.
6. Combine one or more of these approaches.
   

It's beyond the scope of this segment to describe the benefits and drawbacks of each method. But method three, which we will use below, does merit a closer look.

Note that I have started with the top cell labeled "A0," I have taken each right-hand neighbor, and when I reached the end, I made the last cell neighborly with the first cell. Think of this as wrapping the grid around on itself.

The cellular automaton now has a new property: diameter.

Which brings us to the all-important question: which kind of grid is simpler- infinite or finite?

Well, who knows? I think the finite grid is simpler, because even though it has a new property (namely, diameter), it's smaller and it's calculable. In addition to that, using this kind of a finite grid causes the cellular automaton we've been discussing here to exhibit interesting properties. If you look again at the previous section, note that even with a diameter of 25, there is a great deal of complexity to the structure.

It may even be universal, in the same sense that Wolfram's Rule 30 and Conway's Game of Life have already been proven to be.

With that last addition to the mechanical overview, we're now going to commit our lengthy explanation into some extraordinarily concise code.

Labels: cellular automata, deusexautomatis, etech

Now for some mechanics.

A cellular automaton is a model. Untangled from all the biological, physical, and mathematical metaphor, cellular automata are simple.

They exist on a grid of cells:


As pictured here, cells are represented by the egg shapes with letters in them. As you may have guessed, the cells give cellular automata the first part of their name. Between the cells are arrows, which declare the "neighborhood" of a cell. A cell's neighbors have arrows pointing into that cell.

Some cellular automata differentiate between one neighbor and another. In this series we'll look at some of each. Note, in passing (don't get hung up on it) that any cellular automaton that does not distinguish between neighbors can be easily represented by one that does. So the former should just be considered a kind of short-cut for the latter.

Inside each cell is exactly one member of a finite set.


Different models use different symbols in the set. 1 and 0 is very common. As is black and white. As long as the set is finite, it can also include more than two symbols.

If you're with me so far, this next piece is the last before we put it all together.

In order to pick which symbol from the finite set a cell should display, the cell examines its neighbors, and only its neighbors, and applies a rule. Programmers think of this rule as code in some programming language, but it can be even simpler than that. Here is an example of a rule:


This rule could be stated in the following casual shorthand: if exactly one of a cell's neighbors is a 1, that cell should be a 1. Otherwise, it should be a 0.

It's important to note that at least one 1200 page book has sold a fair number of copies by pointing out that a very simple rule can generate complexity out of simplicity. Put another way, complexity is simply a feature of some systems, even without entropy or chance.

The rule I just described would yield us output that looks something like this:


And with output like that, who needs a million monkeys typing?

Labels: cellular automata, deusexautomatis, etech

The history of cellular automata is intertwined with the history of computers itself.

It was easy to imagine cool things to do with computers. The emerging technology conference- a talk by Microsoft Labs next-door, another talk by Amazon Web Services out in the courtyard, and only the cool kids here. That's you all- the cook kids.

With a few notable exceptions, everyone decided to ignore cellular automata. Which is why he's often pictured with a computer (notably, the EDVAC), instead of a self-reproducing automaton.

Very few.

Ten or so years after von Neumann's untimely death, his friend Arthur W. Burks published his papers on automata theory. I read the originals. Genius, but clearly unfinished. He was a busy guy. You know, inventing computers and the atomic bomb and game theory.

E.F. Codd- yes, the same E.F. Codd who gave us relational databases- had a brief romance with cellular automata with a simplification of JVN's self-reproducing machine.

And from there, the field exploded, experiencing slow linear growth for another forty years.

John Conway's Game of Life is a cellular automaton that mimics a biological ecology.

Rudy Rucker uses a particularly gnarly class of automata to describe Jellyfish.

Chris Langton made a famous one to describe the way an ant walks, but seems to focus on swarms now.

Thomas Schelling's segregation model was a cellular automaton in all but name.

As was most of Donald Greenspan's 1973 book Discrete Models, featuring a rant about how infinity is un-mathematical.

And we can't forget the preeeeeeetty seeeashells courtesy of Stephen Wolfram.

And all that only took another forty years.

Now that I've given you the history lesson, you all know why I became a computer programmer instead of a historian.

Before closing I should note, in passing, that there have been a steady stream of philosopher-hackers over those forty years, starting with Konrad Zuse's Rechender Raum (translated into English as Calculating Space), who insist that the universe itself is a calculation.

There will be time enough for that later, though.

Labels: cellular automata, deusexautomatis, etech

A cellular automaton, of course, is a kind of discrete model, which as you will see shortly can be a useful thing for hackers. Today's post is the beginning of my O'Reilly Emerging Technology presentation, in a heavily edited version.

I will present the talk in a series of posts, outlining the discovery and history of this kind of model. I'll follow with a mechanical overview of cellular automata, for hackers. Next, a few examples in the fabulous Perl 6 programming language (using Pugs, of course). Last, but not least, I will present the long list of open questions I presented at the end of my talk. These were the start of a Q/A session at the conference, and I hope they will be here as well.

When I gave the talk in San Diego, I started with some witty remarks, facilitated by the poorly functioning A/V system. On the original text of the speech, which I will post with the original slides at the end of these journal entries, I had the following note after my intro:

DRINK, PAUSE, LOOK THOUGHTFUL

So if you can manage that before moving on, take a drink, pause, and look thoughtful.

Cellular Automata.

Really rolls off of the tongue.

John von Neumann (a name you'll hear a lot) established the study of these models as a field. He was, unfortunately for all of us, a native speaker of physics. Worse yet, his second language was Hungarian. He's the one who saddled us with the name.

Cellular Automata.

I first encountered cellular automata about seven years ago, shortly after moving to Washington, DC. Living in Washington affords some advantages for doing research. For instance, our neighborhood library turns out to have every book ever published, and then some.

Because of my proximity to the Library of Congress, when Stephen Wolfram came out of hiding with A New Kind of Science, I wasn't one of the people who had to camp out in front of the bookstore for three days to get one.

I just went down to the library.

But that was just the beginning. If you're planning a visit to Washington, make sure to send me an email. I'll take you on the cellular automatour. The real treasure trove is in the Library of Congress manuscript reading room. John von Neumann left his papers- published and unpublished- to the library when he died.

Which you can just ask for.

Wow.

The letters between Stanislaw Ulam and John von Neumann are a great starting point. The two probably should be credited as co-founders of the field. Sanislaw Ulam had a great deal of affection for von Neumann, always calling him "Johnny". His letters were full of practical advice, grand plans, and occasional favors he would ask of von Neumann.

John von Neumann inevitably wrote back something utterly banal.

"Don't you owe me fifty cents?" Of course that was 1947. Fifty cents was a lot of money then.

Which brings me to my next point. If this is a sixty-year-old field, why was I giving a presentation at an Emerging Technology conference one week ago? Tune in tomorrow to find out!

Labels: cellular automata, deusexautomatis, etech, history

The talk in San Diego is come and gone, and it was incredible fun. Thanks to all of you who posted materials, emailed me, posted on your blogs, and came to the talk.

I had a great time.

I learned things.

For instance, that the title for my talk, had I used the ablative correctly, would have been Deus Ex Automatis. File that under things I never would have known.

The slides are linked above. The text of the talk, I'll be trickling out in segments here on my online journal. The first segment, this afternoon, will be my "historical" introductions. Lucky for you all, I'm no more historian than I am Latin scholar.

Labels: cellular automata, etech, software, technology

While rehearsing for my presentation at the Emerging Tech conference, it came clear to me that the term "cellular automata" is in that awful, yet oddly ubiquitous class of scientific terms that explain exactly nothing to the lay person.

I am all for obfuscation when it serves some purpose, but in this particular case, the term doesn't do much for hackers, either. Lacking a PhD, I can't speak for them, but the only purpose I can imagine such a term would serve, is to make the speaker sound "really smart" (read: like a pompous ass). The term was coined by a guy whose first language was abstract math, with Hungarian as a close second- not exactly the poster children of clarity.

Here is where I've arrived so far. It still needs polish:

A cellular automaton is a graph, with each node (cell) on the graph containing exactly one member of a finite set (value). The state of the model is completely specified by the values of each cell. The value of a cell is updated by applying a rule to the values of its neighboring cells.

My objection to other descriptions I read are not entirely overcome by my own description. I have used the words "graph" and "node" from graph theory, and implied the word "vertex" without using it by using the phrase "neighboring cells."

Not perfect.

But better than some. My big objections to other descriptions is that they include too much math, physics, or biology to be considered generally useful abstractions. After all, one of my favorite models in this class is from a social scientist.

Labels: cellular automata, discrete models, etech, graph theory