Automata

Automata: elementary, life-like, noisy, and group automata, automata over infinite alphabets, 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.systems.computer_science.automata import AntCellElement
>>> AntCellElement('cell').ant
-1

Source code in src/skcomplex/systems/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

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.systems.computer_science.automata import BinaryCellElement
>>> BinaryCellElement('cell', alive=1).alive
1

Source code in src/skcomplex/systems/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.systems.computer_science.automata import DiffusionCellElement
>>> DiffusionCellElement('cell', r=0.2).r
0.2

Source code in src/skcomplex/systems/computer_science/automata/_variants.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

DigitCellElement(label, visual=None, *, digit=0, base=2)

Bases: Element

Cell holding a digit of a q-adic integer, from 0 to base - 1, the label of a vertex of the q-ary tree.

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
digit	Annotated[float, StateSpec(domain=ZZ)]	The initial digit.	0
base	Annotated[float, ParameterSpec(domain=open(0, oo))]	The base q of the digits, at least 2.	2

Examples:

>>> from skcomplex.systems.computer_science.automata import DigitCellElement
>>> DigitCellElement('cell', digit=1).base
2

Source code in src/skcomplex/systems/computer_science/automata/_shift_spaces.py

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

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

Bases: Element

Cell of the golden mean shift, whose state alive is 0 or 1 and whose configurations hold no two adjacent ones.

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=GOLDEN_MEAN)]	The initial value, 0 or 1.	0

Examples:

>>> from skcomplex.systems.computer_science.automata import GoldenCellElement
>>> GoldenCellElement('cell', alive=1).alive
1

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

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

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

Bases: Element

Cell of an automaton whose alphabet is a group, holding a group element by its number.

The number is the site of the element in a group space, or its position in the list of a finite group, and a negative number names no element, the fill value read outside a ball.

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 number of the initial group element, 0 for the identity.	0

Examples:

>>> from skcomplex.systems.computer_science.automata import GroupCellElement
>>> GroupCellElement('cell', value=2).value
2

Source code in src/skcomplex/systems/computer_science/automata/_alphabets.py

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

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.systems.computer_science.automata import LaplacianCellElement
>>> LaplacianCellElement('cell').modulus
3

Source code in src/skcomplex/systems/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

LeniaSiteElement(label, visual=None, *, A=0.0, B=0.0, C=0.0)

Bases: Element

Site of a Lenia world, with a value in [0, 1] for each of up to three channels.

The updates of the world change the channels, and a world of one channel leaves B and C at 0.

Parameters:

Name	Type	Description	Default
label	str	The label of the site or the field.	required
visual	VisualSpec | None	How the element is drawn, or None for default_visual_.	None
A	Annotated[float, StateSpec(domain=closed(0, 1))]	The initial value of the first channel.	0.0
B	Annotated[float, StateSpec(domain=closed(0, 1))]	The initial value of the second channel.	0.0
C	Annotated[float, StateSpec(domain=closed(0, 1))]	The initial value of the third channel.	0.0

Examples:

>>> from skcomplex.systems.computer_science.automata import LeniaSiteElement
>>> LeniaSiteElement('site', A=0.5).A
0.5

Source code in src/skcomplex/systems/computer_science/automata/_lenia.py

def __init__(
    self,
    label: str,
    visual: VisualSpec | None = None,
    *,
    A: Annotated[float, StateSpec(domain=RealSet.closed(0, 1))] = 0.0,
    B: Annotated[float, StateSpec(domain=RealSet.closed(0, 1))] = 0.0,
    C: Annotated[float, StateSpec(domain=RealSet.closed(0, 1))] = 0.0,
) -> None:
    super().__init__(label, visual=visual)
    self.A = A
    self.B = B
    self.C = C

LeniaUpdateInteraction(label, *, target, channel='A', kernels=(('A', 13.0, 1.0, (1.0,), 0.15, 0.015),), T=10.0, n_dim=2)

Bases: Interaction

Update of a channel of a Lenia world by the growth maps of the convolutions of channels with ring kernels.

Every kernel (source, radius, h, beta, mu, sigma) reads the state of its source channel, and its concentric rings peak at beta. At the distance q in units of its radius, with B rings, it is beta_i K_C(B q - i) on the ring i = floor(B q), with the bump K_C(x) = exp(4 - 1 / (x (1 - x))), normalised to a sum of 1 over the sites. Its growth map is G(u) = 2 exp(-(u - mu)^2 / (2 sigma^2)) - 1, and one step adds the growths weighted by h over the sum of the weights and clips the channel, A <- [A + sum_k (h_k / h) G_k(K_k * A_k) / T] in [0, 1].

Parameters:

Name	Type	Description	Default
label	str	The label of the interaction.	required
target	Annotated[str, RoleSpec()]	The path of the world.	required
channel	str	The name of the state of the channel that the update changes.	'A'
kernels	Sequence[RingKernel]	The kernels (source, radius, h, beta, mu, sigma), with the name of the state of the source channel and the radius in sites.	(('A', 13.0, 1.0, (1.0,), 0.15, 0.015),)
T	float	The number of steps per unit time.	10.0
n_dim	int	The number of dimensions of the world.	2

Examples:

>>> from skcomplex.systems.computer_science.automata import LeniaUpdateInteraction
>>> LeniaUpdateInteraction('update', target='world').T
10.0

Source code in src/skcomplex/systems/computer_science/automata/_lenia.py

def __init__(
    self,
    label: str,
    *,
    target: Annotated[str, RoleSpec()],
    channel: str = 'A',
    kernels: Sequence[RingKernel] = (('A', 13.0, 1.0, (1.0,), 0.15, 0.015),),
    T: float = 10.0,
    n_dim: int = 2,
) -> None:
    super().__init__(label)
    self.target = target
    self.channel = channel
    self.kernels = kernels
    self.T = T
    self.n_dim = n_dim

LigationInteraction(label, *, target, edges=ADLEMAN_EDGES)

Bases: Interaction

Random ligation of the strands of a test tube, which joins a strand that ends at a node to one that starts there.

Every step the strands meet in random pairs. The oligo of the node that the first strand ends at and the second starts at holds their ends together, and the ligase joins them into one strand, as long as the joined path fits the longest path the tube holds. The second strand is consumed, and an edge oligo drawn uniformly from the links of the graph takes its place, since the tube holds a vast excess of oligos.

Parameters:

Name	Type	Description	Default
label	str	The label of the interaction.	required
target	Annotated[str, RoleSpec()]	The path of the group of strands.	required
edges	Sequence[tuple[int, int]]	The directed links of the graph, one edge oligo each.	ADLEMAN_EDGES

Examples:

>>> from skcomplex.systems.computer_science.automata import LigationInteraction
>>> LigationInteraction('ligation', target='strands', edges=((0, 1),)).edges
((0, 1),)

Source code in src/skcomplex/systems/computer_science/automata/_dna_computation.py

def __init__(
    self,
    label: str,
    *,
    target: Annotated[str, RoleSpec()],
    edges: Sequence[tuple[int, int]] = ADLEMAN_EDGES,
) -> None:
    super().__init__(label)
    self.target = target
    self.edges = edges

MorseElement(label, axiom='', *, alphabet=None, ignore='', geometry=None, max_size=10000000, bounds=None, visual=None)

Bases: WordElement

Word rewritten by the Thue-Morse substitution 0 → 01, 1 → 10.

From the axiom 0, generation n is the word a_n = T(0) T(1) ... T(2^n - 1) of the Thue-Morse sequence, whose term T(k) is the parity of the number of ones in the binary expansion of k.

Parameters:

Name	Type	Description	Default
label	str	The label of the word.	required
axiom	Annotated[Letters, StateSpec(domain=None)]	The word at generation 0.	''

Examples:

>>> from skcomplex.systems.computer_science.automata import MorseElement
>>> [law.successor for law in MorseElement('morse', axiom='0')._get_laws(None)]
['01', '10']

Source code in src/skcomplex/core/components/elements/_word.py

def __init__(
    self,
    label: str,
    axiom: Annotated[Letters, StateSpec(domain=None)] = '',
    *,
    alphabet: str | Mapping[str, int] | None = None,
    ignore: str | Sequence[str] = '',
    geometry: GeometrySpec | None = None,
    max_size: int = 10_000_000,
    bounds: Sequence[float] | None = None,
    visual: VisualSpec | None = None,
) -> None:
    super().__init__(label, visual=visual)
    self.axiom = axiom
    self.alphabet = alphabet
    self.ignore = ignore
    self.geometry = geometry
    self.max_size = max_size
    self.bounds = bounds

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.systems.computer_science.automata import NoisyElementaryCellElement
>>> NoisyElementaryCellElement('cell', noise=0.1).noise
0.1

Source code in src/skcomplex/systems/computer_science/automata/_variants.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

PairCellElement(label, visual=None, *, first=0, second=0, modulus=2)

Bases: Element

Cell of an automaton over the product H x H of the integers modulo n with itself, or K^2 for a prime n.

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
first	Annotated[float, StateSpec(domain=ZZ)]	The initial first coordinate, an integer from 0 to modulus - 1.	0
second	Annotated[float, StateSpec(domain=ZZ)]	The initial second coordinate, an integer from 0 to modulus - 1.	0
modulus	Annotated[float, ParameterSpec(domain=open(0, oo))]	The order n of the cyclic group H, the size of the field K when prime.	2

Examples:

>>> from skcomplex.systems.computer_science.automata import PairCellElement
>>> PairCellElement('cell', first=1).modulus
2

Source code in src/skcomplex/systems/computer_science/automata/_free_group_automata.py

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

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.systems.computer_science.automata import PascalCellElement
>>> PascalCellElement('cell', value=3).value
3

Source code in src/skcomplex/systems/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

PowerSeriesCellElement(label, visual=None, *, ring=RATIONAL_SERIES, variables=None)

Bases: DeclaredElement

Cell of an automaton over a ring K[[t]] of formal power series truncated at an order.

The cell declares the state value in the ring it is given, so it holds the coefficients a_0, ..., a_{order - 1} of a series, which a local rule reads as one row per cell.

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
ring	PowerSeriesSpec	The truncated power series ring of the values.	RATIONAL_SERIES
variables	Mapping[str, DeclaredVariableSpec] | None	Declared states and parameters besides value, or values that replace its default, by name.	None

Examples:

>>> from skcomplex.core.specs import PowerSeriesSpec
>>> from skcomplex.systems.computer_science.automata import PowerSeriesCellElement
>>> PowerSeriesCellElement('cell', ring=PowerSeriesSpec(3)).get_value('value').tolist()
[0.0, 0.0, 0.0]

Source code in src/skcomplex/systems/computer_science/automata/_alphabets.py

def __init__(
    self,
    label: str,
    visual: VisualSpec | None = None,
    *,
    ring: PowerSeriesSpec = RATIONAL_SERIES,
    variables: Mapping[str, DeclaredVariableSpec] | None = None,
) -> None:
    super().__init__(label, visual=visual, variables=variables)
    self.ring = ring

RealCellElement(label, visual=None, *, value=0.0)

Bases: Element

Cell of an automaton over the real numbers.

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=RR)]	The initial value.	0.0

Examples:

>>> from skcomplex.systems.computer_science.automata import RealCellElement
>>> RealCellElement('cell', value=0.5).value
0.5

