computable set

A subset $S$ of the natural numbers is computable if there exists a total computable function $f$ such that:

:$f(x)=1$ if $x\backslash in\; S$

:$f(x)=0$ if $x\backslash notin\; S$.

In other words, the set $S$ is computable if and only if the indicator function $\backslash mathbb\{1\}\_\{S\}$ is computable.

• 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.
• The subset of prime numbers is computable.
• The set of Gödel numbers is computable.

{{Main|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.

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 $\backslash 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.

• Computably enumerable
• Decidability (logic)
• Recursively enumerable language
• Recursive language
• Recursion

{{reflist|group=note|refs=

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.

}}

{{reflist}}

• 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}}

• {{MathWorld |title=Recursive Set |id=RecursiveSet |author=Sakharov, Alex}}

{{Mathematical logic}}

{{Set theory}}

Category:Computability theory

Category:Theory of computation