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:
“Histories are more full of examples of the fidelity of dogs than of friends.”
—Alexander Pope (1688–1744)
“No rules exist, and examples are simply life-savers answering the appeals of rules making vain attempts to exist.”
—André Breton (1896–1966)
“There are many examples of women that have excelled in learning, and even in war, but this is no reason we should bring ‘em all up to Latin and Greek or else military discipline, instead of needle-work and housewifry.”
—Bernard Mandeville (1670–1733)