I understand that Halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running or continue to run forever. That is, there are two options for HP: Halt (accept/reject) OR loop.

With this definition of HP, I am unable to understand what is co-HP, since any program can have only 2 options, Halt or loop, so what is co-HP? How do we even know co-HP exists?


The complement of a language $L$ is the language of all strings (over the same alphabet) not in $L$. So the complement of any language exists, by definition. It may be empty, which seems to be the case here.

However, your definition of HP is a bit strange, as every program for a given input either halts after a finite number of steps or does not. So, including both in HP obviously gives you all programs.

It might be more useful to consider something similar to the halting set $K := \{ (i, x) | \text{program $i$ halts when run on input $x$}\}$ (see wikipedia), i.e. the language of all programs that halt.

The complement of $K$ is then, of course, the set of all programs that do not halt.

| cite | improve this answer | |
  • 1
    $\begingroup$ To be picky, the complement of HP would also include any string over the alphabet that is not a valid encoding of a program/input pair. $\endgroup$ – Pontus Apr 28 '17 at 12:05
  • $\begingroup$ @Pontus, wouldn't that just be strings not accepted? Unless you mean to include strings outside of the alphabet entirely? $\endgroup$ – Ben I. Apr 28 '17 at 12:09
  • $\begingroup$ @Choirbean, I mean that if HP is the set of words over the alphabet that are valid encodings of a program/input pair such that the program halts on that input, then the complement of HP contains all words not in HP. This must include the program/input pairs that do not halt and also the words that are not valid encodings in the first place. (Checking if a word is a valid encoding or just nonsense is typically an easy syntactic check, so it's not really important in most settings to consider nonsense words, hence the pickiness of my comment.) $\endgroup$ – Pontus Apr 28 '17 at 12:17
  • 1
    $\begingroup$ @Pontus I just assumed that all strings over some alphabet are valid encodings. (not entirely unreasonable, I think. we can consider even syntactically 'invalid' programs 'valid' for our purposes if we interpret them as simply terminating with an error) You can be more picky, but that mostly depends on the exact method of formalizing and that is not the main point here. $\endgroup$ – Discrete lizard Apr 28 '17 at 12:21
  • $\begingroup$ @Discretelizard, I fully agree. $\endgroup$ – Pontus Apr 28 '17 at 12:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.