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 <math>S</math> of the natural numbers is computable if there exists a 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.

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

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.