Computable set

In computability theory, a set of natural numbers is called computable, recursive, or decidable if there is an algorithm which takes a number as input, terminates after a finite amount of time (possibly depending on the given number) and correctly decides whether the number belongs to the set or not.

A set which is not computable is called noncomputable or undecidable.

A more general class of sets than the computable ones consists of the computably enumerable (c.e.) sets, also called semidecidable sets. For these sets, it is only required that there is an algorithm that correctly decides when a number is in the set; the algorithm may give no answer (but not the wrong answer) for numbers not in the set.

Formal definition

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

Examples and non-examples

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.

Properties

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 $\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.

References

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