Set theory computer science

99 Views Asked by At

I am studying "recursion theory" and i can't understand how to study these three sets (if they are productive or creative, or even r.e.).

The three sets are the follow: $$Z= \{ x | \phi_x(1)\uparrow \wedge \phi_x(0)\downarrow \}$$

$$W= \{ x \vert (∀z > x)(\phi_x(z) = z) \}$$

$$T= \{ \langle x,y\rangle \vert E_x=W_y \}$$

I can't find a way to reduce to $K$ or $!K$, where

$$K = \{ x | \phi_x(x)\downarrow \}.$$


The notation above has the following meaning:

$\phi_x(y)$ = Turing Machine with index $x$ on input $y$

$\downarrow$ = machine halt

$\uparrow$ = machine loop (never halt)

$W_x$ = the r.e. set associated to a $\phi_x$ , so $W_x = dom(\phi_x)$

$E_x$ = the range of to $\phi_x$

$!K$ = the complement of $K$.

Thanks for your attention.