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 , input string
Question: Does not terminate on ?

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.