After thinking on Joel's answer at [Computable nonstandard models for weak systems of arithemtic](https://mathoverflow.net/questions/38160/computable-nonstandard-models-for-weak-systems-of-arithemtic) for a few days, I do not see how to develop enough tuple machinery in I-Sigma\_0 (PA with induction restricted to Sigma\_0 formulas) to prove the necessary result.


Does I-Sigma\_0 prove that "for any number d, there is a number c coding the set of Turing machine programs less than d that halt on input 0 with output 0 in at most d steps", with a coding such that determining whether a standard number n is in the set is computable from (=,0,S,+,\*)?


With the coding Joel suggested, which is code(set) := $\displaystyle\Pi\_{n \in set} \; p\_n$, I don't even see a way for I-Sigma\_0 to prove "For all n, there is a number coding the set of numbers less than n", and I can't think of a better coding either.



Tuple machinery in I-Sigma_0
As I recall, McAloon's method for proving that there are no computable nonstandard models of $I\Delta\_0$ was to show that there are initial segments that are nonstandard models of PA. The usual Tennenbaum tricks can then be used to show that addition and multiplication are not computable.


Additional Comment--
Here are references for McAloon's paper and the paper of Wilmers that proves a similar result for
$IE\_1$ the fragment of $I\Delta\_0$ where you only have induction for formulas with bounded existential quantifiers


McAloon, Kenneth, On the complexity of models of arithmetic. 
J. Symbolic Logic 47 (1982), no. 2, 403--415. 


Wilmers, George Bounded existential induction. J. Symbolic Logic 50 (1985), no. 1, 72--90.


