What non-standard model of arithmetic does Hofstadter reference in GEB?

Question

Following some of the coolest bits of Hofstadter's Gödel, Escher, Bach, extensions of the standard model of arithmetic are described. A ways in, the paragraph "Supernatural Addition and Multiplication" mentions:

... It turns out that you can "index" the supernaturals in a simple and natural way by assocating with each supernatural number a trio of ordinary integers... [e.g. (9,-8,3)] ... Under some indexing schemes, it is very easy to calculate the index triplet for the sum of two supernaturals, given the indices of the two numbers to be added. Under other indexing schemes, it is very easy to calculate the index triplet for the product of two supernaturals, given the indices of the two numbers to be multiplied. But under no indexing scheme is it possible to calculate both.

-- Douglas Hofstadter; Gödel, Escher, Bach; Chapter XIV

The description is mystifying me and also seems to have mystified at least one Wikipedia talk page, where you can also find a fuller quote.

Having done some basic digging on this, I'm confused.

• It looks like what's being discussed is a countable non-standard model of arithmetic. However, the "index triplet" isn't something I can find reference to anywhere. Is there a plausible candidate for such a "simple and natural" indexing?
• The theorem referenced sounds a lot like Tennenbaum's theorem, but that theorem says more strongly that neither addition nor multiplication is computable (cf discussion here). Is there some other candidate for what theorem is being referred to here?

An old Math Forum post has some hints, but I don't have access to the linked articles at the moment.

Answer 1

My first guess is that the triples come from the fact that nonstandard countable models of PA look like $$\mathbb N + \mathbb Z\times\mathbb Q$$ and elements of $\mathbb Q$ can be represented by pairs.

As for the separate computability of $+$ (addition) and $\cdot$ (multiplication), I am speculating but perhaps the idea is something like this:

Let the theories $T_1$ and $T_2$ be obtained from $\mathrm{Th}(\mathbb N,+)$ and $\mathrm{Th}(\mathbb N,\cdot)$, respectively, by adding axioms saying that a new constant symbol $c$ is "infinite". Then $T_1$ and $T_2$ each have computable models. [Computable model just means that the operations $+$ and $\cdot$ are computable functions.]

For $T_1$ you could add axioms $\varphi_n$ expressing $c\ge n$ as $$\exists x(\underbrace{1+\dots+1}_{n}+x=c)$$

For $T_2$, you could say that there are at least $n$ primes that divide $x$. But in $T_2$ you do not get a linear ordering, so I don't know whether using triples is sensible for models of $T_2$.