Computable set
≈ 2 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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.
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 S of the natural numbers is computable if there exists a total computable function f such that: f(x)=1 if x\in S 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
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 \Delta^0_1 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.
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.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1370344919 under CC BY-SA 4.0; modifications have been made.