In computability theory, a set of natural numbers is computable (or decidable or recursive) if there is an algorithm that computes the membership of every natural number in a finite number of steps.
Definition
A subset of the natural numbers is computable if there exists a total computable function such that:
if if .
In other words, the set is computable if and only if the indicator function is computable.
Examples Every recursive language is computable. Every finite or cofinite subset of the natural numbers is computable. The empty set is computable. The entire set of natural numbers is computable. Every natural number is computable. The subset of prime numbers is computable. The set of Gödel numbers is computable.
Non-examples
The set of Turing machines that halt is not computable. The set of pairs of homeomorphic finite simplicial complexes is not computable. The set of busy beaver champions is not computable. Hilbert's tenth problem is not computable.
Properties
Both A, B are sets in this section.
If A is computable then the complement of A is computable. If A and B are computable then: A ∩ B is computable. A ∪ B is computable. The image of A × B under the Cantor pairing function is computable.
In general, the image of a computable set under a computable function is computably enumerable, but possibly not computable.
A is computable 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 computable. The image of a computable set under a total computable bijection is computable.
A is computable if and only if it is at level of the arithmetical hierarchy.
A is computable if and only if it is either the image (or range) of a nondecreasing total computable function, or the empty set.
See also Computably enumerable Decidability (logic) Recursively enumerable language Recursive language Recursion
Notes
References
Bibliography Cutland, N. Computability. Cambridge University Press, Cambridge-New York, 1980. ; Rogers, H. The Theory of Recursive Functions and Effective Computability, MIT Press. ; Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987.
External links