Source code in src/skcomplex/systems/computer_science/automata/_alphabets.py

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

StrandElement(label, visual=None, *, path=EMPTY)

Bases: Element

Strand of DNA in the test tube, the path of nodes its ligated edge oligos spell, padded with -1.

Parameters:

Name	Type	Description	Default
label	str	The label of the strand or the group.	required
visual	VisualSpec | None	How the element is drawn, or None for default_visual_.	None
path	Annotated[object, StateSpec()]	The initial nodes of the path, padded with -1 to the longest path the tube holds.	EMPTY

Examples:

>>> from skcomplex.systems.computer_science.automata import StrandElement
>>> StrandElement('strand', path=(0, 1, -1)).path
(0, 1, -1)

Source code in src/skcomplex/systems/computer_science/automata/_dna_computation.py

def __init__(
    self,
    label: str,
    visual: VisualSpec | None = None,
    *,
    path: Annotated[object, StateSpec()] = EMPTY,
) -> None:
    super().__init__(label, visual=visual)
    self.path = path

TapeCellElement(label, visual=None, *, symbol=0, head=-1)

Bases: Element

Cell of the tape of a Turing machine: a symbol, and the internal state of the head on it or -1.

The local rule of turing_machine lets the head on a cell write the symbol of its action table, move one cell left or right, or stay, and take its next internal state. A halted head keeps its cell and the tape stays unchanged.

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
symbol	Annotated[float, StateSpec(domain=NN)]	The initial symbol.	0
head	Annotated[float, StateSpec(domain=ZZ)]	The internal state of the head on the cell, from 0, or -1 for no head.	-1

Examples:

>>> from skcomplex.systems.computer_science.automata import TapeCellElement
>>> TapeCellElement('cell').head
-1

Source code in src/skcomplex/systems/computer_science/automata/_turing_machine.py

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

TernaryCellElement(label, visual=None, *, symbol=0)

Bases: Element

Cell of a subshift over the alphabet {0, 1, 2}, such as the context-free subshift.

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
symbol	Annotated[float, StateSpec(domain=FiniteEnumeratedSet([0, 1, 2]))]	The initial symbol, 0, 1, or 2.	0

Examples:

>>> from skcomplex.systems.computer_science.automata import TernaryCellElement
>>> TernaryCellElement('cell', symbol=2).symbol
2

Source code in src/skcomplex/systems/computer_science/automata/_shift_spaces.py

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

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.systems.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/systems/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},
    )

adding_machine(digits=6, *, base=2, initial=None)

Return the adding machine r → r + 1 on the q-adic integers, the odometer acting on the q-ary tree.

The cells hold the digits of r, the lowest first, the first digits letters of its infinite word, a vertex of the q-ary tree. Every step adds 1: the lowest digit turns by the cycle 0 → 1 → ... → q - 1 → 0, and a digit turns when every lower digit is q - 1, the carry (Ceccherini-Silberstein and Coornaert 2023, Exercise 6.59). The machine is an automorphism of the tree of infinite order whose orbits are dense, and on the first digits levels it visits all q^digits vertices in turn. The lowest digit reads q - 1 beyond the segment, the carry of +1.

Parameters:

Name	Type	Description	Default
digits	int	The number of digits kept, the depth of the tree.	6
base	int	The base q, at least 2.	2
initial	ArrayLike | None	The initial digits, the lowest first, or None for 0.	None

Returns:

Name	Type	Description
system	System	The system, with the digits cells.digit.

Raises:

Type	Description
ParameterError	The base is below 2.

Examples:

>>> from skcomplex.systems.computer_science.automata import adding_machine
>>> adding_machine(4).elements[0].prepare().size_
4

Source code in src/skcomplex/systems/computer_science/automata/_shift_spaces.py

@register_system(
    field='computer_science/automata',
    tags=('odometer', 'q-adic integers', 'self-similar group', 'tree automorphism'),
    references=('Ceccherini-Silberstein and Coornaert 2023',),
    defaults={'until': 64, 'dt': 1},
)
def adding_machine(
    digits: int = 6,
    *,
    base: int = 2,
    initial: npt.ArrayLike | None = None,
) -> System:
    """Return the adding machine `r → r + 1` on the q-adic integers, the odometer acting on the q-ary tree.

    The cells hold the digits of `r`, the lowest first, the first `digits` letters of its infinite word, a vertex of the
    q-ary tree. Every step adds 1: the lowest digit turns by the cycle `0 → 1 → ... → q - 1 → 0`, and a digit turns
    when every lower digit is `q - 1`, the carry (Ceccherini-Silberstein and Coornaert 2023, Exercise 6.59). The machine
    is an automorphism of the tree of infinite order whose orbits are dense, and on the first `digits` levels it
    visits all `q^digits` vertices in turn. The lowest digit reads `q - 1` beyond the segment, the carry of `+1`.

    Args:
        digits:
            The number of digits kept, the depth of the tree.

        base:
            The base `q`, at least 2.

        initial:
            The initial digits, the lowest first, or `None` for 0.

    Returns:
        system:
            The system, with the digits `cells.digit`.

    Raises:
        ParameterError:
            The base is below 2.

    Examples:
        >>> from skcomplex.systems.computer_science.automata import adding_machine
        >>> adding_machine(4).elements[0].prepare().size_
        4
    """
    if base < MIN_BASE:
        error_msg = f'The base of the adding machine is at least 2, but it is {base}.'
        raise ParameterError(error_msg)
    values = np.zeros(digits) if initial is None else np.asarray(initial, dtype=float)
    return System(
        elements=[
            LatticeElement(
                'cells',
                element=DigitCellElement,
                space=LatticeSpace(digits, boundary='fixed', fill=base - 1),
                values={'digit': values, 'base': base},
            ),
        ],
        interactions=[
            LocalRuleInteraction(
                'carry',
                target='cells',
                state='digit',
                rule=_carry,
                neighborhood=LatticeNeighborhood(tuple((offset,) for offset in range(1 - digits, 1))),
            ),
        ],
    )

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.systems.computer_science.automata import baumslag_solitar
>>> from skcomplex.core.components.spaces import CayleySpace
>>> CayleySpace(baumslag_solitar(), ball=1).prepare().generators_
('a', 't')

Source code in src/skcomplex/systems/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.systems.computer_science.automata import baumslag_solitar
        >>> from skcomplex.core.components.spaces import CayleySpace
        >>> CayleySpace(baumslag_solitar(), ball=1).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 system, with the cells cells.alive.

Examples:

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

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

@register_system(
    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 system, with the cells `cells.alive`.

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

context_free_subshift(size=60, *, initial=None, random_state=0)

Return a Markov chain on the context-free subshift, ternary rings where every block 0 1^h 2^k 0 has h = k.

The subshift is not sofic, since a finite graph cannot match the counts of ones and twos (Ceccherini-Silberstein and Coornaert 2023, Exercise 6.80). Every step proposes to change every cell of the ring, in a random order, to one of the two other symbols, and rejects the changes that would leave the subshift, so the chain samples its admissible rings uniformly. It starts from blocks 0 1^h 2^h, with h drawn from a geometric law.

Parameters:

Name	Type	Description	Default
size	int	The number of cells of the ring.	60
initial	ArrayLike | None	The initial symbols, an admissible ring, or None for random balanced blocks.	None
random_state	int | Generator | None	The seed or generator of the initial blocks.	0

Returns:

Name	Type	Description
system	System	The system, with the symbols cells.symbol.

Raises:

Type	Description
ParameterError	The initial ring is not admissible.

Examples:

>>> from skcomplex.systems.computer_science.automata import context_free_subshift
>>> context_free_subshift(12).elements[0].values['symbol'].tolist()
[0.0, 1.0, 1.0, 2.0, 2.0, 0.0, 1.0, 2.0, 0.0, 1.0, 2.0, 0.0]

Source code in src/skcomplex/systems/computer_science/automata/_shift_spaces.py

@register_system(
    field='computer_science/automata',
    tags=('subshift', 'context-free', 'Monte Carlo', 'not sofic'),
    references=('Ceccherini-Silberstein and Coornaert 2023',),
    defaults={'until': 50, 'dt': 1},
)
def context_free_subshift(
    size: int = 60,
    *,
    initial: npt.ArrayLike | None = None,
    random_state: int | np.random.Generator | None = 0,
) -> System:
    """Return a Markov chain on the context-free subshift, ternary rings where every block `0 1^h 2^k 0` has `h = k`.

    The subshift is not sofic, since a finite graph cannot match the counts of ones and twos
    (Ceccherini-Silberstein and Coornaert 2023, Exercise 6.80). Every step proposes to change every cell of the ring, in
    a random order, to one of the two other symbols, and rejects the changes that would leave the subshift, so the
    chain samples its admissible rings uniformly. It starts from blocks `0 1^h 2^h`, with `h` drawn from a geometric
    law.

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

        initial:
            The initial symbols, an admissible ring, or `None` for random balanced blocks.

        random_state:
            The seed or generator of the initial blocks.

    Returns:
        system:
            The system, with the symbols `cells.symbol`.

    Raises:
        ParameterError:
            The initial ring is not admissible.

    Examples:
        >>> from skcomplex.systems.computer_science.automata import context_free_subshift
        >>> context_free_subshift(12).elements[0].values['symbol'].tolist()
        [0.0, 1.0, 1.0, 2.0, 2.0, 0.0, 1.0, 2.0, 0.0, 1.0, 2.0, 0.0]
    """
    if initial is None:
        generator = np.random.default_rng(random_state)
        blocks: list[float] = []
        while len(blocks) < size:
            height = int(generator.geometric(BALANCED_BLOCK))
            blocks += [0.0] + [1.0] * height + [2.0] * height
        symbols = np.zeros(size)
        cut = max(index for index in range(size + 1) if index == len(blocks) or blocks[index] == 0)
        symbols[:cut] = blocks[:cut]
    else:
        symbols = np.asarray(initial, dtype=float)
    if not _is_context_free(symbols):
        error_msg = f'The initial ring {symbols.tolist()} holds a block 0 1^h 2^k 0 with h != k.'
        raise ParameterError(error_msg)
    return System(
        elements=[
            LatticeElement('cells', element=TernaryCellElement, space=LatticeSpace(size), values={'symbol': symbols}),
        ],
        interactions=[
            LocalRuleInteraction(
                'moves',
                target='cells',
                state='symbol',
                rule=_context_free_move,
                neighborhood=_whole_ring(size),
                schedule='random-sequential',
                stochastic=True,
            ),
        ],
    )

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 system, with the contents cells.level.

Examples:

>>> from skcomplex.systems.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/systems/computer_science/automata/_variants.py

@register_system(
    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 system, with the contents `cells.level`.

    Examples:
        >>> from skcomplex.systems.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),
            ),
        ],
    )

dna_computation(n_strands=2000, *, edges=ADLEMAN_EDGES, start=0, end=6, random_state=0)

Return Adleman's DNA computation of a Hamiltonian path, by random ligation of edge oligos in a test tube.

