2.8 PRODUCTIVE AND CREATIVE SETS
Some non r.e. sets S are, in a way of speaking, “effectively non r.e.” in that we have an algorithmic way to refute their r.e.-ness in the context of any claim of the form “Wx = S”. That is, we can construct a counterexample m ∈ S – Wx. Such sets were called productive by Dekker.
2.8.0.15 Definition. A set S is productive with a productive function f ∈ 
if, for all x, whenever we have Wx ⊆ S then f(x) ∈ S – Wx. 
Clearly, every productive set S is not c.e. for if we think otherwise, then S = Wm for some m. But then f(m) ∈ S – Wm—where f is a given productive function for S—and this yields a contradiction.
2.8.0.16 Example. 
is productive with productive function 
x.x. Indeed, let Wx ⊆ . Note that this entails that x ∈ Wx is false, for it says x(x) ↓, that ...
Get Theory of Computation now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
