Recursive Set - Examples

Examples

  • Every finite or cofinite subset of the natural numbers is computable. This includes these special cases:
    • The empty set is computable.
    • The entire set of natural numbers is computable.
    • Each natural number (as defined in standard set theory) is computable; that is, the set of natural numbers less than a given natural number is computable.
  • The set of prime numbers is computable.
  • A recursive language is a recursive subset of a formal language.
  • The set of Gödel numbers of arithmetic proofs described in Kurt Gödel's paper "On formally undecidable propositions of Principia Mathematica and related systems I"; see Gödel's incompleteness theorems.

Read more about this topic:  Recursive Set

Famous quotes containing the word examples:

    “No rules exist, and examples are simply life-savers answering the appeals of rules making vain attempts to exist.”
    —André Breton (1896–1966)

    “Histories are more full of examples of the fidelity of dogs than of friends.”
    —Alexander Pope (1688–1744)

    “In the examples that I here bring in of what I have [read], heard, done or said, I have refrained from daring to alter even the smallest and most indifferent circumstances. My conscience falsifies not an iota; for my knowledge I cannot answer.”
    —Michel de Montaigne (1533–1592)