In
computability theory
Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since ex ...
, a
set of
natural number
In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...
s is computable (or decidable or recursive) if there is an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
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
of the
natural number
In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...
s is computable if there exists a
total computable function such that:
:
if
:
if
.
In other words, the set
is computable
if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either bo ...
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 , then the indicator functio ...
is
computable.
Examples
*Every
recursive language is a computable.
*Every finite or
cofinite subset of the natural numbers is computable.
**The
empty set
In mathematics, the empty set or void set is the unique Set (mathematics), set having no Element (mathematics), elements; its size or cardinality (count of elements in a set) is 0, zero. Some axiomatic set theories ensure that the empty set exi ...
is computable.
**The entire set of natural numbers is computable.
**Every 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 (mathematics), 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 ...
s 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
In mathematics and more specifically in topology, a homeomorphism ( from Greek roots meaning "similar shape", named by Henri Poincaré), also called topological isomorphism, or bicontinuous function, is a bijective and continuous function betw ...
finite
simplicial complex
In mathematics, a simplicial complex is a structured Set (mathematics), set composed of Point (geometry), points, line segments, triangles, and their ''n''-dimensional counterparts, called Simplex, simplices, such that all the faces and intersec ...
es 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
In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either bo ...
''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
In mathematics, a bijection, bijective function, or one-to-one correspondence is a function between two sets such that each element of the second set (the codomain) is the image of exactly one element of the first set (the domain). Equival ...
is computable.
''A'' is computable if and only if it is at level
of the
arithmetical hierarchy
In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene–Mostowski hierarchy (after mathematicians Stephen Cole Kleene and Andrzej Mostowski) classifies certain sets based on the complexity of formulas that define th ...
.
''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
Recursion occurs when the definition of a concept or process depends on a simpler or previous version of itself. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in m ...
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
*
{{Set theory
Computability theory
Theory of computation