O'Reilly logo

Theory of Computation by George Tourlakis

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 mSWx. Such sets were called productive by Dekker.

2.8.0.15 Definition. A set S is productive with a productive function fimages if, for all x, whenever we have WxS then f(x) ∈ SWx. images

2.8.0.16 Example. images is productive with productive function images x.x. Indeed, let Wximages. Note that this entails that xWx is false, for it says x(x) ↓, that ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required