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.

Static analysis

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

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: