By Tennenbaum's theorem, in the usual sense of computability for models,

neither addition nor multiplication can be computable in a non-standard model of PA.

Weak version:

Can addition or multiplication become computable if non-equality

only needs to be computably enumerable, rather than computable?

In other words, can there be a countable structure on which [either addition is computable or multiplication is computable] and some quotient of that structure is a non-standard model of PA?

If I understand the proof of the addition version of Tennenbaum's theorem correctly, then for addition to be computable there would need to be a representative r_{0} of a non-standard number such that {r : r represents the same element as r_{0}} is not computably enumerable.

**I'm mainly after an answer to either version, rather than both,**

so the following will be quite strong.

Super-Strong version:

Are there

a computable function d : {0,1,2,3,...}^{2}$\to \mathbb{Q}$

and

binary operations +_{M}and *_{M}on {0,1,2,3,...} (by Tennenbaum, they can't be computable)

such that

composing d with the inclusion from $\mathbb{Q}$ to the real numbers gives a metric

and

the induced metric space is complete

and

there is an algorithm that approximates +_{M}and *_{M}to arbitrary accuracy

and

+_{M}and *_{M}make {0,1,2,3,...} intothe non-standard partof a model of PA

?

The standard part could just be put in with distance 1 from everything, so requiring it

to be a non-standard part is stronger than requiring it be a full non-standard model.

Furthermore, for any function and operations witnessing the truth of the Super-Strong version,

[the set of well formed expression using $\hspace{.02 in}0,\hspace{-0.04 in}1,\hspace{-0.04 in}+,\hspace{-0.04 in}*,\hspace{-0.04 in}(\hspace{.02 in},\hspace{-0.03 in})\hspace{.02 in}$ and elements of the metric space]

is a non-standard model in the sense of the weak version,

which *both* operations are computable in.

meantfor the "Super-Strong" version to obviously be stronger than the weak version. $\:$ It is in fact stronger, since one can use the free term algebra on the metric space (so that inequality will be c.e.), but that's certainly not obvious. $\:$ Based on the idea of the free term algebra over the metric space, I'm about to simplify the statement of the Super-Strong version in a way that I believe gives something equivalent to what was there when you commented. $\;\;\;\;\;\;\;\;$ $\endgroup$ – user5810 Oct 14 '15 at 13:30