Computable set
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.
≈ 5 min read
Computable set. encyclopegia.org, snapshot enwiki-001370344919. /a/computable-set
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.
Definition
edit edit sourceA subset S of the natural numbers is computable if there exists a total computable function f such that:
- f(x)=1 if x∈S
- f(x)=0 if x∉S.
In other words, the set S is computable if and only if the indicator function 𝟙S is computable.
Examples
edit edit source- Every recursive language is computable.
- Every finite or cofinite subset of the natural numbers is computable.
- The subset of prime numbers is computable.
- The set of Gödel numbers is computable.[note 2]
Non-examples
edit edit source- The set of Turing machines that halt is not computable.
- The set of pairs of homeomorphic finite simplicial complexes is not computable.[1]
- The set of busy beaver champions is not computable.
- Hilbert's tenth problem is not computable.
Properties
edit edit sourceBoth 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 Δ10 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
edit edit source- Computably enumerable
- Decidability (logic)
- Recursively enumerable language
- Recursive language
- Recursion
Notes
edit edit source- ^ That is, under the Set-theoretic definition of natural numbers, the set of natural numbers less than a given natural number is computable. Wikipedia revision 1370344919, retrieved 2026-11-20
- ^ c.f. Gödel's incompleteness theorems; "On formally undecidable propositions of Principia Mathematica and related systems I" by Kurt Gödel. Wikipedia revision 1370344919, retrieved 2026-11-20
References
edit edit source- ^ Markov, A. (1958). "The insolubility of the problem of homeomorphy". Doklady Akademii Nauk SSSR. 121: 218–220. MR 0097793. Wikipedia revision 1370344919, retrieved 2026-11-20
Bibliography
edit edit source- 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
External links
edit edit source Mathematical logic(list),
paradoxes
systems
(list),
language,
syntax
theory
- Cartesian product
- Complement (i.e. set difference)
- De Morgan's laws
- Disjoint union
- Identities
- Intersection
- Power set
- Symmetric difference
- Union
- Concepts
- Methods
- Paradoxes
- Problems
Text derived from https://en.wikipedia.org/w/index.php?oldid=1370344919 under CC BY-SA 4.0; modifications have been made.