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:
“Mothers often are too easily intimidated by their children’s negative reactions...When the child cries or is unhappy, the mother reads this as meaning that she is a failure. This is why it is so important for a mother to know...that the process of growing up involves by definition things that her child is not going to like. Her job is not to create a bed of roses, but to help him learn how to pick his way through the thorns.”
—Elaine Heffner (20th century)