Simple sets were devised by Emil Leon Post 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 a many-one reduction.

Post's idea was validated by Friedberg and Muchnik in the 1950s using a novel technique called the priority method. They give a construction for a set that is simple (and thus non-computable), but fails to compute the halting problem.^[1]

In what follows, ${\displaystyle W_{e}}$  denotes a standard uniformly c.e. listing of all the c.e. sets.

• A set ${\displaystyle I\subseteq \mathbb {N} }$  is called immune if ${\displaystyle I}$  is infinite, but for every index ${\displaystyle e}$ , we have ${\displaystyle W_{e}{\text{ infinite}}\implies W_{e}\not \subseteq I}$ . Or equivalently: there is no infinite subset of ${\displaystyle I}$  that is c.e..
• A set ${\displaystyle S\subseteq \mathbb {N} }$  is called simple if it is c.e. and its complement is immune.
• A set ${\displaystyle I\subseteq \mathbb {N} }$  is called effectively immune if ${\displaystyle I}$  is infinite, but there exists a recursive function ${\displaystyle f}$  such that for every index ${\displaystyle e}$ , we have that ${\displaystyle W_{e}\subseteq I\implies \#(W_{e})<f(e)}$ .
• A set ${\displaystyle S\subseteq \mathbb {N} }$  is called effectively simple if it is c.e. and its complement is effectively immune. Every effectively simple set is simple and Turing-complete.
• A set ${\displaystyle I\subseteq \mathbb {N} }$  is called hyperimmune if ${\displaystyle I}$  is infinite, but ${\displaystyle p_{I}}$  is not computably dominated, where ${\displaystyle p_{I}}$  is the list of members of ${\displaystyle I}$  in order.^[2]
• A set ${\displaystyle S\subseteq \mathbb {N} }$  is called hypersimple if it is simple and its complement is hyperimmune.^[3]

• Soare, Robert I. (1987). Recursively enumerable sets and degrees. A study of computable functions and computably generated sets. Perspectives in Mathematical Logic. Berlin: Springer-Verlag. ISBN 3-540-15299-7. Zbl 0667.03030.
• Odifreddi, Piergiorgio (1988). Classical recursion theory. The theory of functions and sets of natural numbers. Studies in Logic and the Foundations of Mathematics. Vol. 125. Amsterdam: North Holland. ISBN 0-444-87295-7. Zbl 0661.03029.
• Nies, André (2009). Computability and randomness. Oxford Logic Guides. Vol. 51. Oxford: Oxford University Press. ISBN 978-0-19-923076-1. Zbl 1169.03034.