Computable set
In computability theory, a set of natural numbers is computable if there is an algorithm that computes the membership of every natural number in a finite number of steps. A set is noncomputable if it is not computable.
Definition
A subset of the natural numbers is computable if there exists a total computable function such that: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
- 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.
- A is computable if and only if A and the complement of A are both computably enumerable.
- 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 either the image of a nondecreasing total computable function, or the empty set.