Every node of a directed graph is an oligonucleotide, and every link an oligo that joins the end of one node to the start of the next, so ligation builds strands that spell random paths of the graph. The tube starts with edge oligos drawn uniformly from the links, which meet in random pairs and join when the end of one is the start of the other. Adleman's filters then keep the strands that start at start and end at end, that pass through as many nodes as the graph has, and that visit every node, and any strand left is a Hamiltonian path. On the graph of Adleman's experiment, with seven nodes and fourteen links, solutions appear after some steps and every one of them is the path 0, 1, 2, 3, 4, 5, 6, while a graph without a Hamiltonian path leaves no strand.

Parameters:

Name	Type	Description	Default
n_strands	int	The number of strands in the tube.	2000
edges	Sequence[tuple[int, int]]	The directed links of the graph, with the nodes numbered from 0.	ADLEMAN_EDGES
start	int	The node the paths start at.	0
end	int	The node the paths end at.	6
random_state	int | Generator | None	The seed or generator of the initial oligos.	0

Returns:

Name	Type	Description
system	System	The system, with the group strands of paths path, padded with -1. Its standard observable solutions is the number of strands that pass the filters for the default nodes of Adleman's graph.

Raises:

Type	Description
ParameterError	The graph has no links, or the start or the end is not a node of it.

Examples:

>>> from skcomplex.systems.computer_science.automata import dna_computation
>>> dna_computation(10).elements[0].values['path'].shape
(10, 7)

Source code in src/skcomplex/systems/computer_science/automata/_dna_computation.py

@register_system(
    field='computer_science/automata',
    tags=('dna computing', 'molecular computation', 'hamiltonian path', 'agents', 'stochastic'),
    references=('Adleman 1994', 'Raman 2021'),
    defaults={'until': 60},
    observables=lambda system: [
        ObservableSpec('solutions', group='strands', variable='path', reduce=_adleman_solutions),
    ],
)
def dna_computation(
    n_strands: int = 2000,
    *,
    edges: Sequence[tuple[int, int]] = ADLEMAN_EDGES,
    start: int = 0,
    end: int = 6,
    random_state: int | np.random.Generator | None = 0,
) -> System:
    """Return Adleman's DNA computation of a Hamiltonian path, by random ligation of edge oligos in a test tube.

    Every node of a directed graph is an oligonucleotide, and every link an oligo that joins the end of one node to the
    start of the next, so ligation builds strands that spell random paths of the graph. The tube starts with edge oligos
    drawn uniformly from the links, which meet in random pairs and join when the end of one is the start of the other.
    Adleman's filters then keep the strands that start at `start` and end at `end`, that pass through as many nodes as
    the graph has, and that visit every node, and any strand left is a Hamiltonian path. On the graph of Adleman's
    experiment, with seven nodes and fourteen links, solutions appear after some steps and every one of them is the
    path 0, 1, 2, 3, 4, 5, 6, while a graph without a Hamiltonian path leaves no strand.

    Args:
        n_strands:
            The number of strands in the tube.

        edges:
            The directed links of the graph, with the nodes numbered from 0.

        start:
            The node the paths start at.

        end:
            The node the paths end at.

        random_state:
            The seed or generator of the initial oligos.

    Returns:
        system:
            The system, with the group `strands` of paths `path`, padded with -1. Its standard observable `solutions`
            is the number of strands that pass the filters for the default nodes of Adleman's graph.

    Raises:
        ParameterError:
            The graph has no links, or the start or the end is not a node of it.

    Examples:
        >>> from skcomplex.systems.computer_science.automata import dna_computation
        >>> dna_computation(10).elements[0].values['path'].shape
        (10, 7)
    """
    nodes = {node for edge in edges for node in edge}
    if not edges or start not in nodes or end not in nodes:
        error_msg = f'The start {start!r} and the end {end!r} need to be nodes of a graph with links.'
        raise ParameterError(error_msg)
    rng = np.random.default_rng(random_state)
    paths = np.full((n_strands, len(nodes)), EMPTY)
    paths[:, :2] = np.asarray(edges)[rng.integers(len(edges), size=n_strands)]
    strands = GroupElement('strands', element=StrandElement, size=n_strands, values={'path': paths})
    return System(elements=[strands], interactions=[LigationInteraction('ligation', target='strands', edges=edges)])

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 system, with the cells cells.alive.

Examples:

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

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

@register_system(
    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 system, with the cells `cells.alive`.

    Examples:
        >>> from skcomplex.systems.computer_science.automata import elementary_automaton
        >>> elementary_automaton(90, size=11).elements[0].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(),
            ),
        ],
    )

fredkin_replicator(shape=(128, 128), *, initial=None, radius=4.0)

Return Fredkin's parity automaton, whose local law copies any initial pattern into translated replicas.

Every cell takes the sum modulo 2 of its four nearest neighbours, x(i, j, n + 1) = x(i - 1, j, n) + x(i + 1, j, n) + x(i, j - 1, n) + x(i, j + 1, n) (mod 2). The law is linear over the integers modulo 2, and raising it to the power 2^k gives the sum of the pattern translated by 2^k cells in each of the four directions, so at the times 2^k the initial pattern reappears four times, far enough apart not to overlap once 2^k exceeds its width, and at other times the copies multiply in more complex arrangements. By default the pattern is a circumference, as in Dilão's example.

Parameters:

Name	Type	Description	Default
shape	Sequence[int]	The number of rows and columns of the torus.	(128, 128)
initial	ArrayLike | None	The initial cells, an array of the shape, or None for a circumference of the radius in the middle.	None
radius	float	The radius of the default circumference.	4.0

Returns:

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

Examples:

>>> from skcomplex.systems.computer_science.automata import fredkin_replicator
>>> int(fredkin_replicator((32, 32)).elements[0].values['alive'].sum())
32

Source code in src/skcomplex/systems/computer_science/automata/_fredkin_replicator.py

@register_system(
    field='computer_science/automata',
    tags=('lattice', 'replicator', 'linear', 'parity'),
    references=('Fredkin 1990', 'Dilão 1993', 'Dilão 2023'),
    defaults={'until': 32, 'dt': 1},
)
def fredkin_replicator(
    shape: Sequence[int] = (128, 128),
    *,
    initial: npt.ArrayLike | None = None,
    radius: float = 4.0,
) -> System:
    """Return Fredkin's parity automaton, whose local law copies any initial pattern into translated replicas.

    Every cell takes the sum modulo 2 of its four nearest neighbours, `x(i, j, n + 1) = x(i - 1, j, n) +
    x(i + 1, j, n) + x(i, j - 1, n) + x(i, j + 1, n) (mod 2)`. The law is linear over the integers modulo 2, and
    raising it to the power `2^k` gives the sum of the pattern translated by `2^k` cells in each of the four
    directions, so at the times `2^k` the initial pattern reappears four times, far enough apart not to overlap once
    `2^k` exceeds its width, and at other times the copies multiply in more complex arrangements. By default the
    pattern is a circumference, as in Dilão's example.

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

        initial:
            The initial cells, an array of the shape, or `None` for a circumference of the radius in the middle.

        radius:
            The radius of the default circumference.

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

    Examples:
        >>> from skcomplex.systems.computer_science.automata import fredkin_replicator
        >>> int(fredkin_replicator((32, 32)).elements[0].values['alive'].sum())
        32
    """
    if initial is None:
        rows, columns = np.indices(tuple(shape))
        distance = np.hypot(rows - shape[0] // 2, columns - shape[1] // 2)
        values = (np.abs(distance - radius) < HALF_CELL).astype(float)
    else:
        values = 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((1, 3), (1, 3)),
                neighborhood=VonNeumannNeighborhood(),
            ),
        ],
    )

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.systems.computer_science.automata import free_group
>>> from skcomplex.core.components.spaces import CayleySpace
>>> CayleySpace(free_group(3), ball=1).prepare().generators_
('a', 'b', 'c')

Source code in src/skcomplex/systems/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.systems.computer_science.automata import free_group
        >>> from skcomplex.core.components.spaces import CayleySpace
        >>> CayleySpace(free_group(3), ball=1).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 system, with the cells cells.alive.

Examples:

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

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

