Automata

Automata: elementary, life-like, noisy, and group automata, turmites, linear automata, and subshifts.

AntCellElement(label, visual=None, *, color=0, ant=-1)

Bases: Element

Cell of Langton's ant: a color, and the heading of the ant on it or -1.

The local rule of langtons_ant turns the ant right on a white cell and left on a black one, flips the cell's color, and moves the ant one cell forward.

Parameters:

Name	Type	Description	Default
label	str	The label of the cell or the lattice group.	required
visual	VisualSpec | None	How the element is drawn, or None for default_visual_.	None
color	Annotated[float, StateSpec(domain=FiniteEnumeratedSet([0, 1]))]	The initial color, 0 for white and 1 for black.	0
ant	Annotated[float, StateSpec(domain=ZZ)]	The initial heading of an ant on the cell, 0 to 3 for north, east, south, and west, or -1 for none.	-1

Examples:

>>> from skcomplex.models.computer_science.automata import AntCellElement
>>> AntCellElement('cell').ant
-1

Source code in src/skcomplex/models/computer_science/automata/_automata.py

def __init__(
    self,
    label: str,
    visual: VisualSpec | None = None,
    *,
    color: Annotated[float, StateSpec(domain=FiniteEnumeratedSet([0, 1]))] = 0,
    ant: Annotated[float, StateSpec(domain=ZZ)] = -1,
) -> None:
    super().__init__(label, visual=visual)
    self.color = color
    self.ant = ant

Automaton(space, neighborhood, rule, states=2) dataclass

Cellular automaton on a finite universe: a periodic lattice, a finite quotient of a group, or a ball.

The automaton maps a configuration, one integer value from 0 to states - 1 per site, to the configuration whose value at every site is the rule applied to the values of the neighbourhood of the site, as LocalRuleLaws do. Sites outside a lattice with fixed edges or outside a ball read the fill value of the space.

Parameters:

Name	Type	Description	Default
space	BaseSpace	The lattice or the group space.	required
neighborhood	Reach	The neighbourhood of offsets on a lattice, or the memory set on a group space.	required
rule	object	A TableSpec, a TotalisticSpec rule, an OuterTotalisticSpec rule, an object whose table() returns a TableSpec, or a function of one array per neighbour that returns the next values.	required
states	int	The number of values of a cell.	2

Examples:

>>> from skcomplex.specs import TotalisticSpec
>>> from skcomplex.core.spaces import BoxNeighborhood, LatticeSpace
>>> from skcomplex.models.computer_science.automata import Automaton
>>> parity = Automaton(LatticeSpace(5), BoxNeighborhood(), TotalisticSpec(lambda total: total % 2))
>>> parity.step([0, 0, 1, 0, 0]).tolist()
[0, 1, 1, 1, 0]

reads property

Neighbourhood the rule reads, with the site itself first for an outer totalistic rule.

size property

Number of sites.

local_map()

Return the next value of every pattern of the cells the rule reads, indexed by the code of the pattern.

Returns:

Name	Type	Description
values	IntArray	One integer value per pattern.

Raises:

Type	Description
ValidationError	The rule returns a value outside 0 to states - 1.

Source code in src/skcomplex/models/computer_science/automata/_automaton.py

def local_map(self) -> IntArray:
    """Return the next value of every pattern of the cells the rule reads, indexed by the code of the pattern.

    Returns:
        values:
            One integer value per pattern.

    Raises:
        ValidationError:
            The rule returns a value outside `0` to `states - 1`.
    """
    patterns = _patterns(self.states, _count(self.reads))
    values = np.asarray(self._evaluate(patterns), dtype=float)
    if values.size and (values.min() < 0 or values.max() >= self.states or not np.all(values == np.rint(values))):
        error_msg = f'The rule returns values outside the integers 0 to {self.states - 1}.'
        raise ValidationError(error_msg)
    return values.astype(np.int64)

run(configuration, steps)

Return the configurations of a number of steps, the initial one first.

Parameters:

Name	Type	Description	Default
configuration	ArrayLike	The initial values of the sites.	required
steps	int	The number of steps.	required

Returns:

Name	Type	Description
configurations	IntArray	One row per step.

Source code in src/skcomplex/models/computer_science/automata/_automaton.py

def run(self, configuration: npt.ArrayLike, steps: int) -> IntArray:
    """Return the configurations of a number of steps, the initial one first.

    Args:
        configuration:
            The initial values of the sites.

        steps:
            The number of steps.

    Returns:
        configurations:
            One row per step.
    """
    rows = [np.asarray(configuration, dtype=np.int64)]
    for _ in range(steps):
        rows.append(self.step(rows[-1]))
    return np.stack(rows)

step(configuration)

Return the image of a configuration, or of one configuration per row.

Parameters:

Name	Type	Description	Default
configuration	ArrayLike	The values of the sites, or one row of values per configuration.	required

Returns:

Name	Type	Description
image	IntArray	The next values, of the same shape.

Source code in src/skcomplex/models/computer_science/automata/_automaton.py

def step(self, configuration: npt.ArrayLike) -> IntArray:
    """Return the image of a configuration, or of one configuration per row.

    Args:
        configuration:
            The values of the sites, or one row of values per configuration.

    Returns:
        image:
            The next values, of the same shape.
    """
    values = np.asarray(configuration, dtype=np.int64)
    fill = np.full((*values.shape[:-1], 1), int(getattr(self.space, 'fill', 0)), dtype=np.int64)
    padded = np.concatenate([values, fill], axis=-1)
    return self.local_map()[_codes(padded[..., self.table()], self.states)]

table()

Return the site of every cell the rule reads at every site, with the number of sites outside the space.

Returns:

Name	Type	Description
table	Indices	One row per site and one column per cell of reads.

Source code in src/skcomplex/models/computer_science/automata/_automaton.py

def table(self) -> Indices:
    """Return the site of every cell the rule reads at every site, with the number of sites outside the space.

    Returns:
        table:
            One row per site and one column per cell of `reads`.
    """
    return _table(self.space, self.reads)

BinaryCellElement(label, visual=None, *, alive=0)

Bases: Element

Cell of an automaton whose state alive is 0 or 1, changed by the local rule of an interaction.

Parameters:

Name	Type	Description	Default
label	str	The label of the cell or the lattice group.	required
visual	VisualSpec | None	How the element is drawn, or None for default_visual_.	None
alive	Annotated[float, StateSpec(domain=FiniteEnumeratedSet([0, 1]))]	The initial value, 0 or 1.	0

Examples:

>>> from skcomplex.models.computer_science.automata import BinaryCellElement
>>> BinaryCellElement('cell', alive=1).alive
1

Source code in src/skcomplex/models/computer_science/automata/_binary_cell.py

def __init__(
    self,
    label: str,
    visual: VisualSpec | None = None,
    *,
    alive: Annotated[float, StateSpec(domain=FiniteEnumeratedSet([0, 1]))] = 0,
) -> None:
    super().__init__(label, visual=visual)
    self.alive = alive

DiffusionCellElement(label, visual=None, *, level=0.0, r=0.1)

Bases: Element

Cell of a lattice with a content and the share of the difference it exchanges with each neighbour in a step.

Parameters:

Name	Type	Description	Default
label	str	The label of the cell or the lattice group.	required
visual	VisualSpec | None	How the element is drawn, or None for default_visual_.	None
level	Annotated[float, StateSpec(domain=closed_open(0, oo))]	The initial content.	0.0
r	Annotated[float, ParameterSpec(domain=closed_open(0, oo))]	The share of the difference with a neighbour exchanged in a step, below 1 / (2 d) in d dimensions.	0.1

Examples:

>>> from skcomplex.models.computer_science.automata import DiffusionCellElement
>>> DiffusionCellElement('cell', r=0.2).r
0.2

Source code in src/skcomplex/models/computer_science/automata/_diffusion_cell.py

def __init__(
    self,
    label: str,
    visual: VisualSpec | None = None,
    *,
    level: Annotated[float, StateSpec(domain=RealSet.closed_open(0, oo))] = 0.0,
    r: Annotated[float, ParameterSpec(domain=RealSet.closed_open(0, oo))] = 0.1,
) -> None:
    super().__init__(label, visual=visual)
    self.level = level
    self.r = r

LaplacianCellElement(label, visual=None, *, value=0, modulus=3)

Bases: Element

