The Complexity of Braids, Cables, and Weaves Modeled with Stranded Cellular Automata

Year: 2017 Authors: Joshua Holden

Core claim

For certain stranded cellular automata configurations, the maximum possible repeat length can be bounded above and below by explicit functions of the pattern width.

Topics

cellular automata complexity, braids and weaves, repeat length bounds, interlacing strands

Domains

cellular automata, combinatorics, Möbius function, least common multiple, textile arts, weaving, knitting, crochet

Methods

rule-based modeling, periodicity analysis, upper and lower bounds, exhaustive case analysis

Media

strands, knitted patterns, crocheted cables, loom weaves

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Bridges 2017 Conference Proceedings

The Complexity of Braids, Cables, and Weaves Modeled with Stranded Cellular Automata

Joshua Holden Department of Mathematics, Rose-Hulman Institute of Technology 5500 Wabash Ave., Terre Haute, IN 47803, USA holden@rose-hulman.edu

Abstract

In a previous Bridges paper, the author and Lana Holden presented a system for modeling the depiction of one-dimensional strands in three-dimensional space, applicable to knitting, crochet, weaving, and other forms of artistic media depicting knots and other forms of interlacing strands. This system of Stranded Cellular Automata depends on the idea of a one-dimensional grid of cells that evolves through a time dimension according to specified rules. This paper starts an investigation of the complexity of the patterns produced by Stranded Cellular Automata, as measured by the length of the maximum possible repeat for a given width of pattern. Upper and lower bounds are given for special situations, although the general case remains open.

Introduction

Stranded Cellular Automata (SCAs), introduced in [3] and [2], are a way of modeling artwork that depicts one-dimensional strands in three-dimensional space. In particular, this includes knitted and crocheted cables and traditional loom weaves. SCAs borrow from Elementary Cellular Automata (see, e.g., [4]) the idea of a one-dimensional grid of cells that evolve through a time dimension, which is visually represented as a second spacial dimension with the starting row at the bottom. Each cell has eight possible states, corresponding to no strands, a vertical strand starting on the left, a vertical strand starting on the right, two vertical strands, a slanted strand starting on the left, a slanted strand starting on the right, two crossed strands right over left, or two crossed strands left over right. (Most of these can be seen in the figures below, where the different types of crossings are shown in different shades for emphasis. The states with crossed strands could be represented in knitting or crochet as a cable crossing.) The cells are stacked in a staggered grid, which resembles a brick wall, and the state of a given cell at time $t$ depends on the states of the two “neighbor” cells that touch it from below. This captures the idea that each crossing is affected by the crossings that “feed into” it.

For aesthetic and practical reasons, we restrict the set of possible rules. Firstly, we make sure that continuity of the strands is preserved. Secondly, we break each rule into two pieces. A “Turning Rule” determines whether stands are vertical or slanted, based on whether the strands in the neighbor cells are vertical, slanted, or absent. (Strands slanted one way cannot directly turn to slant the other way.) A “Crossing Rule” determines which strand is on top if the strands cross, depending on whether the strands in the neighbor cells are crossed and if so, which strand is on top. The rules are coded in binary using a system similar to the coding for Elementary Cellular Automata in [6]; see [2] for a complete explanation of the coding.

Stranded Cellular Automata and Complexity

Cellular automata, even very simple ones, can produce very complex behavior. Stephen Wolfram conjectured in 1984 that Elementary Cellular Automaton Rule 30 exhibited aperiodic behavior, and this was proved by Erica Jen in 1986 [4, 5]. Even more interestingly, Rule 30 seems to display some of the characteristics

Holden

associated with continuous chaotic systems. [6, p. 871]. On the other hand, Matthew Cook proved in 1994 [1] that Rule 110 can be used to simulate any Turing machine, making it computationally universal.

