TOPICS
Search

Productive Set


A set A of integers is productive if there exists a partial recursive function f such that, for any x, the following holds: If the domain of phi_x is a subset of A, then f(x) is convergent, f(x) belongs to A, and f(x) does not belong to the domain of phi_x, where phi_x denotes a recursive function whose Gödel number is x.

Productive sets are not recursively enumerable.


See also

Creative Set, Gödel's First Incompleteness Theorem, Gödel Number, Gödel's Second Incompleteness Theorem, Recursive Function

This entry contributed by Alex Sakharov (author's link)

Explore with Wolfram|Alpha

References

Davis, M. Computability and Unsolvability. New York: Dover, 1982.Kleene, S. C. Mathematical Logic. New York: Dover, 2002.Rogers, H. Theory of Recursive Functions and Effective Computability. Cambridge, MA: MIT Press, 1987.

Referenced on Wolfram|Alpha

Productive Set

Cite this as:

Sakharov, Alex. "Productive Set." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein. https://mathworld.wolfram.com/ProductiveSet.html

Subject classifications