Hang Detection

Hang detection is an important part of exhaustive search. Without it, the search would take too long. Furthermore, there is no certainty that the Busy Beaver is not overlooked because it was assumed to hang.

No Data hangs

The most simple type of hang is a No Data Hang. Here the program gets in a state where the program pointer repeatedly traverses the same path on the program grid and this path does not contain any DATA instructions. This means that the state of the data does not change. This in turn means that the program pointer always behaves the same when it encounters a TURN instruction. It will never exit this path, so the program hangs. Figure 1 shows an example of such a program.

Static analysis

Many hangs can be detected via static analysis of the interpreted program. This boils down to a single detection algorithm:

Figure 1. A program that gets stuck in a No Data hang.

Dynamic analysis

For hangs that cannot be detected statically, dynamic analysis can be used. Here the behaviour of the program is observed while it is being executed. Dynamic analysis has two main inputs:

  • How data changes over time
  • How program execution varies over time

For dynamic hang analysis, three program execution behaviors can be distinguished:

  • Periodic hangs. Here the program is stuck in a loop. The program repeatedly executes exactly the same set of instructions.
  • Meta-periodic hangs. Here the program carries out the same set of loops interspersed by some "transition" instructions. The behavior, however, is not periodic because the number of iterations for each loop is not constant. Typically, the number of iterations for each loop increases as program execution progresses.
  • More complex hang behaviors. Fortunately, these do not occur for small enough program grids so are not considered further here.

For more details see: