Prove existence of non-computable double argument function

Question

Recently we've been dealing with computable and non-computable functions, trying to construct different interesting models within the theory. Yesterday, thoughts on one of tasks we've considered during classes lead me to the following question: whether is it possible for non-computable function $F: \mathbb{N}^2 \longrightarrow \mathbb{N}$ to exist, if all this functions projections are computable:

$\forall a \in \mathbb{N}: f(a,x) - \\$ is computable function $\forall x \in \mathbb{N}$

and

$\forall a \in \mathbb{N}: f(x,a) - \\$ is computable function $\forall x \in \mathbb{N}$;

($F$ is not necessary defined for all values from $\mathbb{N}$ - it may be partially defined).

Do you have any ideas?

Answer 1

Sure. Let the function's range be $\{0,1\}$, such that for each $x\in\mathbb{N}$, $f(x,y)=1$ for exactly one value of $y$; call it $y(x)$, and assume it is strictly increasing with $x$. (In either words, $f$ is the graph of an increasing function.) Clearly $f(x,y)$ is computable for each fixed $x$ (it's all zeroes and a single $1$, the location of which can be specified in a finite number of bits), and $f(x,y)$ is also computable for each fixed $y$ (it's either all zeroes or again all zeroes and a single $1$). But $f(x,y)$ as a function on $\mathbb{N}^2$ is only computable if $y(x)$ is computable. And certainly we can choose $y(x)$ to be a strictly increasing non-computable function (exercise for the reader).

Answer 2

There are already some answers given, so I don't know whether this answer adds anything substantially different. So you are talking about a two argument function $F: \mathbb{N}^2 \rightarrow \mathbb{N}$ such that each "row" and "column" of this function are individually computable, but the function $F$ itself is non-computable?

Can we define $F$ as follows? For each $n \in \mathbb{N}$ we have $F(a,b)=BB(n)$ iff one of the two following possibilities is true:

$(1)$ $a=n$ and $b \geq n$

$(2)$ $b=n$ and $a \geq n$.

Edit: On a second thought, why not just have the value of $F$ as $0$ for all non-diagonal entries and $F(n,n)=BB(n)$ for all $n\in \mathbb{N}$. This is probably simpler than above.

Answer 3

Let $\{ T_n \}$ be an enumeration of all Turing machines. Define $f(x,y)$ to be $1$ if $T_{\min(x,y)}$ halts (on an empty input string), $0$ otherwise.