Cell of an automaton over the field of a prime number of elements, such as the discrete Laplacian on a ring.

Parameters:

Name	Type	Description	Default
label	str	The label of the cell or the lattice group.	required
visual	VisualSpec | None	How the element is drawn, or None for default_visual_.	None
value	Annotated[float, StateSpec(domain=ZZ)]	The initial value, an integer from 0 to modulus - 1.	0
modulus	Annotated[float, ParameterSpec(domain=open(0, oo))]	The prime size of the field.	3

Examples:

>>> from skcomplex.models.computer_science.automata import LaplacianCellElement
>>> LaplacianCellElement('cell').modulus
3

Source code in src/skcomplex/models/computer_science/automata/_group_automata.py

def __init__(
    self,
    label: str,
    visual: VisualSpec | None = None,
    *,
    value: Annotated[float, StateSpec(domain=ZZ)] = 0,
    modulus: Annotated[float, ParameterSpec(domain=RealSet.open(0, oo))] = 3,
) -> None:
    super().__init__(label, visual=visual)
    self.value = value
    self.modulus = modulus

LinearAutomaton(space, neighborhood, coefficients, field='GF(2)') dataclass

Linear cellular automaton, the element sum_s a_s s of the group ring K[G] acting on configurations.

The value at the site g becomes sum_s a_s x(g s) over the field, for every element s of the neighbourhood with its coefficient a_s. On a finite universe it is a square matrix, and injectivity, surjectivity, and pre-injectivity all hold exactly when the matrix is invertible. On Z^d it is a Laurent polynomial, invertible when it is a monomial and surjective when it is not zero.

Parameters:

Name	Type	Description	Default
space	BaseSpace	The periodic lattice or the group space of a finite group or quotient.	required
neighborhood	Reach	The neighbourhood of offsets on a lattice, or the memory set on a group space.	required
coefficients	Sequence[float]	The coefficient of every element of the neighbourhood, integers or rationals.	required
field	str	'GF(p)' for the field of a prime number p of elements, or 'QQ' for the rationals.	'GF(2)'

Examples:

>>> from skcomplex.core.spaces import LatticeNeighborhood, LatticeSpace
>>> from skcomplex.models.computer_science.automata import LinearAutomaton
>>> rule90 = LinearAutomaton(LatticeSpace(6), LatticeNeighborhood(((-1,), (1,))), (1, 1), 'GF(2)')
>>> rule90.step([0, 0, 1, 0, 0, 0]).tolist()
[0, 1, 0, 1, 0, 0]

laurent_polynomial()

Return the Laurent polynomial sum a_s x^s of an automaton on a lattice, its symbol on Z^d.

Returns:

Name	Type	Description
polynomial	LaurentPolynomial	The Sage Laurent polynomial in the variables x0 to x(d-1).

Raises:

Type	Description
ValidationError	The neighbourhood is not one of offsets.

Source code in src/skcomplex/models/computer_science/automata/_linear_automaton.py

def laurent_polynomial(self) -> LaurentPolynomial:
    """Return the Laurent polynomial `sum a_s x^s` of an automaton on a lattice, its symbol on `Z^d`.

    Returns:
        polynomial:
            The Sage Laurent polynomial in the variables `x0` to `x(d-1)`.

    Raises:
        ValidationError:
            The neighbourhood is not one of offsets.
    """
    if not isinstance(self.neighborhood, LatticeNeighborhood):
        error_msg = 'A Laurent polynomial describes a linear automaton on a lattice, with offsets.'
        raise ValidationError(error_msg)
    field = self._field()
    offsets = self.neighborhood.check().prepare().offsets_
    n_dim = len(offsets[0])
    ring = LaurentPolynomialRing(field, [f'x{axis}' for axis in range(n_dim)])
    variables = ring.gens()
    terms = (
        field(QQ(coefficient)) * np.prod([variable**step for variable, step in zip(variables, offset, strict=True)])
        for offset, coefficient in zip(offsets, self.coefficients, strict=True)
    )
    return sum(terms, ring.zero())

matrix()

Return the matrix of the automaton over the field, whose row g gives the image at g.

Returns:

Name	Type	Description
matrix	Matrix	The Sage matrix.

Raises:

Type	Description
ValidationError	A site reads a cell outside the space.

Source code in src/skcomplex/models/computer_science/automata/_linear_automaton.py

def matrix(self) -> Matrix:
    """Return the matrix of the automaton over the field, whose row `g` gives the image at `g`.

    Returns:
        matrix:
            The Sage matrix.

    Raises:
        ValidationError:
            A site reads a cell outside the space.
    """
    table = _table(self.space, self.neighborhood)
    if (table >= _size(self.space)).any():
        error_msg = 'A linear automaton has a matrix on a periodic lattice or a finite group, not on a ball.'
        raise ValidationError(error_msg)
    field = self._field()
    entries = matrix(field, _size(self.space), _size(self.space))
    for site, row in enumerate(table.tolist()):
        for neighbour, coefficient in zip(row, self.coefficients, strict=True):
            entries[site, neighbour] += field(QQ(coefficient))
    return entries

step(configuration)

Return the image of a configuration.

Parameters:

Name	Type	Description	Default
configuration	ArrayLike	The values of the sites.	required

Returns:

Name	Type	Description
image	NDArray[generic]	The next values, reduced modulo the field size over a prime field.

Source code in src/skcomplex/models/computer_science/automata/_linear_automaton.py

def step(self, configuration: npt.ArrayLike) -> npt.NDArray[np.generic]:
    """Return the image of a configuration.

    Args:
        configuration:
            The values of the sites.

    Returns:
        image:
            The next values, reduced modulo the field size over a prime field.
    """
    table = _table(self.space, self.neighborhood)
    values = np.append(np.asarray(configuration), getattr(self.space, 'fill', 0))
    image = values[table] @ np.asarray(self.coefficients)
    characteristic = int(self._field().characteristic())
    return np.rint(image).astype(np.int64) % characteristic if characteristic else image

NoisyElementaryCellElement(label, visual=None, *, alive=0, noise=0.01)

Bases: BinaryCellElement

Binary cell that holds the probability that the output of its local rule is flipped.

Parameters:

Name	Type	Description	Default
label	str	The label of the cell or the lattice group.	required
visual	VisualSpec | None	How the element is drawn, or None for default_visual_.	None
alive	float	The initial value, 0 or 1.	0
noise	Annotated[float, ParameterSpec(domain=closed_open(0, oo))]	The probability that the output of the rule is flipped.	0.01

Examples:

>>> from skcomplex.models.computer_science.automata import NoisyElementaryCellElement
>>> NoisyElementaryCellElement('cell', noise=0.1).noise
0.1

Source code in src/skcomplex/models/computer_science/automata/_noisy_elementary_cell.py

def __init__(
    self,
    label: str,
    visual: VisualSpec | None = None,
    *,
    alive: float = 0,
    noise: Annotated[float, ParameterSpec(domain=RealSet.closed_open(0, oo))] = 0.01,
) -> None:
    super().__init__(label, visual=visual, alive=alive)
    self.noise = noise

PascalCellElement(label, visual=None, *, value=0)

Bases: Element

Cell of an automaton over the nonnegative integers.

Parameters:

Name	Type	Description	Default
label	str	The label of the cell or the lattice group.	required
visual	VisualSpec | None	How the element is drawn, or None for default_visual_.	None
value	Annotated[float, StateSpec(domain=NN)]	The initial value, a nonnegative integer.	0

Examples:

>>> from skcomplex.models.computer_science.automata import PascalCellElement
>>> PascalCellElement('cell', value=3).value
3

Source code in src/skcomplex/models/computer_science/automata/_pascal_cell.py

def __init__(
    self,
    label: str,
    visual: VisualSpec | None = None,
    *,
    value: Annotated[float, StateSpec(domain=NN)] = 0,
) -> None:
    super().__init__(label, visual=visual)
    self.value = value

Subshift(neighborhood, forbidden, states=2) dataclass

Subshift of finite type: the configurations in which no forbidden pattern appears around any site.

A pattern is a tuple of values in the order of a neighbourhood. It appears at a site when the cells of the neighbourhood of the site hold its values, and patterns that reach outside a space are not checked, so a lattice with fixed edges holds the words of a window.

Parameters:

