Computable set

In computability theory, a set of natural numbers is called computable, recursive, or decidable if there exists an algorithm that decides whether a given natural number is in the set after a finite amount of time (possibly depending on the given number). A set is noncomputable or undecidable if it is not computable.

There is a more general class of sets called semidecidable which consists of the computably enumerable (c.e.) sets. For these sets, it only requires the algorithm to decide the membership of a given natural number when the number is in the set. Otherwise, the algorithm run forever and nothing is returned.

A subset ${\displaystyle S}$ of the natural numbers is called computable if there exists a total computable function ${\displaystyle f}$ such that ${\displaystyle f(x)=1}$ if ${\displaystyle x\in S}$ and ${\displaystyle f(x)=0}$ if ${\displaystyle x\notin S}$. In other words, the set ${\displaystyle S}$ is computable if and only if the indicator function ${\displaystyle \mathbb {1} _{S}}$ is computable.

Examples:

• Every finite or cofinite subset of the natural numbers is computable. This includes these special cases:
  • The empty set is computable.
  • The entire set of natural numbers is computable.
  • Each natural number (as defined in standard set theory) is computable; that is, the set of natural numbers less than a given natural number is computable.
• The subset of prime numbers is computable.
• A recursive language is a computable subset of a formal language.
• The set of Gödel numbers of arithmetic proofs described in Kurt Gödel's paper "On formally undecidable propositions of Principia Mathematica and related systems I" is computable; see Gödel's incompleteness theorems.

Non-examples:

• The set of Turing machines that halt is not computable.
• The isomorphism class of two finite simplicial complexes is not computable.
• The set of busy beaver champions is not computable.
• Hilbert's tenth problem is not computable.

If A is a computable set then the complement of A is a computable set. If A and B are computable sets then A ∩ B, A ∪ B and the image of A × B under the Cantor pairing function are computable sets.

A is a computable set if and only if A and the complement of A are both computably enumerable (c.e.). The preimage of a computable set under a total computable function is a computable set. The image of a computable set under a total computable bijection is computable. (In general, the image of a computable set under a computable function is c.e., but possibly not computable).

A is a computable set if and only if it is at level ${\displaystyle \Delta _{1}^{0}}$ of the arithmetical hierarchy.

A is a computable set if and only if it is either the range of a nondecreasing total computable function, or the empty set. The image of a computable set under a nondecreasing total computable function is computable.

• Decidability (logic)
• Recursively enumerable language
• Recursive language
• Recursion

• Cutland, N. Computability. Cambridge University Press, Cambridge-New York, 1980. ISBN 0-521-22384-9; ISBN 0-521-29465-7
• Rogers, H. The Theory of Recursive Functions and Effective Computability, MIT Press. ISBN 0-262-68052-1; ISBN 0-07-053522-1
• Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. ISBN 3-540-15299-7

• Sakharov, Alex. "Recursive Set". MathWorld.