Co Halting Problem

computation

Definition

Co-Halting Problem

The co-halting problem is the complement of the halting problem. It asks whether a given program does not halt on a given input.

Instance: program $\Pi$, input string $I$
Question: Does $\Pi$ not terminate on $I$?

It is undecidable and not semi-decidable.

Relation to Halting Problem

The co-halting problem is the co-problem of the halting problem. If the halting problem is semi-decidable, then its complement is not.