David's Blague

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