Turing machine (three-state busy beaver)
A Turing machine, a head with an internal state that reads, writes, and moves on a tape of symbols.
- Name:
turing_machine - Field:
computer_science/automata - Formalism: lattice dynamics
- References: Turing 1936; Radó 1962; Downey 2018
Select this system
from skcomplex.systems import create_simulation, create_system, describe
system = create_system('turing_machine')
entry = describe('turing_machine')
trajectory = create_simulation('turing_machine').prepare().run().trajectory_
Factory
@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'),
),
],
)
Components
Elements:
TapeCellElement, fromElement
Interactions:
LocalRuleInteraction
class TapeCellElement(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.
Args:
label:
The label of the cell or the lattice group.
visual:
How the element is drawn, or `None` for `default_visual_`.
symbol:
The initial symbol.
head:
The internal state of the head on the cell, from 0, or -1 for no head.
Examples:
>>> from skcomplex.systems.computer_science.automata import TapeCellElement
>>> TapeCellElement('cell').head
-1
"""
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
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,
),
]