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.
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.
of the natural numbers is called computable if there exists a total computable function
Examples: Non-examples: 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 it is at level
A is a computable set if and only if it is either the range of a nondecreasing total computable function, or the empty set.