If I remove infinite loops, indirect self-referential loops, and recursion in a program written in a Turing-complete programming language, will the algorithm implicitly define a directed acyclic graph? In this scenario, can we show that the halting problem is less than NP-hard (perhaps NP-complete, NP, or even P)? The more general question is, under what conditions is the halting problem NP-complete or even P? Or, is the question of the halting problem applicable to the whole Turing-complete language specification rather than to the individual programs written in that language?