haltsnegative

haltsnegative is a term occasionally used in discussions of computability theory to denote the decision problem of determining whether a given computer program does not halt on a given input. In practice, the concept corresponds to the complement of the halting problem. The standard formulation uses the same input encoding: given a program P and an input x, the problem asks whether P runs forever on x. The yes instances are those pairs where P does not halt, while the no instances are those where P halts.

Properties: The halting problem H = {<P, x> | P halts on x} is recursively enumerable (semi-decidable) and is complete for that class under many-one reductions. Its complement, the haltsnegative problem, is not recursively enumerable and is not decidable. This means there is no general algorithm that, for every P and x, can correctly decide non-halting, and there is no general procedure that will always confirm non-halting for all inputs.

Origins and usage: The term haltsnegative is not widely standardized; most literature refers to the non-halting problem or the complement of H. It is commonly used in theoretical expositions to illustrate undecidability and the limits of program verification. In practice, researchers study restricted variants where non-halting is decidable for specific classes of programs or encodings, or where semi-decidability can be achieved under certain assumptions.

Examples: A program that contains an unconditional infinite loop will not halt on the corresponding input, and such pairs are yes-instances of haltsnegative.

See also: Halting problem, Non-halting problem, Recursively enumerable, Undecidable problems, Reductions.