In computability theory, a subset of the natural numbers is called simple if it is computably 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 not computable.

Contents

• Relation to Post's problem
• Formal definitions and some properties
• Notes
• References

Relation to Post's problem

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 nonexistence of 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]

Formal definitions and some properties

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]

Notes

References

• 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.