Computable set

Source: Wikipedia, the free encyclopedia.

In computability theory, a set of natural numbers is called computable, recursive, or decidable if there is an algorithm which takes a number as input, terminates after a finite amount of time (possibly depending on the given number) and correctly decides whether the number belongs to the set or not.

A set which is not computable is called noncomputable or undecidable.

A more general class of sets than the computable ones consists of the

computably enumerable (c.e.) sets
, also called semidecidable sets. For these sets, it is only required that there is an algorithm that correctly decides when a number is in the set; the algorithm may give no answer (but not the wrong answer) for numbers not in the set.

Formal definition

A subset of the

such that if and if . In other words, the set is computable if and only if the indicator function is computable.

Examples and non-examples

Examples:

  • Every finite or
    cofinite
    subset of the natural numbers is computable. This includes these special cases:
    • The empty set is computable.
    • The entire set of natural numbers is computable.
    • Each natural number (as defined in standard set theory) is computable; that is, the set of natural numbers less than a given natural number is computable.
  • The subset of prime numbers is computable.
  • A recursive language is a computable subset of a formal language.
  • The set of Gödel numbers of arithmetic proofs described in Kurt Gödel's paper "On formally undecidable propositions of Principia Mathematica and related systems I" is computable; see Gödel's incompleteness theorems.

Non-examples:

Properties

If A is a computable set then the

Cantor pairing function
are computable sets.

A is a computable set

total computable function is a computable set. The image of a computable set under a total computable bijection
is computable. (In general, the image of a computable set under a computable function is c.e., but possibly not computable).

A is a computable set if and only if it is at level of the arithmetical hierarchy.

A is a computable set if and only if it is either the range of a nondecreasing total computable function, or the empty set. The image of a computable set under a nondecreasing total computable function is computable.

See also

References

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