Skip to main content
MathOverflow

Return to Question

replaced http://mathoverflow.net/ with https://mathoverflow.net/
Source Link
Community Bot
Community Bot
  • 1
  • 2
  • 3

After thinking on Joel's answer at Computable nonstandard models for weak systems of arithmeticComputable nonstandard models for weak systems of arithmetic 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.

After thinking on Joel's answer at Computable nonstandard models for weak systems of arithmetic 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.

After thinking on Joel's answer at Computable nonstandard models for weak systems of arithmetic 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.

Source Link
user5810
user5810

Tuple machinery in I-Sigma_0

After thinking on Joel's answer at Computable nonstandard models for weak systems of arithmetic 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.