Name	Type	Description	Default
neighborhood	Reach	The neighbourhood of offsets on a lattice, or the memory set on a group space, that patterns cover.	required
forbidden	Sequence[tuple[int, ...]]	The forbidden patterns.	required
states	int	The number of values of a cell.	2

Examples:

>>> from skcomplex.core.spaces import LatticeNeighborhood, LatticeSpace
>>> from skcomplex.models.computer_science.automata import Subshift
>>> golden = Subshift(LatticeNeighborhood(((0,), (1,))), [(1, 1)])
>>> golden.count(LatticeSpace(6, boundary='fixed'))
21

count(space)

Return the number of admissible configurations of a space, by dynamic programming over its sites.

The sites are assigned in order, and the counts of completions are shared between assignments that agree on the earlier sites that later patterns read, so a window of a one-dimensional subshift costs linear time.

Parameters:

Name	Type	Description	Default
space	BaseSpace	The lattice or the group space, a window of the subshift.	required

Returns:

Name	Type	Description
count	int	The number of configurations without a forbidden pattern.

Source code in src/skcomplex/models/computer_science/automata/_subshift.py

def count(self, space: BaseSpace) -> int:
    """Return the number of admissible configurations of a space, by dynamic programming over its sites.

    The sites are assigned in order, and the counts of completions are shared between assignments that agree on
    the earlier sites that later patterns read, so a window of a one-dimensional subshift costs linear time.

    Args:
        space:
            The lattice or the group space, a window of the subshift.

    Returns:
        count:
            The number of configurations without a forbidden pattern.
    """
    table, complete = self._complete(space)
    forbidden = {tuple(int(item) for item in pattern) for pattern in self.forbidden}
    checks: list[list[int]] = [[] for _ in range(_size(space))]
    for site in np.flatnonzero(complete):
        checks[int(table[site].max())].append(int(site))
    needed = [
        tuple(
            sorted(
                {int(cell) for later in checks[site:] for anchor in later for cell in table[anchor] if cell < site},
            ),
        )
        for site in range(_size(space) + 1)
    ]
    values = [0] * _size(space)
    memo: dict[tuple[int, tuple[int, ...]], int] = {}

    def extend(site: int) -> int:
        """Return the number of admissible completions of the values before a site."""
        if site == _size(space):
            return 1
        key = (site, tuple(values[cell] for cell in needed[site]))
        if key not in memo:
            total = 0
            for value in range(self.states):
                values[site] = value
                if all(tuple(values[cell] for cell in table[anchor]) not in forbidden for anchor in checks[site]):
                    total += extend(site + 1)
            memo[key] = total
        return memo[key]

    return extend(0)

is_admissible(configuration, space)

Check whether no forbidden pattern appears in a configuration.

Parameters:

Name	Type	Description	Default
configuration	ArrayLike	The values of the sites.	required
space	BaseSpace	The lattice or the group space.	required

Returns:

Name	Type	Description
admissible	bool	Whether the configuration belongs to the subshift.

Source code in src/skcomplex/models/computer_science/automata/_subshift.py

def is_admissible(self, configuration: npt.ArrayLike, space: BaseSpace) -> bool:
    """Check whether no forbidden pattern appears in a configuration.

    Args:
        configuration:
            The values of the sites.

        space:
            The lattice or the group space.

    Returns:
        admissible:
            Whether the configuration belongs to the subshift.
    """
    return not self.violations(configuration, space).any()

sample(space, sweeps=100, *, initial=None, random_state=None)

Return an admissible configuration drawn by a Markov chain of single-cell moves that keep it admissible.

Parameters:

Name	Type	Description	Default
space	BaseSpace	The lattice or the group space.	required
sweeps	int	The number of sweeps, each proposing a random value at every site in a random order.	100
initial	ArrayLike | None	The admissible initial configuration, or None for every cell at 0.	None
random_state	int | Generator | None	The seed or generator of the moves.	None

Returns:

Name	Type	Description
configuration	IntArray	The admissible configuration.

Raises:

Type	Description
ValidationError	The initial configuration is not admissible.

Source code in src/skcomplex/models/computer_science/automata/_subshift.py

def sample(
    self,
    space: BaseSpace,
    sweeps: int = 100,
    *,
    initial: npt.ArrayLike | None = None,
    random_state: int | np.random.Generator | None = None,
) -> IntArray:
    """Return an admissible configuration drawn by a Markov chain of single-cell moves that keep it admissible.

    Args:
        space:
            The lattice or the group space.

        sweeps:
            The number of sweeps, each proposing a random value at every site in a random order.

        initial:
            The admissible initial configuration, or `None` for every cell at 0.

        random_state:
            The seed or generator of the moves.

    Returns:
        configuration:
            The admissible configuration.

    Raises:
        ValidationError:
            The initial configuration is not admissible.
    """
    rng = np.random.default_rng(random_state)
    values = (
        np.zeros(_size(space), dtype=np.int64) if initial is None else np.asarray(initial, dtype=np.int64).copy()
    )
    if not self.is_admissible(values, space):
        error_msg = 'The initial configuration holds a forbidden pattern. Give an admissible one.'
        raise ValidationError(error_msg)
    table, complete = self._complete(space)
    touching: list[list[int]] = [[] for _ in range(_size(space))]
    for anchor in np.flatnonzero(complete):
        for cell in set(table[anchor].tolist()):
            touching[cell].append(int(anchor))
    forbidden = {tuple(int(item) for item in pattern) for pattern in self.forbidden}
    for _ in range(sweeps):
        for site in rng.permutation(_size(space)):
            previous = values[site]
            values[site] = rng.integers(self.states)
            if any(tuple(values[table[anchor]].tolist()) in forbidden for anchor in touching[site]):
                values[site] = previous
    return values

violations(configuration, space)

Return the sites at which a forbidden pattern appears.

Parameters:

Name	Type	Description	Default
configuration	ArrayLike	The values of the sites.	required
space	BaseSpace	The lattice or the group space.	required

Returns:

Name	Type	Description
violations	NDArray[bool_]	One flag per site.

Source code in src/skcomplex/models/computer_science/automata/_subshift.py

def violations(self, configuration: npt.ArrayLike, space: BaseSpace) -> npt.NDArray[np.bool_]:
    """Return the sites at which a forbidden pattern appears.

    Args:
        configuration:
            The values of the sites.

        space:
            The lattice or the group space.

    Returns:
        violations:
            One flag per site.
    """
    table, complete = self._complete(space)
    values = np.append(np.asarray(configuration, dtype=np.int64), 0)
    codes = _codes(values[table], self.states)
    return complete & np.isin(codes, self._forbidden_codes())

Wolfram(number) dataclass

Elementary cellular automaton by its Wolfram number, on the left, centre, and right cells.

A local rule takes it as its rule and reads it through table().

Parameters:

Name	Type	Description	Default
number	int	The rule number from 0 to 255.	required

Examples:

>>> from skcomplex.models.computer_science.automata import Wolfram
>>> Wolfram(30).table().mapping[(1, 0, 0)]
1

table()

Return the rule as a table of the eight patterns.

Returns:

Name	Type	Description
table	TableSpec	The table.

Raises:

Type	Description
ValueError	The number is outside 0 to 255.

Source code in src/skcomplex/models/computer_science/automata/_codes.py

def table(self) -> TableSpec:
    """Return the rule as a table of the eight patterns.

    Returns:
        table:
            The table.

    Raises:
        ValueError:
            The number is outside 0 to 255.
    """
    if not 0 <= self.number < ELEMENTARY_RULES:
        error_msg = f'A Wolfram rule number is between 0 and 255, but it is {self.number}.'
        raise ValueError(error_msg)
    patterns = itertools.product((0, 1), repeat=3)
    return TableSpec(
        {pattern: (self.number >> (4 * pattern[0] + 2 * pattern[1] + pattern[2])) & 1 for pattern in patterns},
    )

baumslag_solitar(m=1, n=2)

Return the Baumslag-Solitar group BS(m, n) = <a, t | t a^m t^-1 = a^n>.

Its balls are built from a confluent rewriting system, which Knuth-Bendix completion finds for BS(1, n).

Parameters:

Name	Type	Description	Default
m	int	The exponent of a conjugated by t.	1
n	int	The exponent it is conjugated to.	2

Returns:

Name	Type	Description
group	GapElement	The finitely presented GAP group.

Examples:

