Incomputability theory, a subset of the natural numbers is calledsimple if it iscomputably enumerable (c.e.) and co-infinite (i.e. its complement is infinite), but every infinite subset of its complement is not c.e.. Simple sets are examples of c.e. sets that are notcomputable.

Simple sets were devised byEmil Leon Post in the search for a non-Turing-complete c.e. set. Whether such sets exist is known asPost's problem. Post had to prove two things in order to obtain his result: that the simple setA is not computable, and that theK, thehalting problem, does notTuring-reduce toA. He succeeded in the first part (which is obvious by definition), but for the other part, he managed only to prove amany-one reduction.

Post's idea was validated by Friedberg and Muchnik in the 1950s using a novel technique called thepriority 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 calledimmune if${\displaystyle I}$ is infinite, but for every index${\displaystyle e}$, we have${\displaystyle W_e\text{ infinite}⟹W_e⊈I}$. Or equivalently: there is no infinite subset of${\displaystyle I}$ that is c.e..
• A set${\displaystyle S\subseteq \mathbb{N}}$ is called simpleif it is c.e. and its complement is immune.
• A set${\displaystyle I\subseteq \mathbb{N}}$ is calledeffectively immune if${\displaystyle I}$ is infinite, but there exists a recursive function${\displaystyle f}$ such that for every index${\displaystyle e}$, we have that.
• A set${\displaystyle S\subseteq \mathbb{N}}$ is calledeffectively 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 calledhyperimmune 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 calledhypersimple 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.

• Computability theory