Editing Computable set

{{Short description|Set with algorithmic membership test}}

In [[computability theory]], a [[Set (mathematics)|set]] of [[natural number]]s 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 <math>S</math> of the [[natural number]]s is '''computable''' if there exists a [[total function|total]] [[computable function]] <math>f</math> such that:

:<math>f(x)=1</math> if <math>x\in S</math>
:<math>f(x)=0</math> if <math>x\notin S</math>.

In other words, the set <math>S</math> is computable [[if and only if]] the [[indicator function]] <math>\mathbb{1}_{S}</math> is [[computable function|computable]].

==Examples==
*Every [[recursive language]] is a 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.<ref group="note" name="set-natural-number"/>
*The subset of [[prime number]]s is computable.
*The set of Gödel numbers is computable.<ref group="note" name="Gödel-numbers"/>

===Non-examples===
{{Main|List of undecidable problems}}
*The set of [[Halting problem|Turing machines that halt]] is not computable.
*The set of pairs of [[homeomorphism|homeomorphic]] finite [[simplicial complex]]es is not computable.<ref>{{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}}</ref>
*The set of [[Busy beaver#Non-computability|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 (set theory)|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 (set theory)|complement]] of ''A'' are both [[computably enumerable|computably enumerable(c.e.)]].
* The [[preimage]] of a computable set under a [[total function|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 <math>\Delta^0_1</math> 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 ==
*[[Computably enumerable]]
*[[Decidability (logic)]]
*[[Recursively enumerable language]]
*[[Recursive language]]
*[[Recursion]]

==Notes==
{{reflist|group=note|refs=
<ref name="set-natural-number">That is, under the [[Set-theoretic definition of natural numbers]], the set of natural numbers less than a given natural number is computable.</ref>
<ref name="Gödel-numbers">c.f. [[Gödel's incompleteness theorems]]; ''"On formally undecidable propositions of Principia Mathematica and related systems I"'' by Kurt Gödel.</ref>
}}

==References==
{{reflist}}

==Bibliography==
*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 ==
*{{MathWorld |title=Recursive Set |id=RecursiveSet |author=[[Alex Sakharov|Sakharov, Alex]]}}

{{Mathematical logic}}
{{Set theory}}

[[Category:Computability theory]]
[[Category:Theory of computation]]