^^Rewriting system. Sistemi di riscrittura.

The Thue-Morse system is one of the classics.

1. rewrite rules    0→01, 1→10
2. start with string 1, and then keep updating it
3. updating:   applying 
   1. both rewrite rules
   2. to all the parts of the of the string
   3. simultaneously.

Sequence of strings generated

1,  10,  1001,  10010110,..

visualize

ref: richardsouthwell254/rewrite-systems

I like rewrite systems because the basic concepts are very simple, but the behavior you get out can be very elaborate and interesting.
This is good because it means that they are easy to understand, and watching them work, teaches us something about how complexity can emerge from simple settings.

slogan: "da stringa nasce stringa"

Esempi

Una Grammatica formale e' un particolare tipo di rewriting system.

Links wikipedia

1. Rewriting; Rewriting system
2. production rules for strings

Storia

Axel Thue

researchgate/Formal_grammars_and_languages

the Norwegian mathematician Axel Thue studied sequences of binary symbols subject to interesting mathematical properties, such as not having the same substring three times in a row. His work infuenced Emil Post, Stephen Kleene, and others to study the mathematical properties of strings and collections of strings.

1943: Post's rewriting system

Emil Post defines and studies a formal rewriting system using productions. With this, the process of rediscovering Pannini in the West begins.