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:
“In the beautiful, man sets himself up as the standard of perfection; in select cases he worships himself in it.... Man believes that the world itself is filled with beauty—he forgets that it is he who has created it. He alone has bestowed beauty upon the world—alas! only a very human, an all too human, beauty.”
—Friedrich Nietzsche (1844–1900)
“It is commonplace that a problem stated is well on its way to solution, for statement of the nature of a problem signifies that the underlying quality is being transformed into determinate distinctions of terms and relations or has become an object of articulate thought.”
—John Dewey (1859–1952)