# Turn sequences

I know this is old stuff, but I've been playing with what happens when you use an L-system to generate a binary sequence and then interpret that sequence as the directions for making left and right turns in a path through a grid. That is, we start with a simple seed string, such as "0", and strings \( x_0 \) and \( x_1, \) generate longer strings by simultaneously replacing every 0 in the shorter string by \( x_0 \) and every one by \( x_1, \) and use the expanded string to generate a sequence of turns.

These strings can generate several different types of shape:

Often (especially when the numbers of 0 and 1 digits in \( x_0 \) or \( x_1 \) differ by more than one from each other) the resulting path curls up on itself to fill a small region of the plane.

The Thue–Morse sequence generated by the expansions 0 → 01 and 1 → 10 produces a path that mostly follows a straight line, but with little bumps up and down. The pattern of the little bumps is itself a Thue–Morse sequence, reduced by a factor of four: each bump comes from four bits in the binary sequence.

Similar straight patterns tend to be generated when both \( x_0 \) and \( x_1 \) both have equal numbers of 0's and 1's.

It's possible that the expansion generates a simple curve. An easily-checked necessary (but not sufficient!) condition for this is that no concatenation of \( x_0 \) and \( x_1 \) should have more than two consecutive equal digits. The example below is generated by the expansions 0 → 010 and 1 → 011:

It may be the case that the finite strings generated at each stage of expansion generate simple curves but that the fractal limit of the curves is no longer simple, as in the two examples below generated by the expansions 0 → 001, 1 → 0011011 and 0 → 1001001, 1 → 0110110 respectively.

It's also possible, but rarer, to have self-intersections in the finite expansions that go away in the limit, leaving a simple curve. Here's one generated by the expansions 0 → 1 and 1 → 00110.

Strings whose expansions have three (but not four) consecutive equal digits may lead to curves that repeatedly touch themselves at vertices but do not cross themselves. The fractal tree pattern filling the triangle below is an example; it has the expansion rules 0 → 01100 and 1 → 011.

Similarly, the paperfolding sequence is generated by an expansion rule of a more complicated type, 11 → 1101, 01 → 1001, 10 → 1100, and 00 → 1000. As is well known, it generates the dragon curve, which completely fills a region of the plane with a fractal boundary.

And then, of course, there are plenty more that neither curl up on themselves nor make nice curves, instead producing some kind of self-intersecting fractal mess.

It makes me wonder how easy it is to predict from \( x_0 \) and \( x_1 \) what the behavior of the curve you get from them will be. In these examples, it seems one can get a clear idea of the behavior of the curve by making only a constant number of expansions. Is that true in general? Or does the number of expansions that are needed to detect a self-intersection at least grow slowly as a function of the lengths of \( x_0 \) and \( x_1 \)? And is it possible for a curve formed in this way to avoid any self-intersection and still fill a full-dimensional region of the plane?