Computable set
Set with algorithmic membership test
title: "Computable set" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["computability-theory", "theory-of-computation"] description: "Set with algorithmic membership test" topic_path: "technology/computing" source: "https://en.wikipedia.org/wiki/Computable_set" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0
::summary Set with algorithmic membership test ::
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. A set is noncomputable (or undecidable) if it is not computable.
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
Main article: List of undecidable problems
- The set of Turing machines that halt is not computable.
- The set of pairs of homeomorphic finite simplicial complexes is not computable.{{cite journal | last = Markov | first = A. | journal = Doklady Akademii Nauk SSSR | mr = 97793 | pages = 218–220 | title = The insolubility of the problem of homeomorphy | volume = 121 | year = 1958}}
- 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.
References
- That is, under the [[Set-theoretic definition of natural numbers]], the set of natural numbers less than a given natural number is computable.
- c.f. [[Gödel's incompleteness theorems]]; ''"On formally undecidable propositions of Principia Mathematica and related systems I"'' by Kurt Gödel.
::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::