@register_system(
    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 system, with the cells `cells.alive`.

    Examples:
        >>> from skcomplex.systems.computer_science.automata import free_group_automaton
        >>> free_group_automaton(radius=3).elements[0].prepare().size_
        53
    """
    space = CayleySpace(free_group(rank), ball=radius)
    return _majority_system(
        space,
        GeneratorNeighborhood(space.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 system, with the cells cells.alive.

Examples:

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

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

@register_system(
    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 system, with the cells `cells.alive`.

    Examples:
        >>> from skcomplex.systems.computer_science.automata import game_of_life
        >>> game_of_life((20, 30)).elements[0].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(),
            ),
        ],
    )

gap_subshift(size=120, *, gaps=None, random_state=0)

Return the shift on the S-gap subshift, the binary sequences whose runs of zeros between ones lie in S.

With S the even numbers it is the even subshift, strictly sofic and not of finite type (Ceccherini-Silberstein and Coornaert 2023, Exercises 1.85 and 1.92). The cells are a window of a configuration drawn from the measure of maximal entropy, whose gaps are independent with the probability λ^-(h + 1) of the gap h, where λ solves sum_(h in S) λ^-(h + 1) = 1 and log λ is the entropy. Every step shifts the window one cell to the left, and the cell entering on the right is a one with the probability that the gap since the last one ends there. A gap longer than the window counts as the window. Gaps are taken below ten times the size.

Parameters:

Name	Type	Description	Default
size	int	The number of cells of the window.	120
gaps	Sequence[int] | None	The allowed numbers of zeros between consecutive ones, the set S, or None for the even numbers.	None
random_state	int | Generator | None	The seed or generator of the initial window.	0

Returns:

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

Raises:

Type	Description
ParameterError	No allowed gap lies below ten times the size.

Examples:

>>> from skcomplex.systems.computer_science.automata import gap_subshift
>>> cells = gap_subshift(40).elements[0].values['alive']
>>> runs = [len(run) for run in ''.join(str(int(cell)) for cell in cells).strip('0').split('1') if run]
>>> all(run % 2 == 0 for run in runs)
True

Source code in src/skcomplex/systems/computer_science/automata/_shift_spaces.py

@register_system(
    field='computer_science/automata',
    tags=('subshift', 'S-gap', 'even shift', 'renewal', 'sofic'),
    references=('Ceccherini-Silberstein and Coornaert 2023',),
    defaults={'until': 100, 'dt': 1},
    observables=_density_observables,
)
def gap_subshift(
    size: int = 120,
    *,
    gaps: Sequence[int] | None = None,
    random_state: int | np.random.Generator | None = 0,
) -> System:
    """Return the shift on the S-gap subshift, the binary sequences whose runs of zeros between ones lie in `S`.

    With `S` the even numbers it is the even subshift, strictly sofic and not of finite type
    (Ceccherini-Silberstein and Coornaert 2023, Exercises 1.85 and 1.92). The cells are a window of a configuration
    drawn from the measure of maximal entropy, whose gaps are independent with the probability `λ^-(h + 1)` of the gap
    `h`, where `λ` solves `sum_(h in S) λ^-(h + 1) = 1` and `log λ` is the entropy. Every step shifts the window one
    cell to the left, and the cell entering on the right is a one with the probability that the gap since the last one
    ends there. A gap longer than the window counts as the window. Gaps are taken below ten times the size.

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

        gaps:
            The allowed numbers of zeros between consecutive ones, the set `S`, or `None` for the even numbers.

        random_state:
            The seed or generator of the initial window.

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

    Raises:
        ParameterError:
            No allowed gap lies below ten times the size.

    Examples:
        >>> from skcomplex.systems.computer_science.automata import gap_subshift
        >>> cells = gap_subshift(40).elements[0].values['alive']
        >>> runs = [len(run) for run in ''.join(str(int(cell)) for cell in cells).strip('0').split('1') if run]
        >>> all(run % 2 == 0 for run in runs)
        True
    """
    _, probabilities, hazards = _gap_law(_gap_lengths(size, gaps))
    cells = _renewal_cells(size, probabilities, random_state)
    neighborhood = LatticeNeighborhood(tuple((offset,) for offset in range(1 - size, 2)))
    return System(
        elements=[
            LatticeElement(
                'cells',
                element=BinaryCellElement,
                space=LatticeSpace(size, boundary='fixed', fill=OUTSIDE),
                values={'alive': cells},
            ),
        ],
        interactions=[
            LocalRuleInteraction(
                'shift',
                target='cells',
                state='alive',
                rule=functools.partial(_gap_shift, hazards=hazards),
                neighborhood=neighborhood,
                stochastic=True,
            ),
        ],
    )

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 system, with the cells cells.alive.

Examples:

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

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

@register_system(
    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 system, with the cells `cells.alive`.

    Examples:
        >>> from skcomplex.systems.computer_science.automata import grigorchuk_automaton
        >>> grigorchuk_automaton(radius=3).elements[0].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.systems.computer_science.automata import grigorchuk_group
>>> from skcomplex.core.components.spaces import CayleySpace
>>> CayleySpace(grigorchuk_group(), ball=1).prepare().generators_
('a', 'b', 'c', 'd')

Source code in src/skcomplex/systems/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.systems.computer_science.automata import grigorchuk_group
        >>> from skcomplex.core.components.spaces import CayleySpace
        >>> CayleySpace(grigorchuk_group(), ball=1).prepare().generators_
        ('a', 'b', 'c', 'd')
    """
    libgap.LoadPackage('automgrp')
    return libgap.AutomatonGroup(GRIGORCHUK_RECURSION)

group_difference_automaton(size=60, *, group=None, initial=None, random_state=0)

Return the automaton τ(x)(n) = x(n)^-1 x(n + 1) whose alphabet is a finite group, on a ring.

Over the integers, with the generator s0 = 1 of infinite order and a nontrivial group alphabet, the automaton is surjective but not injective (Ceccherini-Silberstein and Coornaert 2023, Exercise 3.24): every constant configuration maps to the identity. The ring is the finite quotient of order size, where the product of the image around the ring is the identity. Cells hold group elements by their number in the Cayley table of Sage, the identity first.

Parameters:

Name	Type	Description	Default
size	int	The number of cells of the ring.	60
group	PermutationGroup_generic | None	The finite group, a Sage permutation group, or None for the symmetric group of degree 3.	None
initial	ArrayLike | None	The initial numbers of the elements, or None for random ones.	None
random_state	int | Generator | None	The seed or generator of the random initial elements.	0

Returns:

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

Examples:

>>> from skcomplex.systems.computer_science.automata import group_difference_automaton
>>> group_difference_automaton(10).elements[0].prepare().size_
10

Source code in src/skcomplex/systems/computer_science/automata/_alphabets.py

@register_system(
    field='computer_science/automata',
    tags=('lattice', 'group alphabet', 'surjective', 'symmetric group'),
    references=('Ceccherini-Silberstein and Coornaert 2023',),
    defaults={'until': 30, 'dt': 1},
)
def group_difference_automaton(
    size: int = 60,
    *,
    group: PermutationGroup_generic | None = None,
    initial: npt.ArrayLike | None = None,
    random_state: int | np.random.Generator | None = 0,
) -> System:
    """Return the automaton `τ(x)(n) = x(n)^-1 x(n + 1)` whose alphabet is a finite group, on a ring.

    Over the integers, with the generator `s0 = 1` of infinite order and a nontrivial group alphabet, the automaton is
    surjective but not injective (Ceccherini-Silberstein and Coornaert 2023, Exercise 3.24): every constant
    configuration maps to the identity. The ring is the finite quotient of order `size`, where the product of the image
    around the ring is the identity. Cells hold group elements by their number in the Cayley table of Sage, the
    identity first.

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

        group:
            The finite group, a Sage permutation group, or `None` for the symmetric group of degree 3.

        initial:
            The initial numbers of the elements, or `None` for random ones.

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

    Returns:
        system:
            The system, with the group elements `cells.value`.

    Examples:
        >>> from skcomplex.systems.computer_science.automata import group_difference_automaton
        >>> group_difference_automaton(10).elements[0].prepare().size_
        10
    """
    alphabet = SymmetricGroup(3) if group is None else group
    product = np.asarray(alphabet.cayley_table().table(), dtype=np.intp)
    inverse = np.argmin(product, axis=1).astype(np.intp)
    if initial is None:
        values = np.random.default_rng(random_state).integers(0, product.shape[0], size).astype(float)
    else:
        values = np.asarray(initial, dtype=float)
    rule = functools.partial(_group_difference, product=product, inverse=inverse)
    return System(
        elements=[
            LatticeElement('cells', element=GroupCellElement, space=LatticeSpace(size), values={'value': values}),
        ],
        interactions=[
            LocalRuleInteraction('difference', target='cells', state='value', rule=rule, neighborhood=FORWARD),
        ],
    )

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.systems.computer_science.automata import heisenberg
>>> from skcomplex.core.components.spaces import CayleySpace
>>> CayleySpace(heisenberg(), ball=1).prepare().generators_
('a', 'b')

Source code in src/skcomplex/systems/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.systems.computer_science.automata import heisenberg
        >>> from skcomplex.core.components.spaces import CayleySpace
        >>> CayleySpace(heisenberg(), ball=1).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 system, with the cells cells.alive.

Examples:

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

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

@register_system(
    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 system, with the cells `cells.alive`.

    Examples:
        >>> from skcomplex.systems.computer_science.automata import heisenberg_automaton
        >>> heisenberg_automaton(radius=2).elements[0].prepare().size_
        17
    """
    space = CayleySpace(heisenberg(), ball=radius)
    return _majority_system(
        space,
        GeneratorNeighborhood(space.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 system, with the cells cells.alive.

Raises:

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

Examples:

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

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

@register_system(
    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 system, with the cells `cells.alive`.

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

    Examples:
        >>> from skcomplex.systems.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(),
            ),
        ],
    )

involutive_automaton(n=3, *, size=80, density=0.6, initial=None, random_state=0)

Return a binary automaton on a ring that is its own inverse, with the minimal memory set {-1, 0, ..., n}.

A cell at the left end of a run of exactly n ones, the window alpha = 0 1^n 0, becomes 0, a cell just before a run of exactly n - 1 ones, the window beta = 0 0 1^(n - 1) 0, becomes 1, and every other cell keeps its value (Ceccherini-Silberstein and Coornaert 2023, Exercise 1.36). The two moves undo each other, so two steps return every configuration to itself, and the automaton is invertible with τ^-1 = τ.

Parameters:

Name	Type	Description	Default
n	int	The length of the runs of ones, at least 3.	3
size	int	The number of cells of the ring.	80
density	float	The probability that a cell starts at 1, when no initial cells are given.	0.6
initial	ArrayLike | None	The initial cells, or None for random ones.	None
random_state	int | Generator | None	The seed or generator of the random initial cells.	0

Returns:

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

Raises:

Type	Description
ParameterError	The run length is below 3.

Examples:

>>> from skcomplex.systems.computer_science.automata import involutive_automaton
>>> len(involutive_automaton(3).interactions[0].neighborhood.offsets)
5

Source code in src/skcomplex/systems/computer_science/automata/_line_automata.py

@register_system(
    field='computer_science/automata',
    tags=('lattice', 'cellular automaton', 'invertible', 'involution'),
    references=('Ceccherini-Silberstein and Coornaert 2023',),
    defaults={'until': 10, 'dt': 1},
    observables=_density_observables,
)
def involutive_automaton(
    n: int = 3,
    *,
    size: int = 80,
    density: float = 0.6,
    initial: npt.ArrayLike | None = None,
    random_state: int | np.random.Generator | None = 0,
) -> System:
    """Return a binary automaton on a ring that is its own inverse, with the minimal memory set `{-1, 0, ..., n}`.

    A cell at the left end of a run of exactly `n` ones, the window `alpha = 0 1^n 0`, becomes 0, a cell just before a
    run of exactly `n - 1` ones, the window `beta = 0 0 1^(n - 1) 0`, becomes 1, and every other cell keeps its value
    (Ceccherini-Silberstein and Coornaert 2023, Exercise 1.36). The two moves undo each other, so two steps return every
    configuration to itself, and the automaton is invertible with `τ^-1 = τ`.

    Args:
        n:
            The length of the runs of ones, at least 3.

        size:
            The number of cells of the ring.

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

        initial:
            The initial cells, or `None` for random ones.

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

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

    Raises:
        ParameterError:
            The run length is below 3.

    Examples:
        >>> from skcomplex.systems.computer_science.automata import involutive_automaton
        >>> len(involutive_automaton(3).interactions[0].neighborhood.offsets)
        5
    """
    if n < MIN_INVOLUTION_RUN:
        error_msg = f'The run length of the involutive automaton is at least 3, but it is {n}.'
        raise ParameterError(error_msg)
    values = _random_cells(size, density, random_state) if initial is None else np.asarray(initial, dtype=float)
    return _line_system(_involution, range(-1, n + 1), values)

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.systems.computer_science.automata import lamplighter
>>> from skcomplex.core.components.spaces import CayleySpace
>>> CayleySpace(lamplighter(), ball=1).prepare().generators_
('a', 'b')

Source code in src/skcomplex/systems/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.systems.computer_science.automata import lamplighter
        >>> from skcomplex.core.components.spaces import CayleySpace
        >>> CayleySpace(lamplighter(), ball=1).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 system, with the cells cells.alive.

Examples:

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

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

@register_system(
    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 system, with the cells `cells.alive`.

    Examples:
        >>> from skcomplex.systems.computer_science.automata import lamplighter_automaton
        >>> lamplighter_automaton(radius=3).elements[0].prepare().size_
        39
    """
    space = CayleySpace(lamplighter(), ball=radius)
    cells = _random_cells(space.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 system, with the colors cells.color and the ant cells.ant.

Examples:

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

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

@register_system(
    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 system, with the colors `cells.color` and the ant `cells.ant`.

    Examples:
        >>> from skcomplex.systems.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'),
            ),
        ],
    )

lenia(shape=(64, 64), *, initial=None, R=13.0, T=10.0, mu=0.15, sigma=0.015, beta=(1.0,), channels=1, kernels=None)

Return Lenia, a continuous automaton whose ring-kernel convolutions grow gliding, lifelike solitons.

The world is a torus of sites with values in [0, 1], and one step of 1 / T adds the growth map of the convolution of the world with a ring kernel and clips the result, A <- [A + G(K * A) / T] in [0, 1], with G(u) = 2 exp(-(u - mu)^2 / (2 sigma^2)) - 1 and the kernel of radius R, whose concentric rings peak at beta. The expanded universe of Chan (2020) has several channels and several kernels (source, destination, r, h, beta, mu, sigma), each of radius r R with its own growth map, which reads its source channel and grows its destination with the weight h over the sum of the weights into that destination, A_j <- [A_j + sum_k (h_k / h_j) G_k(K_k * A_i) / T], on worlds of three or more dimensions. By default the world holds Orbium unicaudatus, which glides across the torus at a steady speed while its mass stays near 71. Every step of the system is one update, so a unit of Lenia's time takes T steps.

Parameters:

Name	Type	Description	Default
shape	Sequence[int]	The number of sites along every axis of the torus, two or more axes.	(64, 64)
initial	ArrayLike | None	The initial values, an array of the shape shared by every channel, or one per channel, or None for Orbium in the middle of a two-dimensional world.	None
R	float	The radius of the kernels in sites.	13.0
T	float	The number of steps per unit time, the inverse of the increment of the update.	10.0
mu	float	The centre of the growth map of the single kernel.	0.15
sigma	float	The width of the growth map of the single kernel.	0.015
beta	Sequence[float]	The peaks of the concentric rings of the single kernel.	(1.0,)
channels	int	The number of channels of the world, from one to three.	1
kernels	Sequence[Kernel] | None	The kernels (source, destination, r, h, beta, mu, sigma) of the expanded universe, with the channels as indices, or None for the single kernel of mu, sigma, and beta on the first channel.	None

Returns:

Name	Type	Description
system	System	The system, with the values world.A, world.B, and world.C of the three channels of the sites, the last two at 0 for a world of one channel. Its standard observables mass_A, mass_B, and mass_C are the totals of the values of every channel.

Raises:

Type	Description
ParameterError	The world has fewer than two axes or not one to three channels, Orbium does not fit a default world, the initial values do not have the shape, or a kernel names a channel the world does not have.

Examples:

>>> from skcomplex.systems.computer_science.automata import lenia
>>> lenia().elements[0].values['A'].shape
(64, 64)

Source code in src/skcomplex/systems/computer_science/automata/_lenia.py

@register_system(
    field='computer_science/automata',
    tags=('lattice', 'continuous automaton', 'convolution', 'soliton', 'artificial life', 'field'),
    references=('Chan 2019', 'Chan 2020'),
    defaults={'until': 200, 'dt': 1},
    observables=lambda system: [
        ObservableSpec(f'mass_{channel}', group='world', variable=channel, reduce=_mass) for channel in CHANNELS
    ],
)
def lenia(
    shape: Sequence[int] = (64, 64),
    *,
    initial: npt.ArrayLike | None = None,
    R: float = 13.0,
    T: float = 10.0,
    mu: float = 0.15,
    sigma: float = 0.015,
    beta: Sequence[float] = (1.0,),
    channels: int = 1,
    kernels: Sequence[Kernel] | None = None,
) -> System:
    """Return Lenia, a continuous automaton whose ring-kernel convolutions grow gliding, lifelike solitons.

    The world is a torus of sites with values in `[0, 1]`, and one step of `1 / T` adds the growth map of the
    convolution of the world with a ring kernel and clips the result, `A <- [A + G(K * A) / T]` in `[0, 1]`, with
    `G(u) = 2 exp(-(u - mu)^2 / (2 sigma^2)) - 1` and the kernel of radius `R`, whose concentric rings peak at `beta`.
    The expanded universe of Chan (2020) has several channels and several kernels
    `(source, destination, r, h, beta, mu, sigma)`, each of radius `r R` with its own growth map, which reads its
    source channel and grows its destination with the weight `h` over the sum of the weights into that destination,
    `A_j <- [A_j + sum_k (h_k / h_j) G_k(K_k * A_i) / T]`, on worlds of three or more dimensions. By default the world
    holds Orbium unicaudatus, which glides across the torus at a steady speed while its mass stays near 71. Every
    step of the system is one update, so a unit of Lenia's time takes `T` steps.

    Args:
        shape:
            The number of sites along every axis of the torus, two or more axes.

        initial:
            The initial values, an array of the shape shared by every channel, or one per channel, or `None` for
            Orbium in the middle of a two-dimensional world.

        R:
            The radius of the kernels in sites.

        T:
            The number of steps per unit time, the inverse of the increment of the update.

        mu:
            The centre of the growth map of the single kernel.

        sigma:
            The width of the growth map of the single kernel.

        beta:
            The peaks of the concentric rings of the single kernel.

        channels:
            The number of channels of the world, from one to three.

        kernels:
            The kernels `(source, destination, r, h, beta, mu, sigma)` of the expanded universe, with the channels as
            indices, or `None` for the single kernel of `mu`, `sigma`, and `beta` on the first channel.

    Returns:
        system:
            The system, with the values `world.A`, `world.B`, and `world.C` of the three channels of the sites, the
            last two at 0 for a world of one channel. Its standard observables `mass_A`, `mass_B`, and `mass_C` are the
            totals of the values of every channel.

    Raises:
        ParameterError:
            The world has fewer than two axes or not one to three channels, Orbium does not fit a default world, the
            initial values do not have the shape, or a kernel names a channel the world does not have.

    Examples:
        >>> from skcomplex.systems.computer_science.automata import lenia
        >>> lenia().elements[0].values['A'].shape
        (64, 64)
    """
    shape = tuple(shape)
    if len(shape) < MIN_AXES or not 1 <= channels <= len(CHANNELS):
        error_msg = f'Lenia needs two or more axes and one to three channels, but got {shape!r} and {channels!r}.'
        raise ParameterError(error_msg)
    values = _initial_values(shape, channels, initial)
    rings = ((0, 0, 1.0, 1.0, tuple(beta), mu, sigma),) if kernels is None else tuple(kernels)
    if any(not 0 <= index < channels for kernel in rings for index in kernel[:2]):
        error_msg = f'Every kernel needs a source and a destination among the {channels} channels.'
        raise ParameterError(error_msg)
    world = FieldElement(
        'world',
        element=LeniaSiteElement,
        space=LatticeSpace(shape),
        values={CHANNELS[index]: values[index] for index in range(channels)},
    )
    updates = [
        LeniaUpdateInteraction(
            f'update_{CHANNELS[index]}',
            target='world',
            channel=CHANNELS[index],
            kernels=[
                (CHANNELS[source], radius * R, weight, tuple(peaks), centre, width)
                for source, destination, radius, weight, peaks, centre, width in rings
                if destination == index
            ],
            T=T,
            n_dim=len(shape),
        )
        for index in range(channels)
        if any(kernel[1] == index for kernel in rings)
    ]
    return System(elements=[world], interactions=updates, time=DiscreteTime())

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.systems.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/systems/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.systems.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}})

