Morse subshift

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

• Name: morse_subshift
• Field: computer_science/automata
• Formalism: rewriting system
• References: Ceccherini-Silberstein and Coornaert 2023

Select this system

from skcomplex.systems import create_simulation, create_system, describe

system = create_system('morse_subshift')
entry = describe('morse_subshift')
trajectory = create_simulation('morse_subshift').prepare().run().trajectory_

Factory

@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')])

Components

Elements:

• MorseElement, from WordElement

class MorseElement(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`.

    Args:
        label:
            The label of the word.

        axiom:
            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']
    """

    def _get_laws(self, s: SimpleNamespace) -> list[ProductionLaw]:
        """Return the productions of the Thue-Morse substitution.

        Args:
            s:
                The namespace of the symbols the laws can use.

        Returns:
            laws:
                The productions of the word.
        """
        del s
        return [ProductionLaw('0', '01'), ProductionLaw('1', '10')]