13
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ 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)? $\endgroup$ Nov 18, 2018 at 19:12
  • $\begingroup$ @EmilJeřábek Thanks for your feedback Emil; your "boling down" comment is on the dot. $\endgroup$
    – Ali Enayat
    Nov 18, 2018 at 19:48
  • 3
    $\begingroup$ @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. $\endgroup$
    – user44143
    Nov 19, 2018 at 1:45
  • 3
    $\begingroup$ Here is the link for the paper mentioned by Matt's comment: people.mpi-inf.mpg.de/~msagralo/RealRootComputation.pdf $\endgroup$
    – Ali Enayat
    Nov 19, 2018 at 21:44

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.