life_in_a_tree(*, radius=4, density=0.3, initial=None, random_state=0)

Return the Game of Life on the free group F4, a tree of degree 8, surjective but not pre-injective.

The memory set is the identity and the generators a, b, c, d with their inverses, and a cell is alive after a step when the sum over the memory set is 3, or 4 with the cell alive, Conway's rule on the Cayley graph of F4 (Ceccherini-Silberstein and Coornaert 2023, Exercise 5.14). On the tree the automaton is surjective but not pre-injective, unlike Life on the plane, which is neither. Cells on the boundary of the ball read 0 outside it.

Parameters:

Name	Type	Description	Default
radius	int	The radius of the ball of F4.	4
density	float	The probability that a cell starts alive, when no initial cells are given.	0.3
initial	ArrayLike | None	The initial cells, one per site, or None for random ones.	None
random_state	int | Generator | None	The seed or generator of the random initial cells.	0

Returns:

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

Examples:

>>> from skcomplex.systems.computer_science.automata import life_in_a_tree
>>> life_in_a_tree(radius=2).elements[0].prepare().size_
65

Source code in src/skcomplex/systems/computer_science/automata/_free_group_automata.py

@register_system(
    field='computer_science/automata',
    tags=('group', 'cellular automaton', 'life', 'free group', 'Garden of Eden'),
    references=('Ceccherini-Silberstein and Coornaert 2023',),
    defaults={'until': 20, 'dt': 1},
    observables=_density_observables,
)
def life_in_a_tree(
    *,
    radius: int = 4,
    density: float = 0.3,
    initial: npt.ArrayLike | None = None,
    random_state: int | np.random.Generator | None = 0,
) -> System:
    """Return the Game of Life on the free group F4, a tree of degree 8, surjective but not pre-injective.

    The memory set is the identity and the generators `a`, `b`, `c`, `d` with their inverses, and a cell is alive after
    a step when the sum over the memory set is 3, or 4 with the cell alive, Conway's rule on the Cayley graph of F4
    (Ceccherini-Silberstein and Coornaert 2023, Exercise 5.14). On the tree the automaton is surjective but not
    pre-injective, unlike Life on the plane, which is neither. Cells on the boundary of the ball read 0 outside it.

    Args:
        radius:
            The radius of the ball of F4.

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

        initial:
            The initial cells, one per site, or `None` for random ones.

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

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

    Examples:
        >>> from skcomplex.systems.computer_science.automata import life_in_a_tree
        >>> life_in_a_tree(radius=2).elements[0].prepare().size_
        65
    """
    space = CayleySpace(free_group(TREE_RANK), ball=radius)
    size = space.prepare().size_
    if initial is None:
        cells = (np.random.default_rng(random_state).random(size) < density).astype(float)
    else:
        cells = np.asarray(initial, dtype=float)
    return System(
        elements=[LatticeElement('cells', element=BinaryCellElement, space=space, values={'alive': cells})],
        interactions=[
            LocalRuleInteraction(
                'life',
                target='cells',
                state='alive',
                rule=life((3,), (2, 3)),
                neighborhood=GeneratorNeighborhood(space.generators_, center=False),
            ),
        ],
    )

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 system, with the cells cells.value.

Examples:

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

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

@register_system(
    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 system, with the cells `cells.value`.

    Examples:
        >>> from skcomplex.systems.computer_science.automata import linear_ring_automaton
        >>> linear_ring_automaton(11).elements[0].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(),
            ),
        ],
    )

morse_subshift(axiom='0')

Return the Thue-Morse substitution 0 → 01, 1 → 10, whose words make the language of the Morse subshift.

Generation n from 0 is the prefix T(0) ... T(2^n - 1) of the Thue-Morse sequence, and the Morse subshift is the orbit closure under the shift of the configuration x(n) = T(n) for n >= 0 and T(-n - 1) for n < 0, an infinite minimal subshift that is not sofic, with zero entropy (Ceccherini-Silberstein and Coornaert 2023, Exercises 3.51 and 3.52). Its words of every length are the factors of the generations, which number at most a multiple of their length.

Parameters:

Name	Type	Description	Default
axiom	str	The word at generation 0, 0 for the Thue-Morse sequence and 1 for its mirror.	'0'

Returns:

Name	Type	Description
system	System	The system, with the word morse and its length morse.size.

Examples:

>>> from skcomplex.systems import create_simulation
>>> create_simulation('morse_subshift').prepare().run(until=3).trajectory_.values('morse.size').tolist()
[1.0, 2.0, 4.0, 8.0]

Source code in src/skcomplex/systems/computer_science/automata/_shift_spaces.py

