TheInfoList

OR:

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 $S$ of the natural numbers is called computable if there exists a total
computable function Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can d ...
$f$ such that $f\left(x\right)=1$ if $x\in S$ and $f\left(x\right)=0$ if $x\notin S$. In other words, the set $S$ is computable if and only if the
indicator function In mathematics, an indicator function or a characteristic function of a subset of a set is a function that maps elements of the subset to one, and all other elements to zero. That is, if is a subset of some set , one has \mathbf_(x)=1 if x\i ...
$\mathbb_$ is
computable Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is close ...
.

# Examples and non-examples

Examples: *Every finite or cofinite subset of the natural numbers is computable. This includes these special cases: **The
empty set In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in othe ...
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 number A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s 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 Gödel's incompleteness theorems are two theorems of mathematical logic that are concerned with the limits of in formal axiomatic theories. These results, published by Kurt Gödel in 1931, are important both in mathematical logic and in the philo ...
. Non-examples: *The set of Turing machines that halt is not computable. *The isomorphism class of two finite simplicial complexes is not computable. *The set of busy beaver champions is not computable. * Hilbert's tenth problem is not computable.

# Properties

If ''A'' is a computable set then the complement of ''A'' is a computable set. If ''A'' and ''B'' are computable sets then ''A'' ∩ ''B'', ''A'' ∪ ''B'' and the image of ''A'' × ''B'' under the Cantor pairing function are computable sets. ''A'' is a computable set if and only if ''A'' and the complement of ''A'' are both computably enumerable (c.e.). The
preimage In mathematics, the image of a function is the set of all output values it may produce. More generally, evaluating a given function f at each element of a given subset A of its domain produces a set, called the "image of A under (or through ...
of a computable set under a total
computable function Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can d ...
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 $\Delta^0_1$ 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.

*
Recursively enumerable language In mathematics, logic and computer science, a formal language is called recursively enumerable (also recognizable, partially decidable, semidecidable, Turing-acceptable or Turing-recognizable) if it is a recursively enumerable subset in the set o ...
* Recursive language *
Recursion Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...

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