Productive set?

55 Views Asked by At

My teacher said that the following set $E=\{x: range(\phi_x) \not= \{x\} \}$ ($\phi_x$ is the $x$-th Turning Machine) is productive. Why? I think it should be recursive enumerable. In fact, to decide wether $x$ belongs to $E$, you can simulate the $x$-th Turing Machine with dovetail method and, if $x$ in $E$, the machine will terminate for sure, returning some value different from $x$ (for a certain input y). If $x$ is not in $E$, the Machine will never terminate.

1

There are 1 best solutions below

1
On

Remember that there are two ways to have $x\in E$: we could have $ran(\phi_x)$ contain something other than $x$, or we could have $ran(\phi_x)$ fail to contain $x$ (or both for that matter). The first failure mode is indeed c.e., but the second isn't.

By contrast, the set $$\{x: ran(\phi_x)\not\subseteq\{x\}\}$$ is indeed c.e. by the argument you give.