1.Previous
3.Next

in the search for a non-Turing-complete c.e. set. Whether such sets exist is known as Post's problem. Post had to prove two things in order to obtain his result: that the simple set A is not computable, and that the K, the halting problem, does not Turing-reduce to A. He succeeded in the first part (which is obvious by definition), but for the other part, he managed only to prove nonexistence of a many-one reduction.

1.Previous
3.Next