Computable set

Uses your system voice; voice and rate in settings.

Snapshot

≈ 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.

Provenance

snapshot enwiki-001370344919 · captured 1787234834.0 · version history

Cite this page as: encyclopegia.org, “Computable set”, snapshot enwiki-001370344919. https://encyclopegia.org/a/computable-set

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.