Enzymind Labs

How might a Thue-Morse (TM) sequence occur through physical processes? Might something like a linear chain of algae, where two characteristics are TM along the chain, form naturally? Or a non-periodic crystal with molecular sheet structure in a TM sequence?

The Thue-Morse sequence is a two symbol non-periodic pattern: ABBABAABBAABABBA... The sequence can be formed by starting with one symbol (A), appending its complementary symbol string (A -> AB) and then repeating this operation indefinitely using the new string (A, AB, ABBA, ABBABAAB, ABBABAABBAABABBA, ...).

Is there a local cellular automata (CA) system that generates, as its current state, increasing length TM sub-strings? No, it has a nested structure requiring a rule based on the entire current sub-string: CA systems only use more or less local rules. [2008-10-15 Also yes! See Wolfram's examples of 1-D series of states, TM can appear as a "column", the sequence of states experienced by a particular cell. A cell's history can be TM.] There are many algorithms, including CA systems, that iteratively generate TM, but all require traversal of the previous sub-string or equivalently memory that encodes it.

The algorithm for a TM sequence descibed above resembles a physical folding: repeat (but not fold) the current TM substring across an endpoint and complement the new portion. AB->AB AB (repeat) and then -> AB BA (complement). But a fold operation involves a reflection, not a simple repeat, and a complement.

To illustrate, consider a directional sheet on edge, or linear band (Figure 1). The direction up (U) or down (D) are the symbols of the horizontal sequence. Starting with an unfolded U, after one fold the sequence is UD. After two folds the sequence is UDUD. Further folds result in an alternating, periodic sequence. The direction of the folding, to the left or right, at any step is irrelevant to the final sequence. There are other foldings that also lead to an alternating sequence.

Figure 1: Repeated folding of an directional sheet results in a periodic sequence.

Is there a way to fold a directional sheet to form a long TM sub-sequence? Yes.

For example the folds in Figure 2 form the first eight elements of a TM sequence starting with U. The shape has a mirror symmetry about the center, but the direction is anti-symmetric about the center.

Figure 2: Folding that results in the first eight elements of the Thue-Morse sequence.

This solution can't be extended to include more elements to the right, as the ends are enclosed. But it is not unique: Figure 3a shows another solution. This solution can be extended to the right, doubling the length of the folded sub-sequence (Figure 3b). This extension is essentially a translation of the right side folding pattern (and an inversion of the sheet direction).

Figure 3: Another folding that results in the first eight elements (a), and can be extended to the second eight elements (b), of the Thue-Morse sequence.

And a third similar solution with only the inner folds modified (Figure 4), can also be extended by translation.

Figure 4: A third solution for the first eight elements, that can also be extended by translation and inversion of sheet direction.

Are there more unique foldings for these first eight elements? I don't think so.

Although these foldings can't be extended to more than sixteen elements, the folding procedure can be used to include any length TM substring. Figure 5 shows a folding for the first sixteen elements, that can be extended to include the next sixteen by reflection. Is it unique?

Figure 5: A solution for the first sixteen elements, that can be extended to 32 elements by reflection.

What is the procedure, and can it be proved that it works for any TM sub-string? Will it work for any string that has a balanced number of symbols? An infinite string, such as a Bernoulli sequence?

It seems unlikely that this kind of nested folding could occur naturally. The procedure is not local; up to half the sub-string must be traversed to make a folding decision.

Also see:

Paper folding and the Dragon curve (fractal)

(concerning folding and the Rudin-Shapiro sequence):

Patrick Morton
Connections between binary patterns and paperfolding
Journal de théorie des nombres de Bordeaux, 2 no. 1 (1990), p. 1-12 (PDF )

"... there is the beautiful fact discovered by Mendès France that [the 1-D Rudin-Shapiro sequence is exactly the direction sequence of the paperfolding sequence obtained by folding a rectangular piece of paper alternately under and over the left edge (which is held fixed). (See [2] or [4].)

[2] M. Dekking, M. Mendès France and A. van der Poorten, Folds I,II III, Math. Intelligencer 4 (1982), 130-138, 173-181, 190-195. MR 684028 | Zbl 0493.10001

[4] P. Morton and W.J. Mourant, Paper folding, digit patterns and groups of arithmetic fractals, Proc. London Math. Soc. 59, 2, (1989), 253-293. MR 1004431 | Zbl 0694.10009

J. Dekking et al., Folds!, Math. Intelligencer 4 (1982). A series of 4 articles on paperfolding related to sequences.

Finite automata and arithmetic,  J.-P. Allouche