Our investigations into Stranded Cellular Automata have assumed a cylindrical finite-width grid, so by the Pigeonhole Principle all behavior will eventually be periodic in both the space and time dimensions. This limits the complexity of the behavior, ruling out chaotic or computationally universal behavior in this situation. The first question of complexity then becomes how long a repeat can be for a given width, i.e., the minimum number of time steps between identical configurations. Wolfram observed that the maximum repeat (over all possible rules and starting configurations) of an Elementary Cellular Automata extended to $q$ allowed cell types, with width $m$ , was at most

where $\mu (n)$ is the Möbius function. This comes from the fact that a row of length $m$ that consists of an even number of shorter rows cannot be part of a maximum length repeat. [6, p. 950]

Our first results will assume all strands in the system are slanted. (For example, the starting row may have all slanted strands and the turning rule might be 511, i.e., no turning.) These systems might be of particular interest to weavers, since they can be woven on a traditional loom if the pattern is rotated 45 degrees. If also every cell has two strands, then it was observed in [2] that this is a simulation of an Elementary Cellular Automaton and thus has maximum repeat at most $s_2(m)\le 2^m-2$ . (The same is true if every cell has two strands and all of the crossings are the same.) If not every cell has two strands, however, a longer repeat may be possible.

Proposition 1. Assume all strands are slanted. For a given width $m$ , no repeat can be longer than $m{2}^m-2m$ rows.

Proof. Since half the rows are shifted relative to the other half, there are $2m$ positions that a strand can occupy. After $2m$ rows, all of the strands have returned to their original positions, as shown in Figure 1a. The only question is which strand of each crossing is on top.

(a) Turning Rule 511 and Crossing Rule 100. The bottom and top rows have the strands in the same place but the crossing pattern is different.

(b) Turning Rule 511 and Crossing Rule 257. The top row has the same crossing pattern as the fourth row from the bottom. Figure 1: Examples with all strands slanted and width $m=5$ . (Pictures by Lana Holden)

The Complexity of Braids, Cables, and Weaves Modeled with Stranded Cellular Automata

If there are $m$ crossings, then there are $2^m$ possible arrangements of the crossings, but only 2 possible arrangements of the positions of the strands, as shown in Figure 1b. So the maximum repeat in this case is the least common multiple of a number at most $2^m$ and a number at most $2$, which is therefore at most $2^m$.

On the other hand, if there are $m-1$ crossings, then there are $2^{m-1}$ possible arrangements of the crossings, but $2m$ possible arrangements of the positions of the strands, as shown in Figure 1a. So the maximum repeat is the least common multiple of a number at most $2^{m-1}$ and $2m$, which is therefore at most $2m(2^{m-1}-1)=m{2}^m-2m$. (The largest value of the least common multiple will be when the two numbers are relatively prime, so $2^{m-1}$ won’t give the maximum.) Any other number of crossings will have at most $2^{m-2}$ arrangements of the crossings and at most $2m$ positions of the strands, so will have less than $m{2}^m-2m$ rows in the repeat. ∎

Remark 1.

Since our example of maximum repeat has only three states, the repeat is also bounded by the function $s_3(m)$ defined earlier. The bound in the proposition is better, however.

We also have a lower bound for the maximum repeat if all strands are slanted.

Proposition 2.

Assume all strands are slanted. For a given width $m\ge 2^k$, the maximum repeat is at least $\mathrm{lcm}(2^{k+1},2m)$ rows long.

Proof.

The proof is by construction. Consider the starting row with $m-1$ crossings and one unpaired strand, as shown in Figure 1a. Once again, there are $2m$ different options for the positions of the strands, and each of these is distinct. If the configuration is considered modulo this shift in position, it can be shown that Crossing Rule 100 acts on this starting configuration with a repeat of $2^{k+1}$ when 2^{k}<m\leq 2^{k+1}. (The proof of this lemma is straightforward and uses the additivity of Crossing Rule 100. For more on additivity, see [6, p. 952].) The repeat is thus the least common multiple of $2^{k+1}$ and $2m$.

If $m=2^k$ then the repeat modulo the shift in position is only $2^k$. However, the repeat is then the least common multiple of $2^k$ and $2m=2^{k+1}$, which is the same as $\mathrm{lcm}(2^{k+1},2m)$. ∎