>>> from skcomplex.models.computer_science.automata import baumslag_solitar
>>> from skcomplex.core.spaces import CayleySpace
>>> CayleySpace(baumslag_solitar(), ball=1).check().prepare().generators_
('a', 't')

Source code in src/skcomplex/models/computer_science/automata/_groups.py

def baumslag_solitar(m: int = 1, n: int = 2) -> GapElement:
    """Return the Baumslag-Solitar group `BS(m, n) = <a, t | t a^m t^-1 = a^n>`.

    Its balls are built from a confluent rewriting system, which Knuth-Bendix completion finds for `BS(1, n)`.

    Args:
        m:
            The exponent of `a` conjugated by `t`.

        n:
            The exponent it is conjugated to.

    Returns:
        group:
            The finitely presented GAP group.

    Examples:
        >>> from skcomplex.models.computer_science.automata import baumslag_solitar
        >>> from skcomplex.core.spaces import CayleySpace
        >>> CayleySpace(baumslag_solitar(), ball=1).check().prepare().generators_
        ('a', 't')
    """
    free = libgap.FreeGroup(['a', 't'])
    a, t = free.GeneratorsOfGroup()
    return free / [t * a**m * t**-1 * a**-n]

baumslag_solitar_automaton(m=1, n=2, *, radius=6, density=0.5, random_state=0)

Return the majority automaton on a ball of the Baumslag-Solitar group BS(m, n), of exponential growth.

Every cell reads itself and the cells at a, a^-1, t, and t^-1, and takes the majority value. The ball is built from a confluent rewriting system of the presentation, which GAP finds for BS(1, n).

Parameters:

Name	Type	Description	Default
m	int	The exponent of a conjugated by t.	1
n	int	The exponent it is conjugated to.	2
radius	int	The radius of the ball.	6
density	float	The probability that a cell starts at 1.	0.5
random_state	int | Generator | None	The seed or generator of the initial cells.	0

Returns:

Name	Type	Description
system	System	The model, with the cells cells.alive.

Examples:

>>> from skcomplex.models.computer_science.automata import baumslag_solitar_automaton
>>> baumslag_solitar_automaton(radius=2).elements[0].check().prepare().size_
17

Source code in src/skcomplex/models/computer_science/automata/_group_automata.py

@register_model(
    field='computer_science/automata',
    tags=('group', 'cellular automaton', 'majority', 'solvable'),
    references=('Ceccherini-Silberstein and Coornaert 2023', 'Baumslag and Solitar 1962'),
    defaults={'until': 20, 'dt': 1},
    observables=_density_observables,
)
def baumslag_solitar_automaton(
    m: int = 1,
    n: int = 2,
    *,
    radius: int = 6,
    density: float = 0.5,
    random_state: int | np.random.Generator | None = 0,
) -> System:
    """Return the majority automaton on a ball of the Baumslag-Solitar group `BS(m, n)`, of exponential growth.

    Every cell reads itself and the cells at `a`, `a^-1`, `t`, and `t^-1`, and takes the majority value. The ball is
    built from a confluent rewriting system of the presentation, which GAP finds for `BS(1, n)`.

    Args:
        m:
            The exponent of `a` conjugated by `t`.

        n:
            The exponent it is conjugated to.

        radius:
            The radius of the ball.

        density:
            The probability that a cell starts at 1.

        random_state:
            The seed or generator of the initial cells.

    Returns:
        system:
            The model, with the cells `cells.alive`.

    Examples:
        >>> from skcomplex.models.computer_science.automata import baumslag_solitar_automaton
        >>> baumslag_solitar_automaton(radius=2).elements[0].check().prepare().size_
        17
    """
    space = CayleySpace(baumslag_solitar(m, n), ball=radius)
    return _majority_system(
        space,
        GeneratorNeighborhood(space.check().prepare().generators_),
        density,
        random_state,
    )

diffusion_automaton(shape=(50, 50), *, r=0.1, width=10)

Return a cellular automaton of diffusion, c' = c + r Σ (c_neighbour - c), started from a square of ones.

The total content is conserved on the torus, and the square spreads into a Gaussian bump.

Parameters:

Name	Type	Description	Default
shape	Sequence[int]	The number of rows and columns of the torus.	(50, 50)
r	float	The share of the difference with a neighbour exchanged in a step.	0.1
width	int	The side of the central square of cells that start with content 1.	10

Returns:

Name	Type	Description
system	System	The model, with the contents cells.level.

Examples:

>>> from skcomplex.models.computer_science.automata import diffusion_automaton
>>> float(diffusion_automaton((20, 20), width=4).elements[0].values['level'].sum())
16.0

Source code in src/skcomplex/models/computer_science/automata/_variants.py

@register_model(
    field='computer_science/automata',
    tags=('lattice', 'diffusion', 'conservation'),
    references=('Downey 2018',),
    defaults={'until': 100, 'dt': 1},
)
def diffusion_automaton(shape: Sequence[int] = (50, 50), *, r: float = 0.1, width: int = 10) -> System:
    """Return a cellular automaton of diffusion, `c' = c + r Σ (c_neighbour - c)`, started from a square of ones.

    The total content is conserved on the torus, and the square spreads into a Gaussian bump.

    Args:
        shape:
            The number of rows and columns of the torus.

        r:
            The share of the difference with a neighbour exchanged in a step.

        width:
            The side of the central square of cells that start with content 1.

    Returns:
        system:
            The model, with the contents `cells.level`.

    Examples:
        >>> from skcomplex.models.computer_science.automata import diffusion_automaton
        >>> float(diffusion_automaton((20, 20), width=4).elements[0].values['level'].sum())
        16.0
    """
    level = np.zeros(tuple(shape))
    rows, columns = (shape[0] - width) // 2, (shape[1] - width) // 2
    level[rows : rows + width, columns : columns + width] = 1.0
    return System(
        elements=[
            LatticeElement(
                'cells',
                element=DiffusionCellElement,
                space=LatticeSpace(tuple(shape)),
                values={'level': level, 'r': r},
            ),
        ],
        interactions=[
            LocalRuleInteraction(
                'diffusion',
                target='cells',
                state='level',
                rule=_diffuse,
                neighborhood=VonNeumannNeighborhood(center=True),
            ),
        ],
    )

elementary_automaton(rule=30, *, size=101, initial=None)

Return an elementary cellular automaton by its Wolfram number, started from a single live cell by default.

Parameters:

Name	Type	Description	Default
rule	int	The Wolfram number from 0 to 255.	30
size	int	The number of cells of the ring.	101
initial	Sequence[float] | None	The initial cells, or None for a single live cell in the middle.	None

Returns:

Name	Type	Description
system	System	The model, with the cells cells.alive.

Examples:

>>> from skcomplex.models.computer_science.automata import elementary_automaton
>>> elementary_automaton(90, size=11).elements[0].check().prepare().size_
11

Source code in src/skcomplex/models/computer_science/automata/_automata.py

