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:
“No man, not even a doctor, ever gives any other definition of what a nurse should be than this—”devoted and obedient.” This definition would do just as well for a porter. It might even do for a horse. It would not do for a policeman.”
—Florence Nightingale (1820–1910)