Calculating Software Complexity Using the Halting Problem

Jonathan Bartlett (The Blyth Institute)

NOTE - this talk was removed from the conference due to time constraints, but will appear in the conference proceedings.

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 amount of resources required to modify certain program areas. Cyclomatic complexity is one of the primary estimators of software complexity which operates by counting branch points in software code (1). 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 (2). 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. (3) 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.

(1) McCabe, T. J. 1976. A Complexity Measure. Proceedings of the 2nd International Conference on Software Engineering.
(2) McDirmid, S. 2006. Turing Completeness Considered Harmful: Component Programming with a Simple Language. Unpublished manuscript.
(3) Bartlett, J. L. 2012. The Process of Programming: Using Turing Oracles in Cognitive Models of Problem-Solving. E&M 2012 Conference.