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.

Uses your system voice; voice and rate in settings.

≈ 5 min read

Cite, export and learn8 citation formats · 8 exports · lesson and quiz

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.

  • 3 Properties
  • 4 See also
  • 5 Notes
  • 6 References
  • 7 Bibliography
  • 8 External links
  • Definition

    edit edit source

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

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

    In other words, the set S is computable if and only if the indicator function 𝟙S is computable.

    Examples

    edit edit source
    • 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.[note 1]
    • The subset of prime numbers is computable.
    • The set of Gödel numbers is computable.[note 2]

    Non-examples

    edit edit source

    Properties

    edit edit source

    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 Δ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

    edit edit source

    Notes

    edit edit source
    1. ^ That is, under the Set-theoretic definition of natural numbers, the set of natural numbers less than a given natural number is computable. Wikipedia revision 1370344919, retrieved 2026-11-20
    2. ^ c.f. Gödel's incompleteness theorems; "On formally undecidable propositions of Principia Mathematica and related systems I" by Kurt Gödel. Wikipedia revision 1370344919, retrieved 2026-11-20

    References

    edit edit source
    1. ^ Markov, A. (1958). "The insolubility of the problem of homeomorphy". Doklady Akademii Nauk SSSR. 121: 218–220. MR 0097793. Wikipedia revision 1370344919, retrieved 2026-11-20

    Bibliography

    edit edit source edit edit source Mathematical logicGeneral Theorems
    (list),
    paradoxes Logics Set theory Formal
    systems

    (list),
    language,
    syntax Proof theory Model theory Computability
    theory
    Related Mathematics portal Set theoryOverview Axioms Operations
    • Concepts
    • Methods
    Set types Theories Set theorists

    Text derived from https://en.wikipedia.org/w/index.php?oldid=1370344919 under CC BY-SA 4.0; modifications have been made.

    Words in each sectionPropertiesPropertiesProperties: 153 words153ExamplesExamplesExamples: 104 words104NotesNotesNotes: 56 words56BibliographyBibliographyBibliography: 53 words53DefinitionDefinitionDefinition: 52 words52See alsoSee alsoSee also: 13 words13
    Words in each section. Measured from the stored article body; sections below the minimum are not plotted.

    Provenance

    snapshot enwiki-001370344919 · captured 2026-08-20 · ledger · version history

    Cite this page as: encyclopegia.org, “Computable set”, snapshot enwiki-001370344919. https://encyclopegia.org/a/computable-set