$f(x,y) = P(x) + Q(y)$, for non-constant polynomials $P$ and $Q$, is not computable.

If $P$ and $Q$ both have degree 1, then $f(x,y) = ax + by + c$, so $f(f(0,x),f(y,0)) = a(bx+c) + b(ay+c) + c = a(bx + by + c) + bc + c$, so we can compute $bx + by + c = a0 + b(x+y) + c$, so we can compute $x + y$. So we can assume $Q$ has degree $> 1$.

The basic idea is that we want to use repeated applications of $f$ to encode a list of numbers: $f(i_1, f(i_2, f(i_3, ...)))$.

The first problem with this is that we can't compute what the standard natural numbers are. But we can compute a copy of $\mathbb{N}$ that is also definable. $Q$ is eventually larger than all of its values (because it has degree > 1), so pick some $k$ after this happens (and also after $P$ becomes injective, because that will be important later), and define $g(0) = k$, $g(n+1) = f(0,g(n))$. Now $g$ is increasing, and computable, and also exists in the model.

The second problem is that $f$ might not be injective. But because $P$ and $Q$ are eventually increasing, and $Q$ has degree > 1, it is eventually kind of injective: for any upper bound $K$ on the values of $x$, there is some $N$ such that, if $f(x,y) = f(z,w)$, and $y,w > N$ and $x,z < K$, and $x$ and $z$ are both after the point when $P$ becomes injective, then $x = z$ and $y = w$. We just choose $N$ large enough that the difference between two adjacent values of $Q$ is larger than any possible difference of two values of $P$ below $K$; then we get $y = w$, so $P(x) = P(z)$, and the condition that they're both after $P$ becomes injective means $x = z$.

When I first wrote out this answer, I thought that property was enough. Just put $N+1$ at the end of the list, everything is injective, and it all works, right?

The third problem is that we can't check if a number is $> N$ or not. Fortunately this isn't actually that hard to solve: we can just pick $N$ to also be bigger than any value of $Q$ before it becomes increasing. Now if we find a pair of values that produces the right output, as long as $x < K$, we know we found it; $y < N$ just wouldn't be big enough.

Pick $K$ to be larger than $g(n)$ for all standard $n$, and encode a set $A$ as the number $f(g(i_1), f(g(i_2), f(g(i_3), ...)))$, with $N+1$ at the end to make sure all of it is $> N$. Now given an input $i$, we can just search the list of elements of $A$, and the list of non-elements of $A$, to determine if $i \in A$.

$f(x,y) = x^ny^m$ is not computable, because $f(f(1,x),f(y,1)) = (xy)^{nm}$, and then we can compute $xy$. $f(x,y) = xy^n + c$ is also not computable, because $f(x,y) = (xy^n)1^n + c$ so we can compute $xy^n$. $f(x,y) = x^ny^n + c$ is also not computable, because $f(x,y) = (xy)^n1^n + c$ so we can compute $xy$. So I guess the next question in this family is whether $x^2y^3 + c$ can be computable.

$kx^2y^3 + c$ is not computable. Suppose we know what $n^2$ is, then we can compute $kn^6 + c$, then $n^3$, then $kn^{12} + c$, then $n^4$, then $kn^{14} + c$, then $n$. So for numbers $x$ and $y$, we can compute $y^2$, and then $kx^2(y^2)^3 + c$, and then $xy^3$. I suspect this argument generalises somehow, but I don't know how.

inthe model, since PA proves that addition and multiplication are computable functions. What Tennenbaum's theorem says instead is that the model has no presentation (on domain $\mathbb{N}$) for which either of these functions is computableoutsidethe model. $\endgroup$