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.

Figure 1. A typical glider hang

A more complex glider

Figure 2 shows a glider that is much more complex. 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

Figure 2. A glider with large run blocks