By Tennenbaum's theorem, PA itself does not have any computable nonstandard models. The integer polynomials which are 0 or have a positive leading coefficient form a computable nonstandard model of Robinson arithmetic, which also happens to make the order relation total. Since Presburger arithmetic is decidable, we can add axioms giving it a nonstandard number and work through Henkin's proof of the completeness theorem to get a computable nonstandard model of Presburger arithmetic. (There's probably a simpler way to get one, though.)


Is any system strictly weaker than PA known to have no computable nonstandard models?


What other systems weaker than PA are known to have computable nonstandard models?


.


possible examples of either include:


I-Delta-0, I-Delta-0(exp), I-Sigma-1


Elementary Function Arithmetic


Elementary Recursive Arithmetic, Primitive Recursive Arithmetic


Robinson arithmetic + Euclidean division, Robinson arithmetic + Euclidean division + order relation is total



Computable nonstandard models for weak systems of arithemtic
One of the usual ways of proving Tennenbaum's theorem also
applies to many of the theories on your list, and so they
can have no computable nonstandard models.


The proof I have in mind is the following, which I also
explained in [this MO
answer](https://mathoverflow.net/questions/12426/is-there-a-computable-model-of-zfc/12434#12434).
Let $A$ be the set of Turing machine programs that halt on
input $0$ with output $0$, and let $B$ be the set of
programs that halt on input $0$ with output $1$. These sets
are disjoint and [computably
inseparable](http://en.wikipedia.org/wiki/Recursively_inseparable_sets),
meaning that there is no computable $C$ containing $A$ and
disjoint from $B$. Now, suppose that $M$ is a nonstandard
model of arithmetic. Let $d$ be a nonstandard natural
number, and inside $M$, consider the set of programs below
$d$ that halt on input $0$ in at most $d$ steps with output
$0$. In $M$, this is a (nonstandard) finite list, and so
there is a nonstandard number $c$ coding this list of
programs. Now, let $C$ be the set of standard programs $p$
that $M$ thinks appear on the list coded by $c$. This
includes every program in $A$, since all such programs halt
in a standard finite time with output $0$, and hence $M$
will agree that they halt before time $d$. Second, for a
similar reason, this set includes no programs in $B$, since
those programs halt in finite time with output $1$, and $M$
will see that. Finally, the set $C$ is computable from the
operations of $M$, since we need only perform the decoding
procedure to see if a given number $p$ is on the list coded
by $c$. For example, we might use the coding that would
require us merely to check whether $M$ thinks that the
$p^{th}$ binary digit of $c$ is $1$ or not. If the
operations of $M$ were computable, then this would be a
computable procedure, in contradiction to the fact that $A$
and $B$ are computably inseparable. QED


Now, we haven't really used much of PA in this argument.
Any theory $T$ that is able to perform basic Goedel coding
and simulate Turing machine computations will be sufficient
for the argument. This includes any $I\Sigma\_n$, even
$I\Sigma\_0$, since the operation of a Turing machine is
inductively iterating a very trivial process. So none of
the stronger theories on your list have computable
nonstandard models.


Meanwhile, however, I am unsure about the very weakest
theories on your list, but this argument reduces the
question to: can the given theory prove that for any number
$d$, there is a number $c$ coding the list of Turing
machine programs less than $d$ that halt on input $0$ with
output $0$ in at most $d$ steps?


This is a comparatively simple statement in arithmetic, and
any theory proving it will not have computable nonstandard
models.


