3
$\begingroup$

Turing machines can be encoded as natural numbers. In particular, one can (say, by using the binary representation of a computer program) find a bijection between natural numbers and Turing machines. Now, there exist sets which are nonstandard models of the natural numbers.

Is there work exploring what (according to some reasonable encoding) those Turing machines which are encoded by some non-standard naturals do?

In particular, what, if anything, more can Turing machines in a non-standard model of the integers do that normal Turing machines can't?

Improve this question
$\endgroup$
15
  • 1
    $\begingroup$ overlap with mathoverflow.net/questions/275639/… $\endgroup$
    – Carlo Beenakker
    Commented Aug 8, 2017 at 13:03
  • 1
    $\begingroup$ You might be interested in my blog posts, showing a sense in which every function can be computable in some nonstandard model, using the same universal algorithm: jdh.hamkins.org/every-function-can-be-computable and more recently jdh.hamkins.org/…. $\endgroup$
    – Joel David Hamkins
    Commented Aug 8, 2017 at 13:11
  • $\begingroup$ @CarloBeenakker, I saw that one -- but it seems like it's asking about a Turing machine with access to a non-standard integer -- not one that's encoded by one. $\endgroup$
    – zeno
    Commented Aug 8, 2017 at 13:17
  • 1
    $\begingroup$ @JoelDavidHamkins, That's an interesting post. I think it answers my question (or is an answer, given that my question is open-ended). Thanks. $\endgroup$
    – zeno
    Commented Aug 8, 2017 at 13:18
  • $\begingroup$ The theorem in my post is closely related to a result of Woodin's (and the follow-up post is explicitly about Woodin's theorem), with more recent advances by Enayat and Blanck; earlier formulations of the result go back to Mostowski and Kripke. I can write up a brief answer here summarizing things if you like. $\endgroup$
    – Joel David Hamkins
    Commented Aug 8, 2017 at 13:26

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .