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
Formal definition
A subset of the
Examples and non-examples
Examples:
- Every finite or cofinitesubset 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 classof 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
A is a computable set
A is a computable set if and only if it is at level 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.
See also
References
- Cutland, N. Computability. Cambridge University Press, Cambridge-New York, 1980. ISBN 0-521-29465-7
- Rogers, H. The Theory of Recursive Functions and Effective Computability, MIT Press. 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