The Halting Problem

Define, using The Software Principle, the sets:

Theorem

The sets and are Computably Enumerable.

Proof

Just run them. If they halt, great. If not then output is which is fine.

Theorem

The sets and are not Computable.

Proof

Suppose was computable. Let be the total computable indicator function for . Define the partial function:

Note that is computable, so find some s.t. . Now if then which is a contradiction. If then which is a contradiction. Thus is not computable. Similar works for .