Tennenbaum's theorem generalizations: can we have a computable Collatz map on a nonstandard model of Peano? Tennenbaum's theorem states that for any (countable) nonstandard model of Peano arithmetic, neither the addition nor the multiplications is computable. I find this result fascinating (and frustrating!), but suppose I have less ambitious goals: I merely want to able to compute Collatz iterations! In particular, I want to be compute whether a (nonstandard) integer $n$ is even or odd, and if it's odd, compute $3n+1$, and if even, compute $n/2$.
More generally, I'm curious about any extensions of Tennenbaum's theorem to ruling out the computability of things weaker than addition or multiplication, and also in results on what can be computed (some things can for boring reasons, like the doubling map, for instance: but I'd be curious in anything that is rich enough to still produce an interesting nonstandard structure one could explore with a computer program), although I feel the Collatz map is a particularly fun example to consider.
 A: I suspect this is out of reach of current techniques.
Contra an old (and now deleted) comment of mine, there are simply-definable unary functions which are never nonstandardly computably presentable. More precisely, there is a (highly-non-unique) formula $\varphi(x,y)$ in the language of arithmetic with the following properties:

*

*$\varphi$ is $\Delta_0$.


*$\mathsf{PA}\vdash\forall x\exists!y\varphi(x,y)$ - or more colloquially, $\mathsf{PA}$ proves that $\varphi$ defines a unary function (like the Collatz function!).


*There are $c,d$ such that the r.e. sets $W_c$ and $W_d$ are disjoint and recursively inseparable, and for each $n$ there is an $2n$-cycle in the graph defined by $\varphi$ iff $n\in W_c$ and there is a $2n+1$-cycle in the graph defined by $\varphi$ iff $n\in W_d$; and moreover all of the foregoing is also provable in $\mathsf{PA}$.
Now any nonstandard $(\mathbb{N};\boxplus,\boxtimes)\models\mathsf{PA}$ whose $\varphi$-function is recursive would yield a recursive separator for $W_c$ and $W_d$, so no such model can exist. Thus we have an example of a definable unary function which is never computable in any nonstandard model of arithmetic with domain $\mathbb{N}$. Moreover, $\varphi$ is about as simple - from a recursion-theoretic point of view - as one could hope. So there is no "coarse" reason why the same situation couldn't hold for the Collatz function.
