# Recursively enumerable sets: the halting set

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)?

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.