Enzymind Labs

 

What is simple?

Recursive replacement sequences

History of L-Systems

The Thue-Morse sequence

References

 

What is simple?

"Simple" can mean easy to understand or easy to describe. Here it is used in a narrow sense; simple means that a full description is short. The sequences and patterns discussed are generated by a small set of short rules that are applied with a short algorithm. A system with a short description is often described as having a low, or short,  Kolmogorov complexity", or sometimes with terms like "low descriptive complexity, Kolmogorov-Chaitin complexity, stochastic complexity, algorithmic entropy, or program-size complexity". It is directly related (1)  to the principles of Minimum Message Length (MML), a formal information theory restatement of Occam's Razor.

 

D0L recursive replacement systems

The systems considered are all L-systems, the most basic form of string rewriting or recursive replacement. In formal language theory L-systems are classified as D0L, meaning deterministic and 0-context (context-free); and replacement is in parallel. This means that each symbol in the string is replaced according to a fixed set of rules, regardless what the surrounding symbols may be, and all symbols in the string are replaced simultaneously at each step. 

The general algorithm is a recursive symbol replacement system:

- Start with a set of symbols.

- Replace each symbol (simultaneously) with an ordered set of symbols, a unique set for each symbol.

- Repeat these last two steps indefinitely, using the new set of symbols as input.

[ To Do: Graphically, this algorithm will be represented like this particular system: ...]

[ To Do: To be complete, the allowed set of symbols should be specified... The spatial order is important... Notice that any one symbol can be replaced by a unique symbol without affecting the sequence... So swapping of symbols is allowed without changing the sequence or pattern... All symbols are replaced at the same time, not sequentially... Formal language description... Each symbol has a simple linear history, a one-dimensional ancestry of symbols... Not true for CA or some other types of recursive systems, neighborhood systems... ]

[To Do: Domain of the considered sequences]

[To Do: etc.]

 

History of L-Systems

From Some History of L-Systems

"In 1968 Aristid Lindenmayer , a biologist, introduced a formal method for modelling the development of plants. Now called L-systems, Lindenmayer's method is a type of rewriting system, a general tool for constructing complex objects by starting with a simple object and recursively replacing parts according to instructions provided by a set of rewriting rules. Although the basic ideas of rewriting systems have been known since the beginning of this century, they were not much used until the 1950s when Noam Chomsky applied them to describe the syntax of natural languages. A key difference between Lindenmayer's and Chomsky's uses of rewriting systems, illustrating the effectiveness of L-systems for fractals, is that Chomsky applied the rules sequentially while Lindenmayer applied them simultaneously.

Graphical representations of L-Systems were first published in 1974 by Frijters and Lindenmayer, and by Hogeweg and Hosper. The potential of L-systems for producing realistic images of plants was demonstrated in 1978 by Smith.

In 1979 Szilard and Quinton showed L-systems can generate fractal curves. In 1983 Siromoney and Subramanian used L-systems to space-filling curves. In 1982 Dekking found the dimension fo some curves generated by L-systems. In 1986 Prusinkiewicz produced more examples of fractals and plants generated by L-systems, using turtle graphics for the output. Also, he obtained 3-dimensional versions of L-systems.

Good references are Prusinkiewicz and Hanan, and Prusinkiewicz and Lindenmayer."

 

 

The Thue-Morse sequence

The Thue-Morse sequence is an aperiodic sequence of two symbols:

or

There are several methods for constructing the sequence. One algorithm involves repeated concatenation; start with one symbol (a, or a black square), concate its complementary symbol string (b, or a white square), and repeat this complementary concatenation using the results as the input to the next repetition.

A more general algorithm is a recursive symbol replacement system. Starting with a, replace a with a b and b with b a, and repeat these replacement rules indefinitely, always using the results from one generation as the input to the next repetition:

or

The algorithms are functionally equivalent, resulting in the same series of generations of symbol strings:


or

 

[To Do: List algorithms for generating the Thue-Morse sequence:

1) append complement of self

2) recursively replace a with a b, and b with b a

3) {append the mirrored complement of self

      append the mirror of self}

Note: This one seems more complicated than necessary, and it is ( it is reduced to method 2) ) for symbols that have no internal structure. But if the mirror of a symbol is not itself (like a motif that is not mirror symmetric), then this algorithm genereates a different result. It is necessary for consistancy with a 2-D triangular abstraction of the Thue-Morse sequence. See, for example, a 2-D slice through a symmetry plane of the 3-D Thue-Morse cube.

4) Sequential F2 sum of Period doubling sequence

 

[To Do: Period-doubling construction description.]

 

 

References

(1) Wallace and Dowe (1999a), "Minimum Message Length and Kolmogorov complexity", Comp. J., Vol 42, No. 4 (1999), pp270-283