@register_system(
    field='computer_science/automata',
    tags=('subshift', 'Thue-Morse', 'substitution', 'minimal', 'rewriting system'),
    references=('Ceccherini-Silberstein and Coornaert 2023',),
    defaults={'compiler': RewritingCompiler(), 'until': 10, 'dt': 1},
)
def morse_subshift(axiom: str = '0') -> System:
    """Return the Thue-Morse substitution `0 → 01`, `1 → 10`, whose words make the language of the Morse subshift.

    Generation `n` from `0` is the prefix `T(0) ... T(2^n - 1)` of the Thue-Morse sequence, and the Morse subshift is
    the orbit closure under the shift of the configuration `x(n) = T(n)` for `n >= 0` and `T(-n - 1)` for `n < 0`, an
    infinite minimal subshift that is not sofic, with zero entropy (Ceccherini-Silberstein and Coornaert 2023,
    Exercises 3.51 and 3.52). Its words of every length are the factors of the generations, which number at most a
    multiple of their length.

    Args:
        axiom:
            The word at generation 0, `0` for the Thue-Morse sequence and `1` for its mirror.

    Returns:
        system:
            The system, with the word `morse` and its length `morse.size`.

    Examples:
        >>> from skcomplex.systems import create_simulation
        >>> create_simulation('morse_subshift').prepare().run(until=3).trajectory_.values('morse.size').tolist()
        [1.0, 2.0, 4.0, 8.0]
    """
    return System(elements=[MorseElement('morse', axiom=axiom, alphabet='01')])

muller_automaton(*, radius=5, modulus=2, initial=None, random_state=0)

Return Muller's automaton on the free group F2, pre-injective but not surjective.

The alphabet is A = H x H for the cyclic group H of order modulus, and every cell becomes p1(x(ga)) + p2(x(gb)) + p1(x(ga^-1)) + p2(x(gb^-1)), where p1(h, k) = (h, 0) and p2(h, k) = (k, 0) (Ceccherini-Silberstein and Coornaert 2023, Section 5.11). The image lies in H x {0}, so the automaton is not surjective, yet two configurations that differ on a finite set have different images, so it is pre-injective, which the Garden of Eden theorem forbids on amenable groups. For a prime modulus it is the linear automaton over K^2 of Section 8.10. Cells on the boundary of the ball read 0 outside it.

Parameters:

Name	Type	Description	Default
radius	int	The radius of the ball of F2.	5
modulus	int	The order of H, at least 2.	2
initial	ArrayLike | None	The initial pairs, an array of shape (sites, 2), or None for random ones.	None
random_state	int | Generator | None	The seed or generator of the random initial pairs.	0

Returns:

Name	Type	Description
system	System	The system, with the coordinates cells.first and cells.second.

Raises:

Type	Description
ParameterError	The modulus is below 2.

Examples:

>>> from skcomplex.systems.computer_science.automata import muller_automaton
>>> muller_automaton(radius=2).elements[0].prepare().size_
17

Source code in src/skcomplex/systems/computer_science/automata/_free_group_automata.py

@register_system(
    field='computer_science/automata',
    tags=('group', 'cellular automaton', 'free group', 'Garden of Eden'),
    references=('Ceccherini-Silberstein and Coornaert 2023',),
    defaults={'until': 10, 'dt': 1},
    observables=_pair_observables,
)
def muller_automaton(
    *,
    radius: int = 5,
    modulus: int = 2,
    initial: npt.ArrayLike | None = None,
    random_state: int | np.random.Generator | None = 0,
) -> System:
    """Return Muller's automaton on the free group F2, pre-injective but not surjective.

    The alphabet is `A = H x H` for the cyclic group `H` of order `modulus`, and every cell becomes
    `p1(x(ga)) + p2(x(gb)) + p1(x(ga^-1)) + p2(x(gb^-1))`, where `p1(h, k) = (h, 0)` and `p2(h, k) = (k, 0)`
    (Ceccherini-Silberstein and Coornaert 2023, Section 5.11). The image lies in `H x {0}`, so the automaton is not
    surjective, yet two configurations that differ on a finite set have different images, so it is pre-injective, which
    the Garden of Eden theorem forbids on amenable groups. For a prime modulus it is the linear automaton over `K^2` of
    Section 8.10. Cells on the boundary of the ball read 0 outside it.

    Args:
        radius:
            The radius of the ball of F2.

        modulus:
            The order of `H`, at least 2.

        initial:
            The initial pairs, an array of shape `(sites, 2)`, or `None` for random ones.

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

    Returns:
        system:
            The system, with the coordinates `cells.first` and `cells.second`.

    Raises:
        ParameterError:
            The modulus is below 2.

    Examples:
        >>> from skcomplex.systems.computer_science.automata import muller_automaton
        >>> muller_automaton(radius=2).elements[0].prepare().size_
        17
    """
    return _pair_system(_muller, radius=radius, modulus=modulus, initial=initial, random_state=random_state)

nilpotent_automaton(n=4, *, size=80, density=0.7, initial=None, random_state=0)

Return a binary automaton on a ring that is nilpotent of class n: n steps send every configuration to 0.

The memory set is {-1, 0, ..., n - 1}, and a cell becomes 0 when the whole window holds ones or when it is the left end of a run of ones, p(-1) = 0 and p(0) = 1, and keeps its value otherwise (Ceccherini-Silberstein and Coornaert 2023, Exercise 1.15). After one step every run of ones is shorter than n, and every further step removes the left end of each run, so n steps reach 0 and the run of n + 1 ones needs all of them. The exercise prints the memory set {-1, ..., n - 2}, whose class is n - 1, while its solution relies on {-1, ..., n - 1}, which this system takes.

Parameters:

Name	Type	Description	Default
n	int	The nilpotency class, at least 2.	4
size	int	The number of cells of the ring.	80
density	float	The probability that a cell starts at 1, when no initial cells are given.	0.7
initial	ArrayLike | None	The initial cells, or None for random ones.	None
random_state	int | Generator | None	The seed or generator of the random initial cells.	0

Returns:

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

Raises:

Type	Description
ParameterError	The class is below 2.

Examples:

>>> from skcomplex.systems.computer_science.automata import nilpotent_automaton
>>> len(nilpotent_automaton(3).interactions[0].neighborhood.offsets)
4

Source code in src/skcomplex/systems/computer_science/automata/_line_automata.py

@register_system(
    field='computer_science/automata',
    tags=('lattice', 'cellular automaton', 'nilpotent'),
    references=('Ceccherini-Silberstein and Coornaert 2023',),
    defaults={'until': 6, 'dt': 1},
    observables=_density_observables,
)
def nilpotent_automaton(
    n: int = 4,
    *,
    size: int = 80,
    density: float = 0.7,
    initial: npt.ArrayLike | None = None,
    random_state: int | np.random.Generator | None = 0,
) -> System:
    """Return a binary automaton on a ring that is nilpotent of class `n`: `n` steps send every configuration to 0.

    The memory set is `{-1, 0, ..., n - 1}`, and a cell becomes 0 when the whole window holds ones or when it is the
    left end of a run of ones, `p(-1) = 0` and `p(0) = 1`, and keeps its value otherwise
    (Ceccherini-Silberstein and Coornaert 2023, Exercise 1.15). After one step every run of ones is shorter than `n`,
    and every further step removes the left end of each run, so `n` steps reach 0 and the run of `n + 1` ones needs all
    of them. The exercise prints the memory set `{-1, ..., n - 2}`, whose class is `n - 1`, while its solution relies on
    `{-1, ..., n - 1}`, which this system takes.

    Args:
        n:
            The nilpotency class, at least 2.

        size:
            The number of cells of the ring.

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

        initial:
            The initial cells, or `None` for random ones.

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

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

    Raises:
        ParameterError:
            The class is below 2.

    Examples:
        >>> from skcomplex.systems.computer_science.automata import nilpotent_automaton
        >>> len(nilpotent_automaton(3).interactions[0].neighborhood.offsets)
        4
    """
    if n < MIN_NILPOTENT_CLASS:
        error_msg = f'The nilpotency class of the automaton is at least 2, but it is {n}.'
        raise ParameterError(error_msg)
    values = _random_cells(size, density, random_state) if initial is None else np.asarray(initial, dtype=float)
    return _line_system(_nilpotent, range(-1, n), values)

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 system, with the cells cells.alive.

Examples:

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

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

@register_system(
    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 system, with the cells `cells.alive`.

    Examples:
        >>> from skcomplex.systems.computer_science.automata import noisy_automata
        >>> noisy_automata(184, size=11).elements[0].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,
            ),
        ],
    )

power_series_automaton(size=31, *, order=8, field='QQ', initial=None)

Return the automaton τ(x)(n) = x(n) - t x(n + 1) over the ring K[[t]] of formal power series on a ring.

The alphabet K[[t]] has infinite dimension, and the automaton is bijective with the inverse sigma(y)(n) = sum_j t^j y(n + j), which is not continuous, so it is no cellular automaton (Ceccherini-Silberstein and Coornaert 2023, Exercise 1.37). The cells hold the series truncated at the order, which keeps every coefficient below it exact, since the coefficient of t^i of the image reads coefficients of t^i and t^(i - 1) alone. From the constant series 1 at one cell, the cells at step s hold C(s, k) (-t)^k at the k-th cell to the left, as long as k stays below the order.

Parameters:

Name	Type	Description	Default
size	int	The number of cells of the ring.	31
order	int	The number of coefficients kept.	8
field	str	The field K, 'QQ', 'RR', or 'GF(p)'.	'QQ'
initial	ArrayLike | None	The initial coefficients, an array of shape (size, order), or None for the series 1 in the middle cell.	None

Returns:

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

Examples:

>>> from skcomplex.systems.computer_science.automata import power_series_automaton
>>> power_series_automaton(5, order=3).elements[0].values['value'].shape
(5, 3)

Source code in src/skcomplex/systems/computer_science/automata/_alphabets.py

