Enzymind Labs

 

What is simple?

Recursive sequences

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.

 

Recursive sequences

The primary algorithm that will be considered is a recursive symbol replacement system:

- Start with a set of symbols.

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

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

[ 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.]

 

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