Creative and productive sets

Creative and productive sets are classes of subsets of the natural numbers that occur in computability theory and mathematical logic. They are closely connected with the concept of recursive enumerable (RE ): The production quantities are in a sense still best algorithmically manageable amounts that are not recursively enumerable more. In contrast, the creative sets are exactly the RE- complete (see completeness (theoretical computer science ) ). The term creative lot goes back to a paper by Emil Post in 1944, later was added a unique name for the productive quantities.

Definition

It was an effective enumeration of all recursively enumerable sets.

A set of natural numbers hot -productive, if there is a partial computable function, satisfies the following property:

So whenever a recursively enumerable set is entirely in, is its index to an element of mapped, that is no longer part of this set. In particular, is defined at this point.

In this case, a productive function is called for.

A lot of hot now creative, even if it is recursively enumerable and its complement productive.

Examples

• The special halting problem is the prototype of a creative lot, its complement is productive with the identity as a productive function.
• The class of all valid arithmetic formulas - conceived by a suitable Gödelization as a set of natural numbers - is productive, it means the first Gödel's incompleteness theorem.
• The set of indices of all total computable functions is also productive.

Properties

• The productive function can always choose total and injective.
• Productive quantities are not recursively enumerable, for any amount of recursively enumerable testified yes, that is true.
• However, every productive set has an infinite recursively enumerable subset. In particular, therefore productive quantities are always infinite.

• A lot is therefore exactly creative when it is RE -complete.

• Is productive, as well.
• Is creative, clearly creative when is productive.