@register_system(
    field='computer_science/automata',
    tags=('lattice', 'infinite alphabet', 'power series', 'bijective'),
    references=('Ceccherini-Silberstein and Coornaert 2023',),
    defaults={'until': 12, 'dt': 1},
)
def power_series_automaton(
    size: int = 31,
    *,
    order: int = 8,
    field: str = 'QQ',
    initial: npt.ArrayLike | None = None,
) -> System:
    """Return the automaton `τ(x)(n) = x(n) - t x(n + 1)` over the ring `K[[t]]` of formal power series on a ring.

    The alphabet `K[[t]]` has infinite dimension, and the automaton is bijective with the inverse
    `sigma(y)(n) = sum_j t^j y(n + j)`, which is not continuous, so it is no cellular automaton
    (Ceccherini-Silberstein and Coornaert 2023, Exercise 1.37). The cells hold the series truncated at the order, which
    keeps every coefficient below it exact, since the coefficient of `t^i` of the image reads coefficients of `t^i` and
    `t^(i - 1)` alone. From the constant series 1 at one cell, the cells at step `s` hold
    `C(s, k) (-t)^k` at the `k`-th cell to the left, as long as `k` stays below the order.

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

        order:
            The number of coefficients kept.

        field:
            The field `K`, `'QQ'`, `'RR'`, or `'GF(p)'`.

        initial:
            The initial coefficients, an array of shape `(size, order)`, or `None` for the series 1 in the middle cell.

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

    Examples:
        >>> from skcomplex.systems.computer_science.automata import power_series_automaton
        >>> power_series_automaton(5, order=3).elements[0].values['value'].shape
        (5, 3)
    """
    ring = PowerSeriesSpec(order, field)
    if initial is None:
        values = np.zeros((size, order))
        values[size // 2, 0] = 1.0
    else:
        values = np.asarray(initial, dtype=float)
    rule = functools.partial(
        _power_series_difference,
        ring=ring,
        variable=ring.coefficients_of(ring.ring.gen()),
    )
    return System(
        elements=[
            LatticeElement(
                'cells',
                element=PowerSeriesCellElement,
                space=LatticeSpace(size),
                values={'ring': ring, 'value': values},
            ),
        ],
        interactions=[
            LocalRuleInteraction('difference', target='cells', state='value', rule=rule, neighborhood=FORWARD),
        ],
    )

real_quadratic_automaton(size=64, *, amplitude=0.25, initial=None, random_state=0)

Return the automaton τ(x)(n) = x(n + 1) - x(n)^2 over the reals on a ring.

It is pre-injective but not injective, since the constant configurations 0 and 1 both map to 0, and its image is dense but neither closed nor everything (Ceccherini-Silberstein and Coornaert 2023, Exercise 5.64). The square pulls the cells down at every step, and cells far from the origin run off to minus infinity.

Parameters:

Name	Type	Description	Default
size	int	The number of cells of the ring.	64
amplitude	float	The half width of the uniform initial values.	0.25
initial	ArrayLike | None	The initial values, or None for random ones.	None
random_state	int | Generator | None	The seed or generator of the random initial values.	0

Returns:

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

Examples:

>>> from skcomplex.systems.computer_science.automata import real_quadratic_automaton
>>> real_quadratic_automaton(8).elements[0].prepare().size_
8

Source code in src/skcomplex/systems/computer_science/automata/_alphabets.py

@register_system(
    field='computer_science/automata',
    tags=('lattice', 'infinite alphabet', 'reals', 'pre-injective'),
    references=('Ceccherini-Silberstein and Coornaert 2023',),
    defaults={'until': 6, 'dt': 1},
)
def real_quadratic_automaton(
    size: int = 64,
    *,
    amplitude: float = 0.25,
    initial: npt.ArrayLike | None = None,
    random_state: int | np.random.Generator | None = 0,
) -> System:
    """Return the automaton `τ(x)(n) = x(n + 1) - x(n)^2` over the reals on a ring.

    It is pre-injective but not injective, since the constant configurations 0 and 1 both map to 0, and its image is
    dense but neither closed nor everything (Ceccherini-Silberstein and Coornaert 2023, Exercise 5.64). The square
    pulls the cells down at every step, and cells far from the origin run off to minus infinity.

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

        amplitude:
            The half width of the uniform initial values.

        initial:
            The initial values, or `None` for random ones.

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

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

    Examples:
        >>> from skcomplex.systems.computer_science.automata import real_quadratic_automaton
        >>> real_quadratic_automaton(8).elements[0].prepare().size_
        8
    """
    if initial is None:
        values = np.random.default_rng(random_state).uniform(-amplitude, amplitude, size)
    else:
        values = np.asarray(initial, dtype=float)
    return System(
        elements=[
            LatticeElement('cells', element=RealCellElement, space=LatticeSpace(size), values={'value': values}),
        ],
        interactions=[
            LocalRuleInteraction('quadratic', target='cells', state='value', rule=_quadratic, neighborhood=FORWARD),
        ],
    )

self_indexed_shift(group=None, *, radius=4, initial=None, random_state=0)

Return the map τ(x)(g) = x(g · x(g)) over the group as alphabet, continuous and equivariant but no automaton.

Every cell holds a group element, the number of its site, and takes the value of the cell at the product of its site and its value, so the cell it reads moves with the configuration. On an infinite group no finite memory set describes the map, which is continuous and commutes with the shifts but is no cellular automaton (Ceccherini-Silberstein and Coornaert 2023, Example 1.8.2). The simulation truncates the group: on a ball, a product outside it reads -1, a value that names no element and stays, and a finite group, without a radius, keeps every product.

Parameters:

Name	Type	Description	Default
group	object | None	The group, a Sage or GAP group, or None for the free group of rank 2.	None
radius	int | None	The radius of the ball, or None for a finite group.	4
initial	ArrayLike | None	The numbers of the initial elements, one per site, or None for random ones.	None
random_state	int | Generator | None	The seed or generator of the random initial elements, drawn uniformly among the sites.	0

Returns:

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

Examples:

>>> from skcomplex.systems.computer_science.automata import self_indexed_shift
>>> self_indexed_shift(radius=2).elements[0].prepare().size_
17

Source code in src/skcomplex/systems/computer_science/automata/_alphabets.py

@register_system(
    field='computer_science/automata',
    tags=('group', 'infinite alphabet', 'equivariant', 'free group'),
    references=('Ceccherini-Silberstein and Coornaert 2023',),
    defaults={'until': 6, 'dt': 1},
)
def self_indexed_shift(
    group: object | None = None,
    *,
    radius: int | None = 4,
    initial: npt.ArrayLike | None = None,
    random_state: int | np.random.Generator | None = 0,
) -> System:
    """Return the map `τ(x)(g) = x(g · x(g))` over the group as alphabet, continuous and equivariant but no automaton.

    Every cell holds a group element, the number of its site, and takes the value of the cell at the product of its
    site and its value, so the cell it reads moves with the configuration. On an infinite group no finite memory set
    describes the map, which is continuous and commutes with the shifts but is no cellular automaton
    (Ceccherini-Silberstein and Coornaert 2023, Example 1.8.2). The simulation truncates the group: on a ball, a product
    outside it reads `-1`, a value that names no element and stays, and a finite group, without a radius, keeps every
    product.

    Args:
        group:
            The group, a Sage or GAP group, or `None` for the free group of rank 2.

        radius:
            The radius of the ball, or `None` for a finite group.

        initial:
            The numbers of the initial elements, one per site, or `None` for random ones.

        random_state:
            The seed or generator of the random initial elements, drawn uniformly among the sites.

    Returns:
        system:
            The system, with the group elements `cells.value`.

    Examples:
        >>> from skcomplex.systems.computer_science.automata import self_indexed_shift
        >>> self_indexed_shift(radius=2).elements[0].prepare().size_
        17
    """
    space = CayleySpace(free_group(2) if group is None else group, ball=radius, fill=NO_ELEMENT)
    size = space.prepare().size_
    if initial is None:
        values = np.random.default_rng(random_state).integers(0, size, size).astype(float)
    else:
        values = np.asarray(initial, dtype=float)
    return System(
        elements=[LatticeElement('cells', element=GroupCellElement, space=space, values={'value': values})],
        interactions=[
            LocalRuleInteraction(
                'translation',
                target='cells',
                state='value',
                rule=_translate,
                neighborhood=StateTranslationNeighborhood(),
            ),
        ],
    )

small_world_life(shape=(50, 50), *, p=0.0, density=0.3, random_state=0)

Return Conway's Game of Life on a small-world network rewired from the Moore lattice of a torus.

Every cell is a node linked to its eight Moore neighbours. The rewiring cuts two random links and joins the four loose ends the other way, which keeps every node at eight neighbours, and repeats it p times half the number of links, so a fraction of about p of the links becomes shortcuts across the torus. The rules of life are the same on the network: a dead cell with three live neighbours comes to life, and a live cell with two or three survives. For p = 0 the network is the lattice and the automaton is the Game of Life, and the shortcuts change the density of live cells it settles at, which serves as an order parameter of the rewiring.

Parameters:

Name	Type	Description	Default
shape	Sequence[int]	The number of rows and columns of the torus.	(50, 50)
p	float	The rewiring probability, the fraction of the links rewired.	0.0
density	float	The probability that a cell starts alive.	0.3
random_state	int | Generator | None	The seed or generator of the rewiring and of the initial cells.	0

Returns:

Name	Type	Description
system	System	The system, with the cells cells.alive, one per node in row-major order of the torus. Its standard observable density is the fraction of live cells.

Raises:

Type	Description
ParameterError	The rewiring probability is outside [0, 1].

Examples:

>>> from skcomplex.systems.computer_science.automata import small_world_life
>>> sorted({degree for _, degree in small_world_life((10, 10), p=0.2).elements[0].space.graph.degree()})
[8]

Source code in src/skcomplex/systems/computer_science/automata/_small_world_life.py

@register_system(
    field='computer_science/automata',
    tags=('network', 'life', 'small world', 'emergence'),
    references=('Watts and Strogatz 1998', 'Gros 2015'),
    defaults={'until': 100, 'dt': 1},
    observables=lambda system: [
        ObservableSpec('density', group='cells', variable='alive', reduce=_alive_fraction),
    ],
)
def small_world_life(
    shape: Sequence[int] = (50, 50),
    *,
    p: float = 0.0,
    density: float = 0.3,
    random_state: int | np.random.Generator | None = 0,
) -> System:
    """Return Conway's Game of Life on a small-world network rewired from the Moore lattice of a torus.

    Every cell is a node linked to its eight Moore neighbours. The rewiring cuts two random links and joins the four
    loose ends the other way, which keeps every node at eight neighbours, and repeats it `p` times half the number of
    links, so a fraction of about `p` of the links becomes shortcuts across the torus. The rules of life are the same
    on the network: a dead cell with three live neighbours comes to life, and a live cell with two or three survives.
    For `p = 0` the network is the lattice and the automaton is the Game of Life, and the shortcuts change the density
    of live cells it settles at, which serves as an order parameter of the rewiring.

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

        p:
            The rewiring probability, the fraction of the links rewired.

        density:
            The probability that a cell starts alive.

        random_state:
            The seed or generator of the rewiring and of the initial cells.

    Returns:
        system:
            The system, with the cells `cells.alive`, one per node in row-major order of the torus. Its standard
            observable `density` is the fraction of live cells.

    Raises:
        ParameterError:
            The rewiring probability is outside `[0, 1]`.

    Examples:
        >>> from skcomplex.systems.computer_science.automata import small_world_life
        >>> sorted({degree for _, degree in small_world_life((10, 10), p=0.2).elements[0].space.graph.degree()})
        [8]
    """
    if not 0 <= p <= 1:
        error_msg = f'The rewiring probability is {p!r}. Give a number in [0, 1].'
        raise ParameterError(error_msg)
    rng = np.random.default_rng(random_state)
    graph = _moore_torus(shape)
    swaps = round(p * graph.number_of_edges() / 2)
    if swaps:
        nx.double_edge_swap(graph, nswap=swaps, max_tries=100 * swaps, seed=int(rng.integers(2**31)))
    alive = (rng.random(graph.number_of_nodes()) < density).astype(float)
    cells = LatticeElement('cells', element=BinaryCellElement, space=NetworkSpace(graph), values={'alive': alive})
    return System(
        elements=[cells],
        interactions=[MapInteraction('life', target='cells', state='alive', function=_life)],
        time=DiscreteTime(),
    )

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 system, with the cells cells.alive.

Examples:

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

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

@register_system(
    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 system, with the cells `cells.alive`.

    Examples:
        >>> from skcomplex.systems.computer_science.automata import subshifts
        >>> subshifts(10).elements[0].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=GoldenCellElement, space=LatticeSpace(size))],
        interactions=[flips],
    )

