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

of the natural numbers is computable if there exists a total computable function such that:

1. .

is computable if and only if the indicator function 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 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

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.

External links