After thinking on Joel's answer at 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.