Reference articles on history, science, culture and more
Surprise meSurprise meSubscribe
Encyclopedia

Computable set

Set with algorithmic membership test

Wikipedia contributorsAdapted for Fathomly · View authors
1 min read
Source updated August 20, 2026

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.

01Definition

A subset S of the natural numbers is computable if there exists a total computable function f such that:

f(x)=1 if x\in S
f(x)=0 if x\notin S.

In other words, the set S is computable if and only if the indicator function \mathbb {1} _{S} is computable.

02Examples

  • Every recursive language is computable.
  • Every finite or cofinite subset of the natural numbers is computable.
    • The empty set is computable.
    • The entire set of natural numbers is computable.
    • Every natural number is computable.
  • The subset of prime numbers is computable.
  • The set of Gödel numbers is computable.

Non-examples

03Properties

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:

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 \Delta _{1}^{0} 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.

Watch videos about Computable setExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Computable set”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Continue exploring

Related topics

Computably enumerable set

In computability theory, a set S of natural numbers is called computably enumerable, recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if: There is an algorithm such that the set of input numbers for which the algorithm halts is exactly S. Or, equivalently, There is an algorithm that enumerates the members of S. That means that its output is a list of all the members of S: s1, s2, s3, ... . If S is infinite, this algorithm will run forever, but each element of S will be returned after a finite amount of time.

Decidability (logic)

In logic, a true/false decision problem is decidable if there exists an effective method for deriving the correct answer. Logical systems are decidable if membership in their set of logically valid formulas can be effectively determined.

Recursively enumerable language

In mathematics, logic and computer science, a formal language is called recursively enumerable if it is a recursively enumerable subset in the set of all possible words over the alphabet of the language, i.e., if there exists a Turing machine which will enumerate all valid strings of the language. These are generated by unrestricted grammars.