Computable set

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. Formally, a subset S of the natural numbers is computable if there exists a total computable function f such that

f(x)={1if x∈S,0if x∉S.

Examples

Non-computable sets

Properties

Both A, B are sets in this section.

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 it is at level Δ10 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