Calculating Software Complexity Using the Halting Problem

Abstract

Calculating the complexity of software projects is important to software engineering as it helps in estimating the likely locations of bugs as well as the number of resources required to modify certain program areas. Cyclomatic complexity is one of the pri- mary estimators of software complexity which operates by counted branch points in software code. However, cyclomatic complexity assumes that all branch points are equally complex. Some types of branch points require more creativity and foresight to understand and program correctly than others. Specifically, when knowledge of the behavior of a loop or recursion requires solving a problem similar to the halting problem, that loop has intrinsically more complexity than other types of loops or conditions. Halting-problem-like problems can be detected by looking for loops whose termination conditions are not intrinsically bound in the looping construct. These types of loops are counted to find the program complexity. This metric is orthogonal to cyclomatic complexity (which remains useful) rather than as a substitute for it.