Model Theory – Non-Standard Model of PA with Infinitary Computation

infinite-time-computabilitymodel-theoryordinal-computabilitytheories-of-arithmetic

By the Tennenbaum's theorem,
there are no non-standard countable models of
Peano Arithmetic that are computable using Turing machines. What about models of infinitary computation like infinite time Turing machines,
or ordinal Turing machines?

Question: Is there a nonstandard model of PA (countable or not) where both,
or at least one of addition and multiplication are computable by an ITTM or an OTM?

Best Answer

To move this off the unanswered queue, the answer is yes in a very strong way.

The relevant notion is that of a PA degree. There are many equivalent definitions of PA-ness, as well as many interesting results about them, but for the current purposes the relevant ones are the following I think:

  • Definition: d is PA iff every infinite computable subtree of $2^\mathbb{N}$ has a d-computable infinite path.

  • Theorem (Shoenfield?): The following are equivalent for each degree d:

    1. d is PA.

    2. There is a d-computable nonstandard model of PA (this justifies the name, and explains the relevance to the current question).

    • Every computable consistent first-order theory has a d-computable model (this shows that the model-theoretic side of PA-ness is extremely robust).
  • Theorem: there are surprisingly simple PA-degrees - namely ones $\le_T\emptyset'$ (Shoenfield), $<_T\emptyset'$ (Kreisel), and even low (Jockusch/Soare). And there are other basis theorems too, but these three in order tell the simplest story in my opinion.

Consequently, any modification of the Turing machine model in which the usual halting problem is newly computable will be able to construct nonstandard models of PA. ITTMs, OTMs, and every other variation on the basic theme of infinitary computation goes well beyond this; the closest variant I can think of is limit computability, which Shoenfield showed corresponds to computability relative to the halting problem.

See e.g. Diamondstone/Dzhafarov/Soare for more information on PA degrees and the attendant notions.