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)

    “It is hardly to be believed how spiritual reflections when mixed with a little physics can hold people’s attention and give them a livelier idea of God than do the often ill-applied examples of his wrath.”
    —G.C. (Georg Christoph)

    “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)