Definition and Example
For the remainder of this article, assume that is an acceptable numbering of the computable functions and Wi the corresponding numbering of the recursively enumerable sets.
A set A of natural numbers is called productive if there exists a partial computable function so that for all, if then The function is called the productive function for
A set A of natural numbers is called creative if A is recursively enumerable and its complement is productive. Not every productive set has a recursively enumerable complement, however, as illustrated below.
The archetypal creative set is, the set representing the halting problem. Its complement is productive with productive function f(i) = i. To see this, assume . If i were in then and thus . This would mean, so we can conclude, which means .
Read more about this topic: Creative And Productive Sets
Famous quotes containing the word definition:
“The definition of good prose is proper words in their proper places; of good verse, the most proper words in their proper places. The propriety is in either case relative. The words in prose ought to express the intended meaning, and no more; if they attract attention to themselves, it is, in general, a fault.”
—Samuel Taylor Coleridge (1772–1834)