Lambda value of (outer-)totalistic code
bob...@mail.com
How to compute lambda value for (outer-)totalistic rule?
Is it the same way like computing for elementary?
I'm asking because the totalistic codes aren't so big numbers
(in e.g. r=2) and I don't know if small changes of rule can exhibits
lambda.
Ilmari Karonen
>
> How to compute lambda value for (outer-)totalistic rule?
> Is it the same way like computing for elementary?
If I remember the usual definition of lambda correctly, then yes,
except that you need to weigh the outcomes from different numbers of
active neighbors according to the number of elementary neighborhood
configurations they correspond to.
So, for example, if you have an outer totalistic automaton with 4
neighbors in addition to the center cell, then there will obviously be
only one configuration where the number of live neighbors is 0, but 4
possibilities for the number to be 1 (any of the four can be the live
one), 6 for it to be 2 (any two of them can be live), 4 for it to be 3
and one for it to be 4.
Those numbers are simply the binomial coefficients; if you're not
familiar with them (one can never tell on Usenet), look them up on the
net or in a math book (try one on basic combinatorics).
--
Ilmari Karonen
To reply by e-mail, please replace ".invalid" with ".net" in address.
bob...@mail.com
translate it to the general rule and compute lambda by normal way.
Ok. I tried it and it works! But what if we increase number of states?
I think that binomical coeficients aren't working for k>2
And now the tricky part:)
What about vice versa? (How to create random totalistic rule according
to lambda?)
Translate general rule to totalistic rule isn't possible in some
cases.
I saw some web links to program "lambda CA" at santafe.edu (the full
url was http://alife.santafe.edu/cgi-bin/caweb/lambda.cgi). This
program was probably doing exactly what I'm looking for, but the URL
doesn't exists anymore.
Do you know anything about it?
Ilmari Karonen
> So, you tell that for compute lambda for totalistic rule we have to
> translate it to the general rule and compute lambda by normal way.
>
> Ok. I tried it and it works! But what if we increase number of states?
> I think that binomical coeficients aren't working for k>2
If I've got my combinatorics right, I think you need to compute the
number of ways to assign the cells in each state to the remaining
unassigned cells, and multiply these together. That is, if you have,
say, eight neighbors and three states, with n neighbors in state 1, m
in state 2 and the rest in state 3, the weight would be:
(8 choose n)*(8-n choose m)
where (x choose y) is the binomial coefficient with x over y (the
usual notation being hard to transcribe in an ASCII-only medium).
More generally, if you have N total neighbors, of which n_j are in
state j, 1 <= j <= k, then the number of general configurations
corresponding to that totalistic neigborhood is:
(N choose n_1) * (N-n_1 choose n_2) * (N-n_1-n_2 choose n_3)
* ... * (N-n_1-n_2-...-n_{k-2} choose n_{k-1})
(The order of numbering the states shouldn't matter, and you don't
actually need to stop at n_{k-1}; going on to n_k just adds an extra
term equal to 1.)
> And now the tricky part:)
> What about vice versa? (How to create random totalistic rule according
> to lambda?)
The problem essentially reduces to picking, out of a given set of
tickets with numbers on them, a random combination that sums to a
desired value.
In the strict sense, this problem may not _have_ a solution (there may
be no rule with the exact value of lambda you want), and even if it
does, I'm not sure there's a better way than enumerating all the
combinations with the desired sum (fortunately, one does not have to
enumerate all the _possible_ combinations to do this) and then picking
one at random. And that's assuming that a uniform distribution over
the applicable combinations is in fact what one means by random.
However, if one simply wants a rule with _approximately_ a given value
of lambda, then a simpler method suggests itself: starting with a rule
with lambda=0, pick a random (semi)totalistic neighborhood, set its
outcome to a non-zero value, adjust lambda appropriately and repeat
until it reaches the desired value.
An efficient way to do the random picking is to list all the possible
neighborhoods, shuffle the list (with, say, the Fisher-Yates shuffle
algorithm) and pick in the order of the shuffled list. It's even
possible to modify the Fisher-Yates shuffle to do an "on-demand
shuffle", such that it stops as soon as you have enough neighborhoods
to reach the desired lambda. Also, for target lambda > 0.5, it may be
better to start with a random lambda=1 rule and work downwards.
(Anyway, around this point it should start becoming obvious that
lambda, as usually defined, is a really crude "zeroth-order"
approximation to the mean-field behavior of a rule, such that picking
a rule with _exactly_ a desired value of lambda rarely matters much.
Actually, I think it _might_ be possible to adapt the scheme I
outlined above to pick rules with approximately a given mean-field (or
cluster) density, but the computation, of course, gets more complex.)
bob...@mail.com
I want to do is:
to learn how to create rule that fits in particular Wolfram's class.
How I can see the lambda is complicated. But is there anything less
complicated?
Anyway thanks for your answers!
Ilmari Karonen
> Well, I can see the discussion is starting to be difficult. The thing
> I want to do is:
> to learn how to create rule that fits in particular Wolfram's class.
That's indeed a difficult exercise, given that the classes themselves
aren't all that rigorously defined. Especially so if you're aiming
for the elusive class 4. Lambda can indeed be a useful, if crude,
predictor of a rule's behavior, but just getting the right value of
lambda won't guarantee that you'll get a class-4 rule. Unfortunately,
I'm not aware of any approach that would, so, as far as I know, you'll
just have to satisfy yourself with various approaches to generating
rules that _might_ be in a particular class more probably than a
completely randomly chosen one would.
One observation that seems to generally hold true is that class-4
rules tend to exist along the boundary between classes 2 and 3 by most
measures. So one approach would indeed be to choose some measure,
such as lambda, by which classes 2 and 3 tend to differ, and to try to
generate rules that fall between those classes by that measure. Not
all, or perhaps even most, of them would be in the desired class, but
perhaps some would.
One such measure would indeed be lambda. Its main attraction is its
simplicity, and the perhaps even surprisingly high predictive value it
does have _despite_ that simplicity. Going to slightly more complex
measures, the next one would be the mean-field density of the rule:
this is essentially just a refined variation of lambda, accounting for
the fact that, say, the outcome of a neighborhood full of live cells
should not be given much weight if the rule is unlikely to produce so
many live cells to begin with.
(The mean-field density of a general 2-state rule is a solution to the
equation d = sum(d^k * (1-d)^(n-k)), where the sum is taken over all
neighborhoods that yield a live cell, k is the number of live cells in
the neighborhood and n the neighborhood size; you might note that
replacing d with 1/2 on the right-hand side would simply give you an
expression for lambda. There may be several solutions, including
trivial ones at d=0 and/or d=1 if either of the states is quiescent;
we specifically want the one(s) that are stable against small
perturbations. If you don't like solving equations, simply starting
at d=1/2 and iterating the expression a few times ought to _usually_
give you pretty good convergence, but actually soving the equation
analytically may yield more insight than mere number crunching.)
Another, more dynamic approach might be to start with a random rule,
do some statistical testing to guess which class it belongs in, and
then mutate it, using the chosen measure to pick the direction of the
mutation so that it changes the measure towards class 3 if the current
rule is class 1 or 2 and vice versa. That way, one might hope that
the rule would converge towards the boundary, and perhaps class 4, as
it evolves. With this approach there is little difference between
lambda and the mean-field density -- both increase when the outcome of
a neighborhood changes from dead to live and vice versa -- though the
latter will allow you to better estimate the degree of change
resulting from changing the outcome of a particular neighborhood.
Going further in the direction from lambda to the mean-field
approximation, we first get the pair approximation, which is the same
thing but accounts for pairwise correlations between cells, and then
even higher-order cluster approximations. Which these all capture the
behavior of a rule even better than the mean-field approximation, the
problem becomes one of interpretation; while simply looking at the
density of live cells will easily tell class 1 from class 3, telling
classes 2 and 3 apart will require more careful examination of the
results. Such higher-order approximations will also be even more
complicated to work with.
Alternatively, assuming one in fact has a not just a qualitative but a
quantitative statistical test for evaluating how chaotic a rule is,
one might dispense with external approximations entirely and go for a
full stochastic hill-climbing approach, simply generating random
mutations and discarding those that take the rule further from the
boundary, essentially using the test itself as the guiding measure.
Also, there are other ways, which I'm less familiar with, of locating
CA rules that may be likely to exhibit interesting behavior. One that
I've read of but haven't really looked very deeply into is comparing
the rule with a linearized version of it: IIRC, there seems to be some
tendency for class-4 rules to be close variants of linear rules such
as the elementary rule 90. If you'd like to look deeper into this,
you could try googling for, say, "boolean derivatives on cellular
automata". (That's the title of a 1990 paper by G. Vichniac, but
there are other search results as well.)
I might also recommend the book _Cellular Automata: Theory and
experiment_ by Howard Gutowitz (ed., 1991). Apparently it's at least
partially available on Google Books, if your local library doesn't
happen to have a convenient copy. Of course, there have likely been
further developments in the field since, seeing as the book's getting
old enough to drink in some places, but I at least found it rather
informative, if dense, reading, and much of it deals with just the
subject you seem to be interested in. If nothing else, it might be a
useful starting point.
(Ps. Sorry for the long and dense post. I wanted to give you as many
leads as I could, subject to the limits of my own knowledge, which
rather inevitably resulted in a somewhat rambling braindump. Feel
free to skip any parts you're not interested in, and please let me
know if you'd like me to try explaining something more clearly.)
bob...@mail.com
What I want to do is really program some algorithm for finding class
4.
Using just a lambda obviously don't help.
I'm really interested in that you wrote in paragraph 5. But there is
the problem
with analysing. How to find out that it belongs or not.
Another difficult question! How am I doing this?:)
bob...@mail.com
Automata by finding gliders.
But I still think that it have to be really difficult to implement
even brutus force.
Ilmari Karonen
Well, I just googled for "automatic classification of cellular
automata", and some interesting links did come up, including this
discussion:
http://forum.wolframscience.com/archive/topic/1085-1.html
and this paper:
http://www.ccs.neu.edu/home/kunkle/docs/caClassification.pdf
I'm sure others here more familiar with the field could give you more
pointers.
bob...@mail.com
Thank you and I'll write there later.
Dave Greene
This question has come up a number of times recently. I suppose it
depends partly on what definition of "class 4" you want.
If you're going with the original definition -- "Evolution leads to
complex localized structures, sometimes long-lived." -- then you can
probably pick a sample size and workable definitions for "complex" and
"long-lived", and come up with a (somewhat arbitrary) automatic
classification scheme.
But trying to validate Wolfram's later speculation that "class 4
automata are characterized by the capability for universal
computation"... well, that's really just a huge CA engineering
problem. In fact, it's a separate huge problem for each candidate
rule. Seems as if it would be impossible to prove a lot of rules to
be *not* class-4 -- discovery of a few new structures could set you on
the road to universal computation at any time.
David Eppstein's summary page --
http://www.ics.uci.edu/~eppstein/ca/wolfram.html
-- was enough to convince me not to expect "class 4" to be well-
defined, or at least decidable, for 2D CAs in general.
Keep the cheer,
Dave Greene