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. A set is noncomputable (or undecidable) if it is not computable.

Definition

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

${\displaystyle f(x)=1}$ if ${\displaystyle x\in S}$

${\displaystyle f(x)=0}$ if ${\displaystyle x\notin S}$.

In other words, the set ${\displaystyle S}$ is computable if and only if the indicator function ${\displaystyle \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. ^{[note 1]}
• The subset of prime numbers is computable.
• The set of Gödel numbers is computable. ^{[note 2]}

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. ^[1]
• 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 ${\displaystyle \Delta _{1}^{0}}$ 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

1. That is, under the Set-theoretic definition of natural numbers, the set of natural numbers less than a given natural number is computable.
2. c.f. Gödel's incompleteness theorems; "On formally undecidable propositions of Principia Mathematica and related systems I" by Kurt Gödel.

References

1. Markov, A. (1958). "The insolubility of the problem of homeomorphy". Doklady Akademii Nauk SSSR. 121: 218–220. MR   0097793.

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

• Sakharov, Alex. "Recursive Set". MathWorld .