Computable set
Appearance
(Redirected from Recursive 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. Formally, a subset of the natural numbers is computable if there exists a total computable function such that
Examples
[edit]- Every recursive language is computable.
- Every finite or cofinite subset of the natural numbers is computable.
- The subset of prime numbers is computable.
- The set of Gödel numbers is computable.
Non-computable sets
[edit]- 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
[edit]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 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
[edit]Notes
[edit]- ↑ That is, under the set-theoretic definition of natural numbers, the set of natural numbers less than a given natural number is computable.
References
[edit]- ↑ Markov, A. (1958). "The insolubility of the problem of homeomorphy". Doklady Akademii Nauk SSSR. 121: 218–220. MR 0097793.
- Cutland, Nigel (1980). Computability: An Introduction to Recursive Function Theory. Cambridge University Press. ISBN 0-521-22384-9.
- Rogers, Hartley, Jr (1967). Theory of Recursive Functions and Effective Computability (1987 reprint ed.). Cambridge, MA: MIT Press. ISBN 0-262-68052-1.
{{cite book}}: CS1 maint: multiple names: authors list (link)
- Soare, Robert I. (1987). Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic. Berlin, Heidelberg: Springer. ISBN 3-540-15299-7.
External links
[edit]- Sakharov, Alex. "Recursive set". MathWorld.
