Glider Hangs

The second most-common non-periodic hang are Glider Hangs. Once locked into this hang, DP only visits a small data sequence, typically consisting of only two data cells. It will decrease one counter, and while doing so, it increases another. When the first counter is zero, DP moves to the other, which then becomes the loop counter that is being decreased. This effectively moves the sub-sequence one position to either the right or left. If the number of iterations remains constant, it is still a hang but (also) a periodic one. If the number of iterations decreases, the meta-loop is eventually broken so the program is not (necessarily) hanging. So in the case of non-periodic glider hangs, the number of iterations of the inner-loop increases each time a new loop is started. Figure 1 shows a typical example.

More generally, a Glider Loop is a stationary loop where each loop iteration a) a loop counter is updated, and b) at least one other value is updated. Furthermore, the following should hold: c) the loop terminates when its loop counter becomes zero, and d) the next time the loop executes, DP is shifted such that the other value is now the loop counter.

Glider loops may update more values than the loop counter and the next loop counter. Two cases can be distinguished here. Such a value may either become a loop counter in a later iteration, or the value is never "consumed" by the loop but instead becomes an output value that is left in its wake.

A more complex glider hang

Figure 2 shows a program that ends up in a more complex glider hang. Its interpreted program is shown below.

 0: INC 1 =>  -/ 1
 1: SHR 1 =>  2/ 3
 2: INC 1 =>  -/ 4
 3: EXIT
 4: SHR 2 =>  5/ 6
 5: INC 1 =>  -/ 7
 6: DEC 1 => 20/21
 7: SHR 1 =>  8/ 9
 8: SHL 2 => 10/11
 9: SHL 2 => 10/11
10: DEC 2 =>  -/12
11: INC 1 => 14/15
12: INC 1 => 13/ 4
13: EXIT
14: SHR 1 => 18/19
15: DEC 2 => 16/17
16: INC 1 =>  -/ 7
17: SHL 2 => 13/ 4
18: EXIT
19: DEC 2 => 16/17
20: INC 2 =>  -/ 7
21: INC 2 => 22/ 7
22: SHL 1 => 10/11

After a while, the program enters a glider hang. The glider hang consists of a loop, with an increasing number of iterations, and a transition. A single iteration of the loop consists of 24 program blocks. That's already a lot, given the small grid size. However, the transition run block is even larger. It consists of 79 program blocks. The contents of both run blocks are shown below. The layout shows both the regularities and irregularities in their structure.

The loop      : 7 8 11 15    17 4 6 21
                7 9 11 14 19 17 4 6 21
                7 9 10 12       4 6 21
The transition:                     20
                7 9 10 12       4 6 21
                7 8 11 15    17 4 6 20
                7 9 11 14 19 16
                7 9 10 12       4 6 21
                7 8 11 15 16
                7 9 11 14 19 17 4 6 21 22
                    10 12 4 6       21
                7 8 10 12 4 5
                7 8 11 15    17 4 6 21
                7 9 11 14 19 17 4 6 21
                7 9 10 12       4 6 20