Remark 2.

For $m\le 5$ an exhaustive search shows that this lower bound is sharp. For $m=23$, using all $m$ crossings and Crossing Rule 257 (which is also additive) has a longer repeat. For large $m$, neither the upper bound of Proposition 1 nor this lower bound seems especially likely to be sharp.

When not all strands are slanted, not much is known. When only one or two strands are present and $m\le 5$, an exhaustive search shows that the maximum repeat is $(2m)(2m+1)$ rows long. This is achieved by Turning Rule 97, any crossing rule, and a starting row with two strands, as shown in Figure 2.

Future Work

Clearly we have just scratched the surface of possible results in this area. In the cases where all strands are slanted, we have upper and lower bounds for the maximum repeat but they are rather far apart and probably neither is sharp for large widths. The upper bound is in fact fairly naive and more analysis of the actual properties of Stranded Cellular Automata will likely improve it. The lower bound uses a construction relying on the specific properties of a particular additive rule. Investigation of other additive rules seems like a fruitful way to proceed in improving this bound.

As mentioned earlier, these cases are closely related to loom weaving patterns. It is not yet known exactly which weaving patterns can be produced by SCAs, but it may be possible to relate results on the complexity of SCAs to the number of possible monochrome weaving patterns. (Investigation of multicolor patterns would likely require an extension to the SCA framework involving colored strands. This would also be an interesting investigation.)

Holden

The next simplest category of SCAs to contemplate might be the one where both strands are present in every cell but both vertical and slanted strands are allowed, as in knitted and crocheted cables. Since only three types of cells are present the maximum repeat will be naively bounded by $s_3(m)$ but one can almost certainly do better. This analysis will be complicated by the fact that crossing rules and turning rules interact in this situation — the crossing rule uses information on whether the strands in the neighbor cells are crossing or not, and this is determined by the turning rule.

For SCAs with a small number of strands, the approach of exhaustive search immediately becomes more difficult with three strands. In that case the choice of crossing rule is likely to matter, and the starting configuration has potentially more relevant options as well.

Finally, there are other measures of complexity that could be investigated. We could ask what the computational complexity is of predicting what an SCA will do given its rules and starting configuration. For example, can we predict whether it will have maximum repeat? Or, can we predict whether it will return to the starting configuration, as opposed to entering a cycle that does not include that configuration? (The second possibility is illustrated by Figure 1b, which shows a repeat of length 6 that does not include the starting row.) This question of “pre-periodicity” is also related to the question of reversibility mentioned in [2] — a cellular automaton is called reversible if each possible state of a row is generated by exactly one state of the previous row. The question of which SCA rules are reversible has not yet been investigated. Another open question is whether a Stranded Cellular Automaton can simulate a Linear Bounded Automaton, which also operates on a finite-width grid.

References

[1] M. Cook, Universality in Elementary Cellular Automata, Complex Systems 15 (2004), no. 1, 1-40. This result was proven in 1994 [6, p. 1115] but was not published until 2004 for legal reasons. [2] Joshua Holden and Lana Holden, Modeling Braids, Cables, and Weaves with Stranded Cellular Automata, Proceedings of Bridges 2016: Mathematics, Music, Art, Architecture, Education, Culture, Tessellations Publishing, 2016, pp. 127-134. [3] Lana Holden, Knit Stranded Cellular Automata, Sockupied (Spring 2014), 10-11. [4] Erica Jen, Global Properties of Cellular Automata, Journal of Statistical Physics 43 (1986), no. 1, 219-242. [5] , Aperiodicity in One-Dimensional Cellular Automata, Physica D: Nonlinear Phenomena 45 (1990), no. 1-3, 3-18. [6] Stephen Wolfram, A New Kind of Science, Wolfram Media, Champaign, IL, 2002.

Figure 2: Turning Rule 97 on two strands, with width $m=4$ . The maximum possible repeat of length 72 is achieved. (Picture by Lana Holden)