automata

Pattern manipulation with Cellular Automata.

Cellular Automata are defined here by a ruleset (a table of individual CA rules). Each rule consists of two parts. Firstly a neighbourhood that the rule acts on. Secondly a rule signature specifying the conditions under which cells are Born (B) or Survive (S). These rule signatures are initialised with a string in the "Golly" format. i.e a rule which activates cells with one neighbour and deactivates cells with two would have the rule string "B1/S2". The neighbourhood is specified by an instance of the forma.neighbourhood class as usual.

Once a ruleset is specified, there are two provided implementations of a CA. Firstly the standard synchronous CA is implemented in automata.iterate whereby all cells are updated simultaneously. Secondly an asynchronous update is provided in automata.async_iterate in which each iteration updates only one cell at random.

When a ruleset consists of only one rule, the CA is unambiguous and is applied in the conventional manner. When multiple rules are provided, rule conflicts are resolved in favour of cell deactivation. For example, if there are two rules in the set, cell activation requires that the candidate cell passes the 'birth' criterion of both rules. Cell deactivation requires only that one 'survive' criterion fails.

All CA updates here are only possible on a finite domain of cells. That domain must be specified as a pattern in the iteration call.

Both the synchronous and asynchronous iterations return the result of one CA iteration and a bool specifying whether or not the iteration has converged to a stable pattern.

automata.rule

Define a cellular automata rule. CA rules in forma are defined by a neighbourhood in the usual CA sense and a string signature in the 'Golly' format (BXX/SXX). This function initialises a rule, and performs a few consistency checks.

-- Initialise a rule corresponding to Conway's Game of Life
local gol_rule = automata.rule(neighbourhood.moore(), "B3/S23")

Parameters:

Name	Type	Description
nbh	forma.neighbourhood	specifying the neighbourhood the rule is to be applied in
rule_string	string	specifying the ruleset (i.e B23/S1)

Returns:

• table — a verified rule for use with the CA methods

automata.iterate

Synchronous cellular automata iteration. Performs one standard synchronous CA update on pattern prevp in the specified domain.

-- Domain and initial state (500 seed points) for the CA
local domain = primitives.square(100)
local ca_pat = pattern.sample(domain, 500)
-- Repeat iteration until convergence is reached
local converged = false
repeat
    ca_pat, converged = automata.iterate(ca_pat, domain, {gol_rule})
until converged == true

Parameters:

Name	Type	Description
prevp	forma.pattern	the previous iteration of the pattern
domain	forma.pattern	the cells in which the CA operates
ruleset	table[]	a table of forma.rules defining the CA

Returns:

• forma.pattern — the result of the CA iteration
• boolean — true if converged, false otherwise

automata.async_iterate

Asynchronous cellular automata iteration. Performs a CA update on one cell (chosen randomly) in the specified domain. This corresponds to a 'random independent scheme' update.

-- Domain and initial state (10 seed points) for the CA
local domain = primitives.square(10)
local ca_pat = pattern.sample(domain, 10)
local rng    = math.random
-- Repeat iteration until convergence is reached
local converged = false
repeat
    ca_pat, converged = automata.async_iterate(ca_pat, domain, {gol_rule}, rng)
until converged == true

Parameters:

Name	Type	Description
prevp	forma.pattern	the previous iteration of the pattern
domain	forma.pattern	the cells in which the CA operates
ruleset	table[]	a table of forma.rules defining the CA
rng	(fun(m: integer):integer)?	a random number generator (syntax as per math.random)

Returns:

• forma.pattern — the result of the CA iteration
• boolean — true if converged, false otherwise