Self-indexed shift over a group alphabet
The map τ(x)(g) = x(g · x(g)) over the group as alphabet, continuous and equivariant but no automaton.
- Name:
self_indexed_shift - Field:
computer_science/automata - Formalism: lattice dynamics
- References: Ceccherini-Silberstein and Coornaert 2023
Select this system
from skcomplex.systems import create_simulation, create_system, describe
system = create_system('self_indexed_shift')
entry = describe('self_indexed_shift')
trajectory = create_simulation('self_indexed_shift').prepare().run().trajectory_
Factory
@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(),
),
],
)
Components
Elements:
GroupCellElement, fromElement
Interactions:
LocalRuleInteraction
class GroupCellElement(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.
Args:
label:
The label of the cell or the lattice group.
visual:
How the element is drawn, or `None` for `default_visual_`.
value:
The number of the initial group element, 0 for the identity.
Examples:
>>> from skcomplex.systems.computer_science.automata import GroupCellElement
>>> GroupCellElement('cell', value=2).value
2
"""
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
class LocalRuleInteraction(Interaction):
"""Local rule of a cellular automaton, which sets the next value of every cell from its ordered neighbourhood.
The rule is a table of the next value of every configuration of the neighbourhood, `TableSpec`, a rule of the sum
of the neighbourhood, `TotalisticSpec`, a rule of the cell and the sum of its neighbours, `OuterTotalisticSpec`, an
object whose `table()` returns a `TableSpec`, or a function. A function receives one array per neighbour of every
read state, in neighbourhood order, with one value per cell, the uniform array `random` when the rule is stochastic,
and the parameters of the bound group it names, and returns the next values of the states, one array per state. A
state of several components per cell, such as a truncated power series of `PowerSeriesSpec`, reaches a function as
one row of components per cell. A `StateTranslationNeighborhood` reads a group space at the product of every site
and the group element that the first read state holds there.
Args:
label:
The label of the interaction, unique among the parts of its system.
target:
The path of the group on the cells of a lattice, the nodes of a network, or a Cayley graph.
state:
The name of the state the rule sets, or a tuple of the names of the states it sets together.
rule:
The table, the totalistic rule, or the function.
neighborhood:
The ordered neighbourhood of every cell, such as `VonNeumannNeighborhood(center=True)`.
reads:
The names of the states whose neighbourhoods a function reads, or `None` for the states it sets.
schedule:
`'synchronous'`, `'random-sequential'`, `'random-site'`, `'checkerboard'`, or `'colored'`.
stochastic:
Whether a function receives the uniform random array `random`.
Raises:
ValidationError:
The state or the read states are not names, or the neighbourhood is not a neighbourhood.
Examples:
>>> from skcomplex.core.components.interactions import LocalRuleInteraction
>>> from skcomplex.core.components.spaces import VonNeumannNeighborhood
>>> from skcomplex.core.specs import TotalisticSpec
>>> parity = TotalisticSpec({1: 1, 3: 1})
>>> around = VonNeumannNeighborhood(n_dim=1, center=True)
>>> rule = LocalRuleInteraction('parity', target='cells', state='cell', rule=parity, neighborhood=around)
>>> rule.schedule
'synchronous'
"""
law_classes: ClassVar[tuple[type[BaseLaw], ...]] = (LocalRuleLaw,)
def __init__(
self,
label: str,
*,
target: Annotated[str, RoleSpec(elements=(ElementKind.ANY,), states=('state', 'reads'))],
state: str | tuple[str, ...],
rule: object,
neighborhood: BaseNeighborhood,
reads: Sequence[str] | None = None,
schedule: str = 'synchronous',
stochastic: bool = False,
) -> None:
super().__init__(label)
self.target = target
self.state = state
self.rule = rule
self.neighborhood = neighborhood
self.reads = reads
self.schedule = schedule
self.stochastic = stochastic
def _get_names(self) -> tuple[str, ...]:
"""Return the names of the states the rule sets."""
return (self.state,) if isinstance(self.state, str) else tuple(self.state)
def _check(self) -> None:
"""Raise an error for states that are not names, or a neighbourhood that is not one.
Raises:
ValidationError:
The state or the read states are not names, or the neighbourhood is not a neighbourhood.
"""
super()._check()
names = [*self._get_names(), *(self.reads or ())]
if not names or not all(isinstance(name, str) and name.isidentifier() for name in names):
error_msg = f'The local rule {self.label!r} sets {self.state!r} and reads {self.reads!r}. Give state names.'
raise ValidationError(error_msg)
if not isinstance(self.neighborhood, BaseNeighborhood):
error_msg = f'The neighbourhood of the local rule {self.label!r} is {self.neighborhood!r}. Give one.'
raise ValidationError(error_msg)
def _get_laws(self, namespace: SimpleNamespace) -> list[BaseLaw]:
"""Return the local rule law of the states of the target.
Args:
namespace:
The namespace of the symbols the laws can use, with `namespace.target`.
Returns:
laws:
The local rule law.
"""
targets = tuple(getattr(self._get_member(namespace, 'target'), name) for name in self._get_names())
reads = (
None
if self.reads is None
else tuple(getattr(self._get_member(namespace, 'target'), name) for name in self.reads)
)
return [
LocalRuleLaw(
targets[0] if isinstance(self.state, str) else targets,
self.neighborhood,
self.rule,
reads=reads,
schedule=self.schedule,
stochastic=self.stochastic,
label=self.label,
),
]