@register_model(
    field='computer_science/automata',
    tags=('lattice', 'elementary', 'chaos'),
    references=('Wolfram 1983', 'Charbonneau 2017'),
    defaults={'until': 100, 'dt': 1},
)
def elementary_automaton(rule: int = 30, *, size: int = 101, initial: Sequence[float] | None = None) -> System:
    """Return an elementary cellular automaton by its Wolfram number, started from a single live cell by default.

    Args:
        rule:
            The Wolfram number from 0 to 255.

        size:
            The number of cells of the ring.

        initial:
            The initial cells, or `None` for a single live cell in the middle.

    Returns:
        system:
            The model, with the cells `cells.alive`.

    Examples:
        >>> from skcomplex.models.computer_science.automata import elementary_automaton
        >>> elementary_automaton(90, size=11).elements[0].check().prepare().size_
        11
    """
    values = np.zeros(size) if initial is None else np.asarray(initial, dtype=float)
    if initial is None:
        values[size // 2] = 1.0
    return System(
        elements=[
            LatticeElement('cells', element=BinaryCellElement, space=LatticeSpace(size), values={'alive': values}),
        ],
        interactions=[
            LocalRuleInteraction(
                'rule',
                target='cells',
                state='alive',
                rule=Wolfram(rule),
                neighborhood=BoxNeighborhood(),
            ),
        ],
    )

free_group(rank=2)

Return the free group of a rank, generated by a, b, and so on.

Parameters:

Name	Type	Description	Default
rank	int	The number of generators, from 1 to 26.	2

Returns:

Name	Type	Description
group	GapElement	The free group, a GAP group.

Raises:

Type	Description
ValidationError	The rank is not between 1 and 26.

Examples:

>>> from skcomplex.models.computer_science.automata import free_group
>>> from skcomplex.core.spaces import CayleySpace
>>> CayleySpace(free_group(3), ball=1).check().prepare().generators_
('a', 'b', 'c')

Source code in src/skcomplex/models/computer_science/automata/_groups.py

def free_group(rank: int = 2) -> GapElement:
    """Return the free group of a rank, generated by `a`, `b`, and so on.

    Args:
        rank:
            The number of generators, from 1 to 26.

    Returns:
        group:
            The free group, a GAP group.

    Raises:
        ValidationError:
            The rank is not between 1 and 26.

    Examples:
        >>> from skcomplex.models.computer_science.automata import free_group
        >>> from skcomplex.core.spaces import CayleySpace
        >>> CayleySpace(free_group(3), ball=1).check().prepare().generators_
        ('a', 'b', 'c')
    """
    if not 1 <= rank <= len(string.ascii_lowercase):
        error_msg = f'The rank of a free group is between 1 and 26, but it is {rank}.'
        raise ValidationError(error_msg)
    return libgap.FreeGroup(list(string.ascii_lowercase[:rank]))

free_group_automaton(rank=2, *, radius=6, density=0.5, random_state=0)

Return the majority automaton on a ball of the free group, a tree in which every cell follows its neighbours.

Every cell reads itself and the cells at its generators and their inverses, and takes the majority value, so the random start freezes into blocks of agreeing cells. Cells on the boundary count only their neighbours inside the ball.

Parameters:

Name	Type	Description	Default
rank	int	The number of generators.	2
radius	int	The radius of the ball.	6
density	float	The probability that a cell starts at 1.	0.5
random_state	int | Generator | None	The seed or generator of the initial cells.	0

Returns:

Name	Type	Description
system	System	The model, with the cells cells.alive.

Examples:

>>> from skcomplex.models.computer_science.automata import free_group_automaton
>>> free_group_automaton(radius=3).elements[0].check().prepare().size_
53

Source code in src/skcomplex/models/computer_science/automata/_group_automata.py

@register_model(
    field='computer_science/automata',
    tags=('group', 'cellular automaton', 'majority', 'free group'),
    references=('Ceccherini-Silberstein and Coornaert 2023',),
    defaults={'until': 20, 'dt': 1},
    observables=_density_observables,
)
def free_group_automaton(
    rank: int = 2,
    *,
    radius: int = 6,
    density: float = 0.5,
    random_state: int | np.random.Generator | None = 0,
) -> System:
    """Return the majority automaton on a ball of the free group, a tree in which every cell follows its neighbours.

    Every cell reads itself and the cells at its generators and their inverses, and takes the majority value, so the
    random start freezes into blocks of agreeing cells. Cells on the boundary count only their neighbours inside the
    ball.

    Args:
        rank:
            The number of generators.

        radius:
            The radius of the ball.

        density:
            The probability that a cell starts at 1.

        random_state:
            The seed or generator of the initial cells.

    Returns:
        system:
            The model, with the cells `cells.alive`.

    Examples:
        >>> from skcomplex.models.computer_science.automata import free_group_automaton
        >>> free_group_automaton(radius=3).elements[0].check().prepare().size_
        53
    """
    space = CayleySpace(free_group(rank), ball=radius)
    return _majority_system(
        space,
        GeneratorNeighborhood(space.check().prepare().generators_),
        density,
        random_state,
    )

game_of_life(shape=(100, 100), *, density=0.3, initial=None, born=(3,), survive=(2, 3), random_state=0)

Return Conway's Game of Life, or another life-like rule, on a torus.

Parameters:

Name	Type	Description	Default
shape	Sequence[int]	The number of rows and columns.	(100, 100)
density	float	The probability that a cell starts alive, when no initial cells are given.	0.3
initial	ArrayLike | None	The initial cells, an array of the shape, or None for random cells.	None
born	Sequence[int]	The numbers of live neighbours that bring a dead cell to life.	(3,)
survive	Sequence[int]	The numbers of live neighbours that keep a live cell alive.	(2, 3)
random_state	int | Generator | None	The seed or generator of the random initial cells.	0

Returns:

Name	Type	Description
system	System	The model, with the cells cells.alive.

Examples:

>>> from skcomplex.models.computer_science.automata import game_of_life
>>> game_of_life((20, 30)).elements[0].check().prepare().size_
600

Source code in src/skcomplex/models/computer_science/automata/_automata.py

@register_model(
    field='computer_science/automata',
    tags=('lattice', 'life', 'emergence'),
    references=('Gardner 1970', 'Downey 2018'),
    defaults={'until': 100, 'dt': 1},
)
def game_of_life(
    shape: Sequence[int] = (100, 100),
    *,
    density: float = 0.3,
    initial: npt.ArrayLike | None = None,
    born: Sequence[int] = (3,),
    survive: Sequence[int] = (2, 3),
    random_state: int | np.random.Generator | None = 0,
) -> System:
    """Return Conway's Game of Life, or another life-like rule, on a torus.

    Args:
        shape:
            The number of rows and columns.

        density:
            The probability that a cell starts alive, when no initial cells are given.

        initial:
            The initial cells, an array of the shape, or `None` for random cells.

        born:
            The numbers of live neighbours that bring a dead cell to life.

        survive:
            The numbers of live neighbours that keep a live cell alive.

        random_state:
            The seed or generator of the random initial cells.

    Returns:
        system:
            The model, with the cells `cells.alive`.

    Examples:
        >>> from skcomplex.models.computer_science.automata import game_of_life
        >>> game_of_life((20, 30)).elements[0].check().prepare().size_
        600
    """
    values = _random_cells(shape, density, random_state) if initial is None else np.asarray(initial, dtype=float)
    space = LatticeSpace(tuple(shape))
    return System(
        elements=[LatticeElement('cells', element=BinaryCellElement, space=space, values={'alive': values})],
        interactions=[
            LocalRuleInteraction(
                'rule',
                target='cells',
                state='alive',
                rule=life(born, survive),
                neighborhood=MooreNeighborhood(),
            ),
        ],
    )

grigorchuk_automaton(*, radius=8, density=0.5, random_state=0)

Return the majority automaton on a ball of the Grigorchuk group, a group of intermediate growth.

Every cell reads itself and the cells at the generators a, b, c, and d, all of order 2, and takes the majority value. The ball of radius 8 holds 271 sites, and cells on its boundary count only their neighbours inside it.

Parameters:

Name	Type	Description	Default
radius	int	The radius of the ball.	8
density	float	The probability that a cell starts at 1.	0.5
random_state	int | Generator | None	The seed or generator of the initial cells.	0

Returns:

Name	Type	Description
system	System	The model, with the cells cells.alive.

Examples:

>>> from skcomplex.models.computer_science.automata import grigorchuk_automaton
>>> grigorchuk_automaton(radius=3).elements[0].check().prepare().size_
23

Source code in src/skcomplex/models/computer_science/automata/_group_automata.py

@register_model(
    field='computer_science/automata',
    tags=('group', 'cellular automaton', 'majority', 'intermediate growth'),
    references=('Ceccherini-Silberstein and Coornaert 2023', 'Grigorchuk 1984'),
    defaults={'until': 20, 'dt': 1},
    observables=_density_observables,
)
def grigorchuk_automaton(
    *,
    radius: int = 8,
    density: float = 0.5,
    random_state: int | np.random.Generator | None = 0,
) -> System:
    """Return the majority automaton on a ball of the Grigorchuk group, a group of intermediate growth.

    Every cell reads itself and the cells at the generators `a`, `b`, `c`, and `d`, all of order 2, and takes the
    majority value. The ball of radius 8 holds 271 sites, and cells on its boundary count only their neighbours
    inside it.

    Args:
        radius:
            The radius of the ball.

        density:
            The probability that a cell starts at 1.

        random_state:
            The seed or generator of the initial cells.

    Returns:
        system:
            The model, with the cells `cells.alive`.

    Examples:
        >>> from skcomplex.models.computer_science.automata import grigorchuk_automaton
        >>> grigorchuk_automaton(radius=3).elements[0].check().prepare().size_
        23
    """
    return _majority_system(CayleySpace(grigorchuk_group(), ball=radius), GRIGORCHUK_MEMORY, density, random_state)

grigorchuk_group()

Return the Grigorchuk group, of intermediate growth, as the automaton group of its action on the binary tree.

The generators act by the wreath recursion a = (1, 1)(0 1), b = (a, c), c = (a, d), d = (1, b). The group is amenable, not finitely presented, and its balls grow faster than any polynomial and slower than any exponential.

Returns:

Name	Type	Description
group	GapElement	The GAP automaton group of the AutomGrp package.

Examples:

>>> from skcomplex.models.computer_science.automata import grigorchuk_group
>>> from skcomplex.core.spaces import CayleySpace
>>> CayleySpace(grigorchuk_group(), ball=1).check().prepare().generators_
('a', 'b', 'c', 'd')

Source code in src/skcomplex/models/computer_science/automata/_groups.py

def grigorchuk_group() -> GapElement:
    """Return the Grigorchuk group, of intermediate growth, as the automaton group of its action on the binary tree.

    The generators act by the wreath recursion `a = (1, 1)(0 1)`, `b = (a, c)`, `c = (a, d)`, `d = (1, b)`. The group is
    amenable, not finitely presented, and its balls grow faster than any polynomial and slower than any exponential.

    Returns:
        group:
            The GAP automaton group of the AutomGrp package.

    Examples:
        >>> from skcomplex.models.computer_science.automata import grigorchuk_group
        >>> from skcomplex.core.spaces import CayleySpace
        >>> CayleySpace(grigorchuk_group(), ball=1).check().prepare().generators_
        ('a', 'b', 'c', 'd')
    """
    libgap.LoadPackage('automgrp')
    return libgap.AutomatonGroup(GRIGORCHUK_RECURSION)

heisenberg()

Return the discrete Heisenberg group of upper unitriangular integer matrices, generated by a and b.

Its commutator a b a^-1 b^-1 is central, and its balls grow as the fourth power of the radius.

Returns:

Name	Type	Description
group	FinitelyGeneratedMatrixGroup_generic	The Sage matrix group over the integers.

Examples:

>>> from skcomplex.models.computer_science.automata import heisenberg
>>> from skcomplex.core.spaces import CayleySpace
>>> CayleySpace(heisenberg(), ball=1).check().prepare().generators_
('a', 'b')

Source code in src/skcomplex/models/computer_science/automata/_groups.py

def heisenberg() -> FinitelyGeneratedMatrixGroup_generic:
    """Return the discrete Heisenberg group of upper unitriangular integer matrices, generated by `a` and `b`.

    Its commutator `a b a^-1 b^-1` is central, and its balls grow as the fourth power of the radius.

    Returns:
        group:
            The Sage matrix group over the integers.

    Examples:
        >>> from skcomplex.models.computer_science.automata import heisenberg
        >>> from skcomplex.core.spaces import CayleySpace
        >>> CayleySpace(heisenberg(), ball=1).check().prepare().generators_
        ('a', 'b')
    """
    return MatrixGroup([matrix(ZZ, generator) for generator in HEISENBERG_GENERATORS])

heisenberg_automaton(*, radius=5, density=0.5, random_state=0)

Return the majority automaton on a ball of the discrete Heisenberg group, of polynomial growth of degree 4.

Every cell reads itself and the cells at a, a^-1, b, and b^-1, on the right, and takes the majority value.

Parameters:

Name	Type	Description	Default
radius	int	The radius of the ball.	5
density	float	The probability that a cell starts at 1.	0.5
random_state	int | Generator | None	The seed or generator of the initial cells.	0

Returns:

Name	Type	Description
system	System	The model, with the cells cells.alive.

Examples:

>>> from skcomplex.models.computer_science.automata import heisenberg_automaton
>>> heisenberg_automaton(radius=2).elements[0].check().prepare().size_
17

Source code in src/skcomplex/models/computer_science/automata/_group_automata.py

@register_model(
    field='computer_science/automata',
    tags=('group', 'cellular automaton', 'majority', 'nilpotent'),
    references=('Ceccherini-Silberstein and Coornaert 2023',),
    defaults={'until': 20, 'dt': 1},
    observables=_density_observables,
)
def heisenberg_automaton(
    *,
    radius: int = 5,
    density: float = 0.5,
    random_state: int | np.random.Generator | None = 0,
) -> System:
    """Return the majority automaton on a ball of the discrete Heisenberg group, of polynomial growth of degree 4.

    Every cell reads itself and the cells at `a`, `a^-1`, `b`, and `b^-1`, on the right, and takes the majority value.

    Args:
        radius:
            The radius of the ball.

        density:
            The probability that a cell starts at 1.

        random_state:
            The seed or generator of the initial cells.

    Returns:
        system:
            The model, with the cells `cells.alive`.

    Examples:
        >>> from skcomplex.models.computer_science.automata import heisenberg_automaton
        >>> heisenberg_automaton(radius=2).elements[0].check().prepare().size_
        17
    """
    space = CayleySpace(heisenberg(), ball=radius)
    return _majority_system(
        space,
        GeneratorNeighborhood(space.check().prepare().generators_),
        density,
        random_state,
    )

highlife(shape=(100, 100), *, rule='B36/S23', density=0.3, initial=None, random_state=0)

Return HighLife, B36/S23, or any other life-like automaton of the planar zoo by its rule, on a torus.

HighLife adds birth on six neighbours to Conway's rule, which gives it a small self-replicating pattern. Other members of the zoo are Seeds, B2/S, Day and Night, B3678/S34678, and Life without death, B3/S012345678.

Parameters:

Name	Type	Description	Default
shape	Sequence[int]	The number of rows and columns.	(100, 100)
rule	str	The rule in the notation B<births>/S<survivals>.	'B36/S23'
density	float	The probability that a cell starts alive, when no initial cells are given.	0.3
initial	ArrayLike | None	The initial cells, an array of the shape, or None for random cells.	None
random_state	int | Generator | None	The seed or generator of the random initial cells.	0

Returns:

Name	Type	Description
system	System	The model, with the cells cells.alive.

Raises:

Type	Description
ParameterError	The rule is not in the notation B<births>/S<survivals>.

Examples:

>>> from skcomplex.models.computer_science.automata import highlife
>>> sorted(highlife((10, 10), rule='B2/S').interactions[0].rule.rule)
[(0, 2)]

Source code in src/skcomplex/models/computer_science/automata/_variants.py

@register_model(
    field='computer_science/automata',
    tags=('lattice', 'life', 'replicator'),
    references=('Bell 1994', 'Charbonneau 2017', 'Downey 2018'),
    defaults={'until': 100, 'dt': 1},
)
def highlife(
    shape: Sequence[int] = (100, 100),
    *,
    rule: str = 'B36/S23',
    density: float = 0.3,
    initial: npt.ArrayLike | None = None,
    random_state: int | np.random.Generator | None = 0,
) -> System:
    """Return HighLife, `B36/S23`, or any other life-like automaton of the planar zoo by its rule, on a torus.

    HighLife adds birth on six neighbours to Conway's rule, which gives it a small self-replicating pattern. Other
    members of the zoo are Seeds, `B2/S`, Day and Night, `B3678/S34678`, and Life without death, `B3/S012345678`.

    Args:
        shape:
            The number of rows and columns.

        rule:
            The rule in the notation `B<births>/S<survivals>`.

        density:
            The probability that a cell starts alive, when no initial cells are given.

        initial:
            The initial cells, an array of the shape, or `None` for random cells.

        random_state:
            The seed or generator of the random initial cells.

    Returns:
        system:
            The model, with the cells `cells.alive`.

    Raises:
        ParameterError:
            The rule is not in the notation `B<births>/S<survivals>`.

    Examples:
        >>> from skcomplex.models.computer_science.automata import highlife
        >>> sorted(highlife((10, 10), rule='B2/S').interactions[0].rule.rule)
        [(0, 2)]
    """
    born, survive = _parse_life_rule(rule)
    values = _random_cells(shape, density, random_state) if initial is None else np.asarray(initial, dtype=float)
    space = LatticeSpace(tuple(shape))
    return System(
        elements=[LatticeElement('cells', element=BinaryCellElement, space=space, values={'alive': values})],
        interactions=[
            LocalRuleInteraction(
                'rule',
                target='cells',
                state='alive',
                rule=life(born, survive),
                neighborhood=MooreNeighborhood(),
            ),
        ],
    )

lamplighter()

Return the lamplighter group, the wreath product of the group of order 2 with the integers, as automaton group.

The automaton a = (a, b)(0 1), b = (a, b) of Grigorchuk and Zuk generates it, and its Cayley graph is the Diestel-Leader graph.

Returns:

Name	Type	Description
group	GapElement	The GAP automaton group of the AutomGrp package.

Examples:

>>> from skcomplex.models.computer_science.automata import lamplighter
>>> from skcomplex.core.spaces import CayleySpace
>>> CayleySpace(lamplighter(), ball=1).check().prepare().generators_
('a', 'b')

Source code in src/skcomplex/models/computer_science/automata/_groups.py

def lamplighter() -> GapElement:
    """Return the lamplighter group, the wreath product of the group of order 2 with the integers, as automaton group.

    The automaton `a = (a, b)(0 1)`, `b = (a, b)` of Grigorchuk and Zuk generates it, and its Cayley graph is the
    Diestel-Leader graph.

    Returns:
        group:
            The GAP automaton group of the AutomGrp package.

    Examples:
        >>> from skcomplex.models.computer_science.automata import lamplighter
        >>> from skcomplex.core.spaces import CayleySpace
        >>> CayleySpace(lamplighter(), ball=1).check().prepare().generators_
        ('a', 'b')
    """
    libgap.LoadPackage('automgrp')
    return libgap.AutomatonGroup(LAMPLIGHTER_RECURSION)

lamplighter_automaton(*, radius=7, density=0.1, random_state=0)

Return the parity automaton on a ball of the lamplighter group, a linear rule over the field of two elements.

Every cell takes the sum modulo 2 of itself and the cells at the generators a and b, so a few ones spread into nested, self-similar patterns over the Diestel-Leader graph of the group.

Parameters:

Name	Type	Description	Default
radius	int	The radius of the ball.	7
density	float	The probability that a cell starts at 1.	0.1
random_state	int | Generator | None	The seed or generator of the initial cells.	0

Returns:

Name	Type	Description
system	System	The model, with the cells cells.alive.

Examples:

>>> from skcomplex.models.computer_science.automata import lamplighter_automaton
>>> lamplighter_automaton(radius=3).elements[0].check().prepare().size_
39

Source code in src/skcomplex/models/computer_science/automata/_group_automata.py

@register_model(
    field='computer_science/automata',
    tags=('group', 'cellular automaton', 'linear', 'lamplighter'),
    references=('Ceccherini-Silberstein and Coornaert 2023', 'Grigorchuk and Zuk 2001'),
    defaults={'until': 20, 'dt': 1},
    observables=_density_observables,
)
def lamplighter_automaton(
    *,
    radius: int = 7,
    density: float = 0.1,
    random_state: int | np.random.Generator | None = 0,
) -> System:
    """Return the parity automaton on a ball of the lamplighter group, a linear rule over the field of two elements.

    Every cell takes the sum modulo 2 of itself and the cells at the generators `a` and `b`, so a few ones spread into
    nested, self-similar patterns over the Diestel-Leader graph of the group.

    Args:
        radius:
            The radius of the ball.

        density:
            The probability that a cell starts at 1.

        random_state:
            The seed or generator of the initial cells.

    Returns:
        system:
            The model, with the cells `cells.alive`.

    Examples:
        >>> from skcomplex.models.computer_science.automata import lamplighter_automaton
        >>> lamplighter_automaton(radius=3).elements[0].check().prepare().size_
        39
    """
    space = CayleySpace(lamplighter(), ball=radius)
    cells = _random_cells(space.check().prepare().size_, density, random_state)
    parity = TotalisticSpec({total: total % 2 for total in range(len(LAMPLIGHTER_MEMORY.elements) + 1)})
    return System(
        elements=[LatticeElement('cells', element=BinaryCellElement, space=space, values={'alive': cells})],
        interactions=[
            LocalRuleInteraction('parity', target='cells', state='alive', rule=parity, neighborhood=LAMPLIGHTER_MEMORY),
        ],
    )

langtons_ant(shape=(80, 80), *, heading=0)

Return Langton's ant, which wanders chaotically for about 10,000 steps before it builds a periodic highway.

Parameters:

Name	Type	Description	Default
shape	Sequence[int]	The number of rows and columns of the torus.	(80, 80)
heading	int	The initial heading of the ant, 0 to 3 for north, east, south, and west.	0

Returns:

Name	Type	Description
system	System	The model, with the colors cells.color and the ant cells.ant.

Examples:

>>> from skcomplex.models.computer_science.automata import langtons_ant
>>> int((langtons_ant((9, 9)).elements[0].values['ant'] >= 0).sum())
1

Source code in src/skcomplex/models/computer_science/automata/_automata.py

@register_model(
    field='computer_science/automata',
    tags=('lattice', 'ant', 'emergence'),
    references=('Langton 1986',),
    defaults={'until': 11000, 'dt': 100},
)
def langtons_ant(shape: Sequence[int] = (80, 80), *, heading: int = 0) -> System:
    """Return Langton's ant, which wanders chaotically for about 10,000 steps before it builds a periodic highway.

    Args:
        shape:
            The number of rows and columns of the torus.

        heading:
            The initial heading of the ant, 0 to 3 for north, east, south, and west.

    Returns:
        system:
            The model, with the colors `cells.color` and the ant `cells.ant`.

    Examples:
        >>> from skcomplex.models.computer_science.automata import langtons_ant
        >>> int((langtons_ant((9, 9)).elements[0].values['ant'] >= 0).sum())
        1
    """
    ant = np.full(tuple(shape), -1.0)
    ant[shape[0] // 2, shape[1] // 2] = heading
    return System(
        elements=[
            LatticeElement('cells', element=AntCellElement, space=LatticeSpace(tuple(shape)), values={'ant': ant}),
        ],
        interactions=[
            LocalRuleInteraction(
                'ant',
                target='cells',
                state=('color', 'ant'),
                rule=_ant_rule,
                neighborhood=VonNeumannNeighborhood(center=True),
                reads=('color', 'ant'),
            ),
        ],
    )

life(born=(3,), survive=(2, 3))

Return a life-like rule in the notation B3/S23 of Conway's Game of Life.

Parameters:

Name	Type	Description	Default
born	Iterable[int]	The numbers of live neighbours that bring a dead cell to life.	(3,)
survive	Iterable[int]	The numbers of live neighbours that keep a live cell alive.	(2, 3)

Returns:

Name	Type	Description
rule	OuterTotalisticSpec	The outer totalistic rule.

Examples:

>>> from skcomplex.models.computer_science.automata import life
>>> rule = life()
>>> rule.rule[(0, 3)], rule.rule[(1, 2)], (1, 4) in rule.rule
(1, 1, False)

Source code in src/skcomplex/models/computer_science/automata/_codes.py

def life(born: Iterable[int] = (3,), survive: Iterable[int] = (2, 3)) -> OuterTotalisticSpec:
    """Return a life-like rule in the notation `B3/S23` of Conway's Game of Life.

    Args:
        born:
            The numbers of live neighbours that bring a dead cell to life.

        survive:
            The numbers of live neighbours that keep a live cell alive.

    Returns:
        rule:
            The outer totalistic rule.

    Examples:
        >>> from skcomplex.models.computer_science.automata import life
        >>> rule = life()
        >>> rule.rule[(0, 3)], rule.rule[(1, 2)], (1, 4) in rule.rule
        (1, 1, False)
    """
    return OuterTotalisticSpec({**{(0, count): 1 for count in born}, **{(1, count): 1 for count in survive}})

linear_ring_automaton(size=101, *, modulus=3)

Return the discrete Laplacian as a linear automaton on a ring, over the field of modulus elements.

The ring is the cyclic group of order size, a periodic lattice, and every cell becomes x(g - 1) + x(g + 1) - 2 x(g) modulo the field size, the element a^-1 + a - 2 of the group ring. From a single 1 in the middle the values spread as binomial coefficients reduced modulo the field size, a self-similar triangle.

Parameters:

Name	Type	Description	Default
size	int	The order of the cyclic group, the number of cells of the ring.	101
modulus	int	The prime size of the field.	3

Returns:

Name	Type	Description
system	System	The model, with the cells cells.value.

Examples:

>>> from skcomplex.models.computer_science.automata import linear_ring_automaton
>>> linear_ring_automaton(11).elements[0].check().prepare().size_
11

Source code in src/skcomplex/models/computer_science/automata/_group_automata.py

@register_model(
    field='computer_science/automata',
    tags=('group', 'cellular automaton', 'linear', 'Laplacian'),
    references=('Ceccherini-Silberstein and Coornaert 2023',),
    defaults={'until': 40, 'dt': 1},
    observables=_mean_observables,
)
def linear_ring_automaton(
    size: int = 101,
    *,
    modulus: int = 3,
) -> System:
    """Return the discrete Laplacian as a linear automaton on a ring, over the field of `modulus` elements.

    The ring is the cyclic group of order `size`, a periodic lattice, and every cell becomes
    `x(g - 1) + x(g + 1) - 2 x(g)` modulo the field size, the element `a^-1 + a - 2` of the group ring. From a single
    1 in the middle the values spread as binomial coefficients reduced modulo the field size, a self-similar triangle.

    Args:
        size:
            The order of the cyclic group, the number of cells of the ring.

        modulus:
            The prime size of the field.

    Returns:
        system:
            The model, with the cells `cells.value`.

    Examples:
        >>> from skcomplex.models.computer_science.automata import linear_ring_automaton
        >>> linear_ring_automaton(11).elements[0].check().prepare().size_
        11
    """
    values = np.zeros(size)
    values[size // 2] = 1.0
    return System(
        elements=[
            LatticeElement(
                'cells',
                element=LaplacianCellElement,
                space=LatticeSpace(size),
                values={'value': values, 'modulus': modulus},
            ),
        ],
        interactions=[
            LocalRuleInteraction(
                'laplacian',
                target='cells',
                state='value',
                rule=_laplacian,
                neighborhood=BoxNeighborhood(),
            ),
        ],
    )

noisy_automata(rule=18, *, noise=0.01, size=101, density=0.5, random_state=0)

Return an elementary cellular automaton whose outputs are flipped at random with a small probability.

Parameters:

Name	Type	Description	Default
rule	int	The Wolfram number from 0 to 255.	18
noise	float	The probability that a cell's output is flipped in a step.	0.01
size	int	The number of cells of the ring.	101
density	float	The probability that a cell starts alive.	0.5
random_state	int | Generator | None	The seed or generator of the random initial cells.	0

Returns:

Name	Type	Description
system	System	The model, with the cells cells.alive.

Examples:

>>> from skcomplex.models.computer_science.automata import noisy_automata
>>> noisy_automata(184, size=11).elements[0].check().prepare().size_
11

Source code in src/skcomplex/models/computer_science/automata/_variants.py

@register_model(
    field='computer_science/automata',
    tags=('lattice', 'elementary', 'noise', 'stochastic'),
    references=('Lindgren 2024',),
    defaults={'until': 100, 'dt': 1},
)
def noisy_automata(
    rule: int = 18,
    *,
    noise: float = 0.01,
    size: int = 101,
    density: float = 0.5,
    random_state: int | np.random.Generator | None = 0,
) -> System:
    """Return an elementary cellular automaton whose outputs are flipped at random with a small probability.

    Args:
        rule:
            The Wolfram number from 0 to 255.

        noise:
            The probability that a cell's output is flipped in a step.

        size:
            The number of cells of the ring.

        density:
            The probability that a cell starts alive.

        random_state:
            The seed or generator of the random initial cells.

    Returns:
        system:
            The model, with the cells `cells.alive`.

    Examples:
        >>> from skcomplex.models.computer_science.automata import noisy_automata
        >>> noisy_automata(184, size=11).elements[0].check().prepare().size_
        11
    """
    values = _random_cells((size,), density, random_state)
    space = LatticeSpace(size)
    return System(
        elements=[
            LatticeElement(
                'cells',
                element=NoisyElementaryCellElement,
                space=space,
                values={'alive': values, 'noise': noise},
            ),
        ],
        interactions=[
            LocalRuleInteraction(
                'rule',
                target='cells',
                state='alive',
                rule=_noisy_rule(rule),
                neighborhood=BoxNeighborhood(),
                stochastic=True,
            ),
        ],
    )

subshifts(size=200)

Return a Markov chain on the golden mean shift, the configurations of a ring that never hold two adjacent ones.

The ring is the cyclic group of order size, a periodic lattice. It starts empty, and every step proposes to flip every cell in a random order, rejecting the flips that would put two ones side by side. The chain samples the admissible configurations, whose number grows as the power of the golden ratio.

Parameters:

Name	Type	Description	Default
size	int	The number of cells of the ring, the order of the cyclic group.	200

Returns:

Name	Type	Description
system	System	The model, with the cells cells.alive.

Examples:

>>> from skcomplex.models.computer_science.automata import subshifts
>>> subshifts(10).elements[0].check().prepare().size_
10

Source code in src/skcomplex/models/computer_science/automata/_group_automata.py

@register_model(
    field='computer_science/automata',
    tags=('group', 'subshift', 'golden mean', 'Markov chain'),
    references=('Ceccherini-Silberstein and Coornaert 2023', 'Lind and Marcus 1995'),
    defaults={'until': 50, 'dt': 1},
    observables=_density_observables,
)
def subshifts(size: int = 200) -> System:
    """Return a Markov chain on the golden mean shift, the configurations of a ring that never hold two adjacent ones.

    The ring is the cyclic group of order `size`, a periodic lattice. It starts empty, and every step proposes to flip
    every cell in a random order, rejecting the flips that would put two ones side by side. The chain samples the
    admissible configurations, whose number grows as the power of the golden ratio.

    Args:
        size:
            The number of cells of the ring, the order of the cyclic group.

    Returns:
        system:
            The model, with the cells `cells.alive`.

    Examples:
        >>> from skcomplex.models.computer_science.automata import subshifts
        >>> subshifts(10).elements[0].check().prepare().size_
        10
    """
    flips = LocalRuleInteraction(
        'flips',
        target='cells',
        state='alive',
        rule=_golden_move,
        neighborhood=BoxNeighborhood(),
        schedule='random-sequential',
        stochastic=True,
    )
    return System(
        elements=[LatticeElement('cells', element=BinaryCellElement, space=LatticeSpace(size))],
        interactions=[flips],
    )

unbounded_alphabet_automaton(size=101)

Return an additive automaton over the nonnegative integers, x'(n) = x(n - 1) + x(n), from a single 1.

Its alphabet has no bound: from a single 1 the cells after t steps hold the binomial coefficients C(t, k), so every row of Pascal's triangle appears.

Parameters:

Name	Type	Description	Default
size	int	The number of cells of the ring.	101

Returns:

Name	Type	Description
system	System	The model, with the cells cells.value.

Examples:

>>> from skcomplex.models.computer_science.automata import unbounded_alphabet_automaton
>>> int(unbounded_alphabet_automaton(9).elements[0].values['value'].sum())
1

Source code in src/skcomplex/models/computer_science/automata/_variants.py

@register_model(
    field='computer_science/automata',
    tags=('lattice', 'integers', 'additive', 'pascal triangle'),
    references=('Ceccherini-Silberstein and Coornaert 2023',),
    defaults={'until': 50, 'dt': 1},
)
def unbounded_alphabet_automaton(size: int = 101) -> System:
    """Return an additive automaton over the nonnegative integers, `x'(n) = x(n - 1) + x(n)`, from a single 1.

    Its alphabet has no bound: from a single 1 the cells after `t` steps hold the binomial coefficients `C(t, k)`, so
    every row of Pascal's triangle appears.

    Args:
        size:
            The number of cells of the ring.

    Returns:
        system:
            The model, with the cells `cells.value`.

    Examples:
        >>> from skcomplex.models.computer_science.automata import unbounded_alphabet_automaton
        >>> int(unbounded_alphabet_automaton(9).elements[0].values['value'].sum())
        1
    """
    value = np.zeros(size)
    value[size // 2] = 1.0
    return System(
        elements=[
            LatticeElement('cells', element=PascalCellElement, space=LatticeSpace(size), values={'value': value}),
        ],
        interactions=[
            LocalRuleInteraction('addition', target='cells', state='value', rule=_add, neighborhood=PREDECESSORS),
        ],
    )