Prove that there are exists uncomputable partial function $U(n,x)$ such that $ \forall n \in N: U(n,x)$ and $U(x,n)$ are computable.

Question

Prove that there are exists uncomputable partial function $U(n,x)$ such that $ \forall n \in N: U(n,x)$ and $U(x,n)$ are computable.

It's new material for me and i don't have any ideas how to solve tasks like this..

Answer 1

The intuitive idea is this: take a non-computable function and "spread it out" across $\mathbb{N}^2$ so that the horizontal and vertical slices each encode only finitely much non-trivial information, and hence are computable.

Here's one solution: Let $H\subseteq \mathbb{N}$ be a non-computable set. Define $$U(x,y) = \begin{cases} 1 & \text{if $x=y$ and $x\in H$}\\ 0 & \text{otherwise}.\end{cases}$$

Now $U$ is not computable. Indeed, if it were computable, then the function $x\mapsto U(x,x)$ would be computable, but this is the characteristic function of $H$.

On the other hand, for any fixed $n$, the functions $x\mapsto U(n,x)$ and $x\mapsto U(x,n)$ are computable. Indeed, if $n\in H$, we have $$U(n,x) = U(x,n) = \begin{cases} 1 & \text{if $x=n$}\\ 0 & \text{otherwise}\end{cases}$$ which is computable: it is the characteristic function of the set $\{n\}$. And if $n\notin H$, then $U(n,x) = U(x,n) = 0$ for all $x$.