Let $U$ bet a Godel universal function and consider the set $R=\{p\in N: U(p,0)\downarrow, \ U(p,1)\uparrow\}$. Prove that $R$ is not c.e. (computably enumerable) and not co-c.e (co-computably enumerable).
Is the following sketch of proof correct?
It's enough to show that $K=\{p\in N: U(p,p)\downarrow\}$ can be $m$-reduced to $R$ and $\overline R$ (overline = complement).
- $K\leq_m R$:
Define the partial function $V:N\times N\to N$ as follows:
- if $n\in K$, then $V(n,x)=\frac{x}{x-1}$;
- if $n\notin K$, then $V(n,x)$ is undefined for all $x$.
This is a computable partial function. Thus there's a total computable $s:N\to N$ such that $V(n,x)=U(s(n),x)$ for all $n,x$. This $s$ $m$-reduces $K$ to $R$.
- $K\leq_m \overline R$
Define the partial function $V:N\times N\to N$ as follows:
- if $n\in K$, then $V(n,x)=\frac{1}{x}$ (or alternatively $V(n,x)=1$ for all $x$);
- if $n\notin K$, then $V(n,x)$ is undefined for all $x$.
This is a computable partial function. Thus there's a total computable $s:N\to N$ such that $V(n,x)=U(s(n),x)$ for all $n,x$. This $s$ $m$-reduces $K$ to $\overline R$.