Extended Automata

This page documents the pedagogical extensions defined in fsm_tools.extended. These classes extend the formal Chomsky hierarchy with n-dimensional tape support, illustrating how a richer computational model can be built within the same grammar classification (see Automata in fsm-tools).

Note

The n-dimensional tape extension does not change the class of languages recognised. ExtendedTuringMachine still recognises exactly the same Type 0 languages as TuringMachine. This is a direct illustration of the Church-Turing thesis.

ExtendedTuringMachine

class fsm_tools.ExtendedTuringMachine(name: str, axes: int = 1, blank_symbol: str = '_', movement: dict | None = None, register: str = '', accept: str = 'OK', reject: str = 'nOK', chomsky: str = 'Recursively Enumerable')[source]

Bases: TuringMachine

A Turing Machine with an n-dimensional, bidirectionally infinite tape.

ExtendedTuringMachine extends the canonical TuringMachine by lifting two constraints:

  • Axes: the tape may have any number of dimensions (axes >= 1).

  • Direction: the tape is infinite in all directions — the head may move to negative positions in any dimension.

The tape is implemented as a dictionary mapping head position tuples to symbols, which naturally supports infinite extension in all directions without explicit memory management.

Grammar classification: chomsky="Recursively Enumerable" (Type 0), inherited from TuringMachine. The extended tape does not change the class of languages recognised.

Parameters:

  • name (str) – Name of the automaton.

  • axes (int) – Number of tape dimensions. Must be >= 1. Defaults to 1.

Initializes the Turing Machine with a given name and the blank symbol (defaults to “_”). Inherits from the base Automaton class and initializes the tape, head, index, and register. Also, the blank symbol is set, and accept/reject states are added to the machine.

Parameters:

  • name (str) – The name of the machine to be initialized.

  • axes (int) – The axes of the machine to be initialized.

  • blank_symbol (str | "_") – The blank symbol, representing an empty or uninitialized tape cell.

  • movement (dict) – dictionary of movement

  • register (str | "") – The current state of the Turing Machine. This is used to determine the next action based on the current state and the symbol under the head.

  • accept (str | "OK") – The accept state to be initialized.

  • reject (str | "nOK") – The reject state to be initialized.

read() → Any[source]

Read the symbol at the current head position.

Returns the blank symbol if the cell has not been written to.

Returns:

Symbol at the current head position.

Return type:

Any

write(symbol: Any) → None[source]

Write a symbol at the current head position.

If the symbol is not in the alphabet it is added automatically.

Parameters:

symbol (Any) – Symbol to write.

set_tape(content: List[Any], location: List[int] | None = None) → None[source]

Initialise the tape from a (possibly nested) list of symbols.

A 1D tape is passed as a flat list: ["a", "b", "c"]. A 2D tape is passed as a list of rows: [["a", "b"], ["c", "d"]]. The nesting depth must equal self.axes.

Parameters:

  • content (List[Any]) – Symbols to load onto the tape.

  • location (List[int] | None) – Starting head position. Defaults to the origin.

Raises:

ReadError – If any symbol is not in the alphabet.

ExtendedLBA

class fsm_tools.ExtendedLBA(name: str, tape_size: List[int], axes: int = 1, blank_symbol: str = '_', movement: dict | None = None, register: str = '', accept: str = 'OK', reject: str = 'nOK')[source]

Bases: ExtendedTuringMachine

A Linear Bounded Automaton with an n-dimensional bounded tape.

ExtendedLBA subclasses ExtendedTuringMachine and reintroduces the tape size limits of the Linear Bounded Automaton, applied independently to each dimension of the n-D tape.

Like ExtendedTuringMachine, it uses a dict-based tape. The head is blocked — with an IndexError — if it reaches a boundary in any dimension.

Grammar classification: chomsky="Context-Sensitive" (Type 1). The bounded tape restricts the class of languages recognised relative to ExtendedTuringMachine, exactly as in the formal Chomsky hierarchy.

Parameters:

  • name (str) – Name of the automaton.

  • tape_size (List[int]) – Maximum tape size for each dimension.

  • axes (int) – Number of tape dimensions. Must match len(tape_size).

Initializes the Turing Machine with a given name and the blank symbol (defaults to “_”). Inherits from the base Automaton class and initializes the tape, head, index, and register. Also, the blank symbol is set, and accept/reject states are added to the machine.

Parameters:

  • name (str) – The name of the machine to be initialized.

  • axes (int) – The axes of the machine to be initialized.

  • blank_symbol (str | "_") – The blank symbol, representing an empty or uninitialized tape cell.

  • movement (dict) – dictionary of movement

  • register (str | "") – The current state of the Turing Machine. This is used to determine the next action based on the current state and the symbol under the head.

  • accept (str | "OK") – The accept state to be initialized.

  • reject (str | "nOK") – The reject state to be initialized.

read() → Any[source]

Read the symbol at the current head position, enforcing tape bounds.

Returns:

Symbol at the current head position.

Return type:

Any

Raises:

IndexError – If the head is out of bounds.

write(symbol: Any) → None[source]

Write a symbol at the current head position, enforcing tape bounds.

Parameters:

symbol (Any) – Symbol to write.

Raises:

IndexError – If the head is out of bounds.

set_tape(content: List[Any], location: List[int] | None = None) → None[source]

Initialise the tape from a (possibly nested) list of symbols, validating content against the dimension limits.

Parameters:

  • content (List[Any]) – Symbols to load onto the tape.

  • location (List[int] | None) – Starting head position. Defaults to the origin.

Raises:

  • ValueError – If content in any dimension exceeds its limit.

  • ReadError – If any symbol is not in the alphabet.