subtraction_automaton(size=41, *, height=10, initial=None)

Return the automaton τ(x)(n) = max(0, x(n) - x(n + 1)) over the naturals, whose image is not closed.

The image of the configurations x_M, equal to M left of the origin and to max(0, M - n) from it, is the block of M ones from the origin. These blocks converge to the configuration of ones on the half line, which is no image, so the image of the automaton over the infinite alphabet N is not closed (Ceccherini-Silberstein and Coornaert 2023, Example 3.3.3). The cells sit on a segment with fixed ends that read 0, and start at x_M with M = height, its origin a quarter of the way along.

Parameters:

Name	Type	Description	Default
size	int	The number of cells.	41
height	int	The value M of the staircase.	10
initial	ArrayLike | None	The initial values, or None for the staircase.	None

Returns:

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

Raises:

Type	Description
ParameterError	The height is negative.

Examples:

>>> from skcomplex.systems.computer_science.automata import subtraction_automaton
>>> subtraction_automaton(12, height=3).elements[0].values['value'].tolist()
[3.0, 3.0, 3.0, 3.0, 2.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]

Source code in src/skcomplex/systems/computer_science/automata/_alphabets.py

@register_system(
    field='computer_science/automata',
    tags=('lattice', 'infinite alphabet', 'naturals', 'non-closed image'),
    references=('Ceccherini-Silberstein and Coornaert 2023',),
    defaults={'until': 10, 'dt': 1},
)
def subtraction_automaton(size: int = 41, *, height: int = 10, initial: npt.ArrayLike | None = None) -> System:
    """Return the automaton `τ(x)(n) = max(0, x(n) - x(n + 1))` over the naturals, whose image is not closed.

    The image of the configurations `x_M`, equal to `M` left of the origin and to `max(0, M - n)` from it, is the block
    of `M` ones from the origin. These blocks converge to the configuration of ones on the half line, which is no image,
    so the image of the automaton over the infinite alphabet `N` is not closed (Ceccherini-Silberstein and Coornaert
    2023, Example 3.3.3). The cells sit on a segment with fixed ends that read 0, and start at `x_M` with `M = height`,
    its origin a quarter of the way along.

    Args:
        size:
            The number of cells.

        height:
            The value `M` of the staircase.

        initial:
            The initial values, or `None` for the staircase.

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

    Raises:
        ParameterError:
            The height is negative.

    Examples:
        >>> from skcomplex.systems.computer_science.automata import subtraction_automaton
        >>> subtraction_automaton(12, height=3).elements[0].values['value'].tolist()
        [3.0, 3.0, 3.0, 3.0, 2.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
    """
    if height < 0:
        error_msg = f'The height of the staircase is a natural number, but it is {height}.'
        raise ParameterError(error_msg)
    if initial is None:
        origin = size // 4
        steps = np.arange(size) - origin
        values = np.where(steps < 0, height, np.maximum(0, height - steps)).astype(float)
    else:
        values = np.asarray(initial, dtype=float)
    return System(
        elements=[
            LatticeElement(
                'cells',
                element=PascalCellElement,
                space=LatticeSpace(size, boundary='fixed'),
                values={'value': values},
            ),
        ],
        interactions=[
            LocalRuleInteraction('subtraction', target='cells', state='value', rule=_subtract, neighborhood=FORWARD),
        ],
    )

surjective_linear_automaton(*, radius=5, modulus=2, initial=None, random_state=0)

Return a linear automaton over K^2 on the free group F2, surjective but not pre-injective.

Every cell becomes q1(x(ga)) + q1(x(ga^-1)) + q2(x(gb)) + q2(x(gb^-1)), where q1(h, k) = (h, 0) and q2(h, k) = (0, h), over the field of a prime number modulus of elements (Ceccherini-Silberstein and Coornaert 2023, Section 8.11). The configuration (0, 1) at the identity and 0 elsewhere maps to 0, so the automaton is not pre-injective, while a preimage of every configuration is built by induction on the word length, so it is surjective, which the Garden of Eden theorem forbids on amenable groups. Cells on the boundary of the ball read 0 outside it.

Parameters:

Name	Type	Description	Default
radius	int	The radius of the ball of F2.	5
modulus	int	The prime size of the field K.	2
initial	ArrayLike | None	The initial pairs, an array of shape (sites, 2), or None for random ones.	None
random_state	int | Generator | None	The seed or generator of the random initial pairs.	0

Returns:

Name	Type	Description
system	System	The system, with the coordinates cells.first and cells.second.

Raises:

Type	Description
ParameterError	The modulus is below 2.

Examples:

>>> from skcomplex.systems.computer_science.automata import surjective_linear_automaton
>>> surjective_linear_automaton(radius=2).elements[0].prepare().size_
17

Source code in src/skcomplex/systems/computer_science/automata/_free_group_automata.py

@register_system(
    field='computer_science/automata',
    tags=('group', 'cellular automaton', 'free group', 'linear', 'Garden of Eden'),
    references=('Ceccherini-Silberstein and Coornaert 2023',),
    defaults={'until': 10, 'dt': 1},
    observables=_pair_observables,
)
def surjective_linear_automaton(
    *,
    radius: int = 5,
    modulus: int = 2,
    initial: npt.ArrayLike | None = None,
    random_state: int | np.random.Generator | None = 0,
) -> System:
    """Return a linear automaton over `K^2` on the free group F2, surjective but not pre-injective.

    Every cell becomes `q1(x(ga)) + q1(x(ga^-1)) + q2(x(gb)) + q2(x(gb^-1))`, where `q1(h, k) = (h, 0)` and
    `q2(h, k) = (0, h)`, over the field of a prime number `modulus` of elements (Ceccherini-Silberstein and Coornaert
    2023, Section 8.11). The configuration `(0, 1)` at the identity and 0 elsewhere maps to 0, so the automaton is not
    pre-injective, while a preimage of every configuration is built by induction on the word length, so it is
    surjective, which the Garden of Eden theorem forbids on amenable groups. Cells on the boundary of the ball read 0
    outside it.

    Args:
        radius:
            The radius of the ball of F2.

        modulus:
            The prime size of the field `K`.

        initial:
            The initial pairs, an array of shape `(sites, 2)`, or `None` for random ones.

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

    Returns:
        system:
            The system, with the coordinates `cells.first` and `cells.second`.

    Raises:
        ParameterError:
            The modulus is below 2.

    Examples:
        >>> from skcomplex.systems.computer_science.automata import surjective_linear_automaton
        >>> surjective_linear_automaton(radius=2).elements[0].prepare().size_
        17
    """
    return _pair_system(_surjective_linear, radius=radius, modulus=modulus, initial=initial, random_state=random_state)

turing_machine(size=21, *, table=None, start='A')

Return a Turing machine, a head with an internal state that reads, writes, and moves on a tape of symbols.

The action table maps the internal state of the head and the symbol under it to the symbol it writes, its move 'L', 'R', or 'N', and its next internal state, 'H' to halt. Every step is a local rule on the cells of a ring of tape: the cell under the head takes the written symbol, and a cell takes the head that moves onto it. The default table is the busy beaver of three states and two symbols, which writes the most ones a halting machine of its size can write on a blank tape: it halts after 13 steps with six ones on the tape.

Parameters:

Name	Type	Description	Default
size	int	The number of cells of the ring of tape, large enough that the head never wraps around.	21
table	Mapping[tuple[str, int], tuple[int, str, str]] | None	The action table, or None for the three-state busy beaver.	None
start	str	The internal state of the head at the start, on the middle cell of a blank tape.	'A'

Returns:

Name	Type	Description
system	System	The system, with the symbols tape.symbol and the head tape.head, which holds the index of the internal state of the head, in the sorted order of the states of the table, on its cell, that index plus one when the head has halted, and -1 elsewhere.

Raises:

Type	Description
ParameterError	The start is not a state of the table, or a move is not 'L', 'R', or 'N'.

Examples:

>>> from skcomplex.systems.computer_science.automata import turing_machine
>>> int(turing_machine(11).elements[0].values['head'][5])
0

Source code in src/skcomplex/systems/computer_science/automata/_turing_machine.py

@register_system(
    field='computer_science/automata',
    tags=('lattice', 'turing machine', 'busy beaver', 'computation'),
    references=('Turing 1936', 'Radó 1962', 'Downey 2018'),
    defaults={'until': 20, 'dt': 1},
)
def turing_machine(
    size: int = 21,
    *,
    table: Mapping[tuple[str, int], tuple[int, str, str]] | None = None,
    start: str = 'A',
) -> System:
    """Return a Turing machine, a head with an internal state that reads, writes, and moves on a tape of symbols.

    The action table maps the internal state of the head and the symbol under it to the symbol it writes, its move
    `'L'`, `'R'`, or `'N'`, and its next internal state, `'H'` to halt. Every step is a local rule on the cells of a
    ring of tape: the cell under the head takes the written symbol, and a cell takes the head that moves onto it. The
    default table is the busy beaver of three states and two symbols, which writes the most ones a halting machine of
    its size can write on a blank tape: it halts after 13 steps with six ones on the tape.

    Args:
        size:
            The number of cells of the ring of tape, large enough that the head never wraps around.

        table:
            The action table, or `None` for the three-state busy beaver.

        start:
            The internal state of the head at the start, on the middle cell of a blank tape.

    Returns:
        system:
            The system, with the symbols `tape.symbol` and the head `tape.head`, which holds the index of the internal
            state of the head, in the sorted order of the states of the table, on its cell, that index plus one when
            the head has halted, and -1 elsewhere.

    Raises:
        ParameterError:
            The start is not a state of the table, or a move is not `'L'`, `'R'`, or `'N'`.

    Examples:
        >>> from skcomplex.systems.computer_science.automata import turing_machine
        >>> int(turing_machine(11).elements[0].values['head'][5])
        0
    """
    actions = BUSY_BEAVER if table is None else table
    states = sorted({state for state, _ in actions})
    if start not in states or any(move not in MOVES for _, move, _ in actions.values()):
        error_msg = f'The start {start!r} needs to be a state of the table, and every move one of L, R, or N.'
        raise ParameterError(error_msg)
    head = np.full(size, -1.0)
    head[size // 2] = states.index(start)
    tape = LatticeElement('tape', element=TapeCellElement, space=LatticeSpace(size), values={'head': head})
    return System(
        elements=[tape],
        interactions=[
            LocalRuleInteraction(
                'machine',
                target='tape',
                state=('symbol', 'head'),
                rule=_turing_rule(actions),
                neighborhood=BoxNeighborhood(),
                reads=('symbol', 'head'),
            ),
        ],
    )

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. Reduced modulo 2, the rule is the mirror image of the additive automaton x(n) + x(n + 1) of Ceccherini-Silberstein and Coornaert (2023, Example 3.3.8), which this system lifts to the nonnegative integers.

Parameters:

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

Returns:

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

Examples:

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

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

@register_system(
    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. Reduced modulo 2, the rule is the mirror image of the additive automaton
    `x(n) + x(n + 1)` of Ceccherini-Silberstein and Coornaert (2023, Example 3.3.8), which this system lifts to the
    nonnegative integers.

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

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

    Examples:
        >>> from skcomplex.systems.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),
        ],
    )