NotHalt

NotHalt is a formal decision problem in computability theory. It asks, for a given Turing machine M and input w, whether M does not halt when run on w. In other words, NotHalt considers the complement of the classic Halting problem.

The Halting problem H is the set of pairs ⟨M, w⟩ such that M halts on w. NotHalt is the complement of H, consisting of all ⟨M, w⟩ where M does not halt on w. Consequently, NotHalt is co-recursively enumerable (co-RE) because its complement, H, is recursively enumerable (RE). NotHalt itself is not RE, and as a result, it is undecidable: there is no general algorithm that can determine non-termination for every possible machine-input pair.

In theoretical terms, NotHalt illustrates the asymmetry between proving termination and proving non-termination. While there are semi-decision procedures for detecting halting, proving non-termination for arbitrary programs is not generally possible. However, in restricted programming languages, specific systems, or particular inputs, termination or non-termination can sometimes be established through manual proofs or specialized static analyses.

NotHalt is primarily discussed in the context of computability and formal language theory, where it helps illuminate the limits of algorithmic analysis and the boundaries of decidability. It is closely related to foundational results about the Halting problem, its undecidability, and the broader implications for termination properties in computation.