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