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.
Best Answer
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.)
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.