# Primitive recursive and feasible presentations for nonstandard models of arithmetic

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.

1. 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.

2. 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).

3. 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.

• I think Shepherdson’s model of IOpen may well be feasible. What it boils down is, is there a feasible presentation of the field of real algebraic numbers (or another real closed field)? – Emil Jeřábek Nov 18 '18 at 19:12
• @EmilJeřábek Thanks for your feedback Emil; your "boling down" comment is on the dot. – Ali Enayat Nov 18 '18 at 19:48
• @EmilJeřábek, it seems that one can present the algebraics feasibly, since for an integer polynomial of degree $n$ with coefficients absolutely bounded by $2^r$, we can isolate roots in time at most $O(n^4 + n^3r^2)$. See Michael Sagraloff and Kurt Mehlhorn, Computing Real Roots of Real Polynomials. – Matt F. Nov 19 '18 at 1:45
• Here is the link for the paper mentioned by Matt's comment: people.mpi-inf.mpg.de/~msagralo/RealRootComputation.pdf – Ali Enayat Nov 19 '18 at 21:44