Computable Sets and Relations
A set A of natural numbers is called computable (synonyms: recursive, decidable) if there is a computable, total function f such that for any natural number n, f(n) = 1 if n is in A and f(n) = 0 if n is not in A.
A set of natural numbers is called computably enumerable (synonyms: recursively enumerable, semidecidable) if there is a computable function f such that for each number n, f(n) is defined if and only if n is in the set. Thus a set is computably enumerable if and only if it is the domain of some computable function. The word enumerable is used because the following are equivalent for a nonempty subset B of the natural numbers:
- B is the domain of a computable function.
- B is the range of a total computable function. If B is infinite then the function can be assumed to be injective.
If a set B is the range of a function f then the function can be viewed as an enumeration of B, because the list f(0), f(1), ... will include every element of B.
Because each finitary relation on the natural numbers can be identified with a corresponding set of finite sequences of natural numbers, the notions of computable relation and computably enumerable relation can be defined from their analogues for sets.
Read more about this topic: Computable Function
Famous quotes containing the words sets and/or relations:
“Until, accustomed to disappointments, you can let yourself rule and be ruled by these strings or emanations that connect everything together, you haven’t fully exorcised the demon of doubt that sets you in motion like a rocking horse that cannot stop rocking.”
—John Ashbery (b. 1927)
“Subject the material world to the higher ends by understanding it in all its relations to daily life and action.”
—Ellen Henrietta Swallow Richards (1842–1911)