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:
“Certain anthropologists hold that man, having discovered tools, ceased to evolve biologically. Animals, never having discovered them, continue to fashion drills out of their beaks, oars out of their hind feet, wings out of their forefeet, suits of armor out of their hides, levers out of their horns, saws out of their teeth. Whether this be true or not, all authorities agree that man is the tool-using animal. It sets him off from the rest of the animal kingdom as drastically as does speech.”
—Stuart Chase (1888–1985)
“I have no wealthy or popular relations to recommend me.”
—Abraham Lincoln (1809–1865)