Sweep Hangs

The most common aperiodic hang is a Sweep Hang. Here DP sweeps across the data, going back and forth. It will extend the sequence at one or both ends while doing so. This causes the sequence to grow, which means that it takes increasingly more time to traverse the sequence, which is why the hang is not periodic.

Sweep Hangs require at a minimum two Sweep Loops. One sweep loop moves DP to the right. This loop exits when the sweep reaches the end of the sweep body. The program then starts executing the other sweep loop, which moves DP leftwards. In between both sweep loops the program may execute some transition instructions. Figure 1 shows a typical example of a Sweep Hang.

There are several characteristics that can be used to classify sweeps: how the sweeped sequence grows, how the sweeped sequence changes during each sweep, and how the sweep is implemented by one or more loops.

A sweep in a given direction can result in the following:

  • No growth. The sweep sequence does not grow in this direction. The sweep may always end at the same point. The hang in Figure 2 is an example. The rightward sweep ends when it encounters a zero and leaves this value unchanged. Figure 3 shows a sweep with multiple fixed end points at the left. The leftwards sweep ends on one of the two 1 values at the end of the sequence.
  • Constant growth. The sequence grows by the same amount each sweep iteration. Figure 1 shows a sweep with constant growth at both ends.
  • Periodic growth. The amount that the sequence grows is not constant but varies periodically. Figure 4 shows an example. The last non-zero value at the right is always increased by one. The sequence only grows when the value is 2; the value 1 is then appended to it.
  • Aperiodic growth. The sequence extends itself but does not grow periodically. Figure 5 gives an example. At the left of the sequence it counts in binary where -1 values are 0-bits and -2 values are 1-bits. When the count overflows, a bit is added and counting restarts from zero. So the number of sweep iterations required to extend the sequence at the left doubles each time the sequence grows there. This decrease in growth rate is typical for all a-periodic growths.

Figure 1. A typical Sweep Hang
Figure 2. Sweep with a fixed end point
Figure 3. Sweep with two end points
Figure 4. Sweep with periodic growth
Figure 5. Sweep with aperiodic growth

During a sweep, the sequence can be modified as follows:

  • Zero Delta. The sweep loop does not modify the sequence. This can be because the sweep loop consists of only shift instructions. The leftward sweep in Figure 2 is an example of this. It is also possible that the sweep loop includes instructions that modify the data values but that these cancel each other out. The rightward sweep in Figure 5 is an example of this.
  • Fixed Delta. The sweep changes the value of the sequence during traversal. Each value is changed by the same amount. The rightward sweep in Figure 4 is an example of this. It increases all values in the sequence by one during its traversal.
  • Varying Deltas. The values in the sequence change, but not all by the same amount. The leftward sweep in Figure 3 is an example where only a half of the values is changed. The leftward sweep in Figure 6 is an example where half of the values is increased, and the other half is decreased.

Figure 6. Sweep with oscillating values in body

The sweep in a given direction can be realized in multiple ways. For 6x6 programs the sweep can be realized as follows:

  • Single Loop. The entire sweep in a given direction is realized by executing a single loop. This is the most basic and common case. Both the leftward and rightward sweep in Figure 1 consist of a single loop.
  • Two Loops. The sweep in a given direction is realized using two loops. The rightwards sweep in Figure 7 is an example. The loop that traverses the 1 values is more complex than the loop that traverses the -1 values. Both loops behave the same in this case.

    Figure 8 shows a more complex example. The rightwards loop again consists of two loops, but these now behave differently. The first loop moves DP two positions each iteration, whereas the second loop moves DP only one position. An additional complication is that the sweep loops are separated by a Mid-sweep Transition Sequence. When transitioning from the first to the second loop several instructions are executed that are not part of either loop. Furthermore, the transition sequence differs between subsequent sweeps, at it depends on the value where the first loop ends.

Note, there is no fundamental restriction that limits a sweep in a given direction to two loops. When the program grid is sufficiently large, programs can be created that realize sweeps using three or more loops. However, the goal for my search program is to correctly classify all 6x6 hangs using logic that does not falsely classify larger programs as hanging. Given that, it suffices that the detection algorithm limits itself to this. As it turns out, this is complex enough.

Figure 7. Sweep consisting of two loops
Figure 8. Sweep consisting of two loops, separated by a varying transition sequence