Let us define a countable model $\cal{M}$ = $(M,+_M ,\cdot_M, <_M)$ of $Q$ (Robinson arithmetic) to have a *(primitive) recursive presentation* if $\cal{M}$ is isomorphic to $(\omega, \oplus, \otimes)$, where $\omega$ is the set of natural numbers, and $\oplus$, and $\otimes$ are (primitive) recursive functions.

Similarly we can define what it means for $\cal{M}$ to have a *feasible presentation*, by insisting that $\oplus$, and $\otimes$ are polynomial-time computable functions (and representing natural numbers by their base-2 representations).

Questions.

**(1)** *Is there a nonstandard model of the fragment* IOpen *of* $PA$ *with a feasible presentation*? IOpen is a subsystem of Peano arithmetic whose induction axioms are limited to open (quantifier free) formulae.

**(2)** *Suppose a model* $\cal{M}$ *of* IOpen *has a recursive (i.e., computable) presentation, does* $\cal{M}$ *also a primitive recursive presentation? If so, and the answer to (1) is positive, does it have a feasible presentation*?

**Motivation for the Questions.**

Shepherdson (1967) showed that (a) models of IOpen are precisely the integer parts of real closed fields; and (b) in contrast to $PA$, there are nonstandard models of IOpen that have a recursive presentation.

As shown in this paper (which appeared in Theor. Comp. Sci. 2017), in certain classes of structures the notion of having a recursive presentation coincides with the notion of having a primitive recursive presentation; and in some other classes of structures, these two notions diverge (but the paper does not address the status of models of arithmetic).

Shepherdson's work was extended by a number of researchers, including Berarducci, Otero, Moniri, and most recently (to my knowledge) Mohsenipour, who constructed a recursive nonstandard model for IOpen with the GCD property and cofinal primes (in the reference below, he informed me that his construction results in a primitive recursive presentation).

Mohsenipour, Shahram, A recursive nonstandard model for open induction with GCD property and cofinal primes. (English summary) Logic in Tehran, 227–238, Lect. Notes Log., 26, Assoc. Symbol. Logic, La Jolla, CA, 2006.