Interesting behaviour with probabilistic automata?

For discussion of other cellular automata.
Post Reply
ivtb
Posts: 11
Joined: January 21st, 2018, 6:07 pm

Interesting behaviour with probabilistic automata?

Post by ivtb » May 18th, 2018, 1:28 am

In Stephen Wolfram's A New Kind of Science, it is explained that most automata appear to be classifiable in four broad categories:

- Class 1 automata settle down into a homogenous state independently of the initial conditions

- Class 2 automata rapidly settle down into predictable patterns, either static or oscillating

- Class 3 Automata show expanding growth of apparently random activity from small initial patterns

- And class 4 automata behave unpredictably, with some patterns growing and others not, and patterns interacting in complex ways.

One thing he noticed was that in his list of elementary automata, class 4 automata would often be appear between class 3 and class 2, as if lying in the boundary between chaos and order.

Although thousands of life-like automata exist, a great majority of them falls in the first 3 categories, and only a handful of them appear to lie in this elusive boundary where interesting behaviour appears.

With non-totalistic CA, we were able manipulate automata to a finer degree of granularity, creating many variations of very similar automata, so we could "tame" automata by tipping them to either side of chaotic or orderly behaviour.

If we had a better way to fine-tune automata, we could produce much more class-4 behaviour. By using a probabilistic automata, we are essentially interpolating a variety of rules, but instead of a discrete range we have an entire continuous range of parameters to test.

An implementation could choose, for each cell, a totalistic rule from a set with some fixed probability. Or we could extend conway's notation with probabilities:

B2(.02)3(.90)/S2(.90)3

Here, an off cell with two neighbours has 2% probability of becoming an on cell, and 90% if it has three neighbours instead, whereas a live cell has 90% probability of being live in the next generation if it has 2 neighbours, or 100% if it has 3.

EDIT:

I just made a couple of Python programs using the NumPy library implementing probabilistic CA:

Code: Select all

def pstep(X, *rule_sheet):
    
    """Receives as arguments pairs (rule, probability) where rule is a pair
    describing a totalistic automaton, as in ((3,),(2,3)) for CGoL."""
    
    nbrs_count = sum(np.roll(np.roll(X, i, 0), j, 1)
        for i in (-1, 0, 1) for j in (-1, 0, 1) if (i != 0 or j != 0))
    
    result = np.zeros(X.shape)
    
    for rule, probability in rule_sheet:
        for birth_count in rule[0]:
            result += probability * ((1-X) & (nbrs_count == birth_count))
        for survival_count in rule[1]:
            result += probability * (X & (nbrs_count == survival_count))
    
    return (result > np.random.random_sample(result.shape)).astype(int)

Code: Select all

def pstep2(X, p_rule):
    
    """Receives as arguments a pair (B,S), where B and S are tuples of pairs (n,p) meaning
    the probability of births or survival, p, given the number, n, of neighbors"""
    
    nbrs_count = sum(np.roll(np.roll(X, i, 0), j, 1)
        for i in (-1, 0, 1) for j in (-1, 0, 1) if (i != 0 or j != 0))
    
    result = (
        sum(probability * ((1-X) & (nbrs_count == birth_count))
            for birth_count, probability in p_rule[0]) +
        sum(probability * ((X) & (nbrs_count == survival_count))
            for survival_count, probability in p_rule[1])
            )
    
    return (result > np.random.random_sample(result.shape)).astype(int)
Note that before using this code you have to import NumPy as np.
Last edited by ivtb on May 18th, 2018, 2:14 pm, edited 2 times in total.

User avatar
KittyTac
Posts: 535
Joined: December 21st, 2017, 9:58 am

Re: Interesting behaviour with probabilistic automata?

Post by KittyTac » May 18th, 2018, 1:35 am

The thing is, any large pattern would be ruined eventually, and stable patterns would be impossible.

User avatar
77topaz
Posts: 1496
Joined: January 12th, 2018, 9:19 pm

Re: Interesting behaviour with probabilistic automata?

Post by 77topaz » May 18th, 2018, 1:52 am

Yeah, you can't really engineer anything if the CA doesn't behave deterministically (Except at maybe a really large scale, analogous to how real-life engineering works despite Heisenberg uncertainty and other effects of quantum mechanics because the scale is much larger than those effects. But, that would probably require an unfeasibly-large-to-simulate scale - you're effectively getting into statistical mechanics at that point.)

ivtb
Posts: 11
Joined: January 21st, 2018, 6:07 pm

Re: Interesting behaviour with probabilistic automata?

Post by ivtb » May 18th, 2018, 2:27 am

We are used to the fixed points of deterministic automata: Patterns that reproduce themselves exactly in a fixed number of generations. If we transport a Life pattern to a probabilistic automaton it will likely not work for long.

But what if a probabilistic mechanism opens up pathways for engineering that do not exist in deterministic ones? With a much more larger set of transitions to explore, many patterns will turn out to be equivalent, and a given set of patterns may be so closely connected that a pattern in the set almost always maps to another pattern in it, for example.

What would pop out if we ran a probabilistic automaton for a very long time?

Post Reply