Decidability & Recursive Sets

Decidable versus merely semi-decidable, and why incompleteness blocks a decision procedure.

The idea

A recursive set is one whose membership an algorithm can decide. Let $A \subseteq \mathbb{N}$. The set $A$ is recursive, or decidable, when some algorithm, given any $n$, halts and answers correctly whether $n \in A$. The set $A$ is recursively enumerable, or semi-decidable, when some algorithm halts and says yes on exactly the members of $A$, and on a non-member may run forever without answering.

The two definitions separate the two ways an algorithm can fail: it can halt with the wrong answer, or it can fail to halt at all. Correctness rules out the first. Whether the second can also be ruled out is exactly the difference between deciding and enumerating.

Every recursive set is recursively enumerable, since a decider meets the weaker requirement. The converse fails, and a search shows the shape of the gap. Search for a proof, for a solution, for a computation that halts: when the object exists, the search finds it after finitely many steps and answers yes; when it does not, the search runs forever, and at no finite stage can "no" be distinguished from "not yet".

Ways to work on it

• Walkthrough. Recursive vs. recursively enumerable, Post's theorem, and the halting set.
• Practice. Classify a set or theory as recursive, merely recursively enumerable, or neither.
• Hardest. Pin down the decidability of a theory's theorem set and connect it to incompleteness.

Not sure where to start? Take the ten-question placement test.