It is in fact provably impossible to construct a computable nonstandard model (where, say, S and +, or S and × are both computable relations) in a standard model of computation. What I was referring to was a nonstandard model that was computable according to an equally nonstandard definition of computation, one that makes explicit the definitional dependence of Turing Machines on the standard natural numbers and replaces them with nonstandard ones.
The question I’m wondering about is whether such a definition leads to a sensible theory of computation (at least on its own terms) or whether it turns out to just be nonsense. This may have been addressed in the literature but if so it’s beyond the level to which I’ve read so far.
It is in fact provably impossible to construct a computable nonstandard model (where, say, S and +, or S and × are both computable relations) in a standard model of computation.
Would you give a reference? I found it easy to find assertions such as “the completeness theorem is not constructively provable,” but this statement is a little stronger.
I’m not sure, but I think it’s impossible to construct a computable nonstandard model of the integers (one where you can implement operations like +).
It is in fact provably impossible to construct a computable nonstandard model (where, say, S and +, or S and × are both computable relations) in a standard model of computation. What I was referring to was a nonstandard model that was computable according to an equally nonstandard definition of computation, one that makes explicit the definitional dependence of Turing Machines on the standard natural numbers and replaces them with nonstandard ones.
The question I’m wondering about is whether such a definition leads to a sensible theory of computation (at least on its own terms) or whether it turns out to just be nonsense. This may have been addressed in the literature but if so it’s beyond the level to which I’ve read so far.
Would you give a reference? I found it easy to find assertions such as “the completeness theorem is not constructively provable,” but this statement is a little stronger.
Tennenbaum’s Theorem