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:
“We are amphibious creatures, weaponed for two elements, having two sets of faculties, the particular and the catholic.”
—Ralph Waldo Emerson (1803–1882)
“Happy will that house be in which the relations are formed from character; after the highest, and not after the lowest order; the house in which character marries, and not confusion and a miscellany of unavowable motives.”
—Ralph Waldo Emerson (1803–1882)