Creative and Productive Sets - Definition and Example

Definition and Example

For the remainder of this article, assume that is an acceptable numbering of the computable functions and W_i 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 .