Wikipedia on the Halting Problem:

The conventional representation of decision problems is the set of objects possessing the property in question.

The halting set $K := \{ (i, x) ~|~ \textrm{program $i$ halts when run on input } x\}$ represents the halting problem.

(1) This set is recursively enumerable, which means there is a computable function that lists all of the pairs (i, x) it contains.

(2) However, the complement of this set is not recursively enumerable.

If possible, could someone provide a proof for (1) and (2)?

Thanks in advance.

  1. Run all possible programs on all possible inputs in parallel, and whenever a (program, input) pair halts, output it. (Running infinitely many things in parallel is simple; run the first n programs on the first n inputs for n steps, repeatedly, with n increasing by 1 each time.)

  2. If the complement were recursively enumerable, we could solve the halting problem by listing all halting and all non-halting (program, input) pairs until we find any particular pair we're interested in in one of the lists. We can't.


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.