# Relationship between non-standard computation and TM(oracle)?

We know that there are non-standard models of arithmetic, and in such models there are non-standard proofs of standardly unprovable sentences. Now, we can imagine a version of representability relative to some non-standard model of some arithmetical theory such that the said function would be what I would call a "non-standard computation". At the same time we can imagine the said computation otherwise correct, as in it would be the same as adding some real/oracle to a TM. Is there a nice way to connect these concepts? Is it a trivial connection? Can it give us insights about the base theory X or the sentence S such that X + "sentence S" $$\vdash$$ TM(oracle) halts?

• I believe Joel Hamkins can shed a lot of light on this question. Dec 28, 2021 at 20:04
• For a taste of the state of the art in the realm of nonstandard computations, I suggest the following blog of Hamkins: jdh.hamkins.org/… Dec 29, 2021 at 1:21
• Thank you both of you. Also @Sam Sanders I see that you are interested in coding. I am also interested in the limits of coding as much information as possible in relatively weak theories. What could you recommend as literature? Dec 29, 2021 at 8:36
• Let me reformulate the question (and perhaps make it more confusing): if $ℳ$ is a model of PA, we can define six sets of subsets of $ℕ$, namely ⓐthose $X⊆ℕ$ for which there is $e∈ℳ$ such that $∀i∈ℕ.ℳ⊧(e•i)↓$ and $∀i∈ℕ.(i∈X⇔ℳ⊧(e•i)=1)$, ⓑthose $X⊆ℕ$ for which there is $e∈ℕ$ such that $∀i∈ℕ.ℳ⊧(e•i)↓$ and $∀i∈ℕ.(i∈X⇔ℳ⊧(e•i)=1)$, ⓒthose $X⊆ℕ$ for which there is $e∈ℳ$ such that $∀i∈ℳ.ℳ⊧(e•i)↓$ and $∀i∈ℕ.(i∈X⇔ℳ⊧(e•i)=1)$ and ⓓthose $X⊆ℕ$ for which there is $e∈ℕ$ such that $∀i∈ℳ.ℳ⊧(e•i)↓$ and $∀i∈ℕ.(i∈X⇔ℳ⊧(e•i)=1)$, (…contd…) Jan 16 at 10:22
• @Gro-Tsen If I am understanding your comments correctly then my answer only shows that (a) and (c) coincide with the standard system of $\mathcal{M}$. On the other hand, (e) just consists of finite sets of natural numbers by overspill. Jan 16 at 16:08

Edit: I think the answers given so far do not completely address the original question nor Gro-Tsen's follow up questions. I believe I can address some of these points so I have greatly expanded my original answer. In brief, no reasonable notion of "computation according to a nonstandard model of arithmetic" seems to be equivalent to "standard computation with an oracle for some real." Additionally there is a pretty good characterization of which sets of Turing degrees can constitute the sets computable according to some nonstandard model of arithmetic.

Some terminology and standard results

Suppose $$\mathcal{M}$$ is a nonstandard model of arithmetic (meaning either PA or some weak fragment of PA containing a sufficient amount of induction to make all arguments below work).

First, some standard terminology. Pick some reasonable way of using natural numbers to code finite sequences and let $$a(i)$$ denote the $$i^\text{th}$$ element in the sequence coded by $$a$$. Define the standard system of $$\mathcal{M}$$, written $$SSy(\mathcal{M})$$, to be the set $$\{x \subseteq \mathbb{N} \mid \exists a\in M\, (\forall i \in \mathbb{N}\, (i \in x \iff a(i) = 1))\}.$$ In other words a subset of $$\mathbb{N}$$ is in the standard system of $$\mathcal{M}$$ if it is an initial segment of some $$\mathcal{M}$$-finite sequence coded by an element of $$\mathcal{M}$$.

If it is known that the standard system of any nonstandard model of PA has some special properties. First, it is closed under relative computability—i.e. if $$x$$ is in the standard system and $$y \le_T x$$ then $$y$$ is also in the standard system. Second, it is closed under computable joins—if $$x$$ and $$y$$ are both in the standard system then so is $$x \oplus y$$. Third, if $$T$$ is an infinite binary tree, some representation of which is in the standard system, then the standard system also contains some infinite path through $$T$$.

I believe these results are originally due to Dana Scott. A careful exposition of them can be found in Kaye's book on models of arithmetic. Unfortunately I don't have a copy of that book on hand so I can't provide a reference so instead I'll link to these notes by Tin Lok Wong (see Theorem 3.5 in particular).

Scott actually proved something more, which will be relevant below. Any set of reals which satisfies the three properties above is called a Scott set. The results mentioned above show that the standard system of any nonstandard model of PA is a Scott set. A partial converse is also true: Scott showed that any countable Scott set is the standard system of some model of PA and Knight and Nadel later extended this to Scott sets of size $$\aleph_1$$ (which finishes the story if we assume CH).

Lastly, let's note that no Scott set is equal to the set of reals computable from some oracle. To see why, let $$A$$ be a Scott set and suppose $$A$$ is equal to the reals computable from $$x$$. Then $$x \in A$$. But if we let $$T$$ be an infinite binary tree computable from $$x$$ with no infinite path computable from $$x$$ then we can see that $$A$$ must contain an infinite path through $$T$$ and thus not every real in $$A$$ is computable from $$x$$.

Computation According to a Nonstandard Model

Let $$\mathcal{M}$$ be a nonstandard model of arithmetic and define "computation according to $$\mathcal{M}$$ as follows: say that a set $$x \subseteq \mathbb{N}$$ is "computable according to $$\mathcal{M}$$ if there is some (possibly nonstandard) number $$e \in M$$ such that $$\mathcal{M} \models \forall n\, (\varphi_e(n) \downarrow)$$ and $$x = \{n \in \mathbb{N} \mid \mathcal{M} \models \varphi_e(n) = 1\}$$—in other words, $$\mathcal{M}$$ believes that the program coded by $$e$$ converges on every input and $$x$$ consists of those natural numbers on which $$\mathcal{M}$$ believes that $$e$$ converges and is equal to $$1$$.

It is easy to see that every set in $$SSy(\mathcal{M})$$ is also "computable according to $$\mathcal{M}$$." The converse is also true. Indeed, it is provable in PA that for any index for a program $$e$$ and any number $$b$$, there is a number $$a$$ coding a sequence which records those numbers less than $$b$$ on which the program coded by $$e$$ converges and outputs $$1$$ (i.e. $$a$$ codes a sequence of length $$b$$ and $$a(i) = 1$$ if and only if $$i < b$$ and $$\varphi_e(i) = 1$$). Now suppose $$e$$ is a (possibly nonstandard) index for a program. Let $$b$$ be any nonstandard number and let $$a$$ be a nonstandard number coding the sequence we have just mentioned. Then the set $$\{i \in \mathbb{N} \mid a(i) = 1\}$$ is exactly the subset of $$\mathbb{N}$$ "computed by $$e$$ according to $$\mathcal{M}$$" and it is clearly in the standard system of $$\mathcal{M}$$.

Since the set of reals "computable according to $$\mathcal{M}$$" is exactly $$SSy(\mathcal{M})$$ and $$\mathcal{M}$$ is a Scott set, the set of reals "computable according to $$\mathcal{M}$$" cannot be equal to the set of reals computable from some oracle.

What if the program only needs to converge on every natural number?

Gro-Tsen proposed a number of modifications of the above definition of "computation according to $$\mathcal{M}$$." The first modification is to relax the requirement on what it means for a program to converge on all inputs. Above we required that $$\mathcal{M}$$ believes that the program coded by $$e$$ converges on all inputs in $$\mathcal{M}$$. What if we only require that $$\mathcal{M}$$ believes it converges on all inputs in $$\mathbb{N}$$? In other words instead of $$\mathcal{M} \models \forall n\, (\varphi_e(n) \downarrow)$$ we only require $$\forall n \in \mathbb{N}\,(\mathcal{M} \models \varphi_e(n)\downarrow)$$?

The answer is that this doesn't change anything. In particular, suppose $$e$$ is an element of $$\mathcal{M}$$ which codes a program which $$\mathcal{M}$$ believes converges on every input in $$\mathbb{N}$$. By overspill there must be some nonstandard number $$b$$ such $$\mathcal{M}$$ believes that the program coded by $$e$$ converges on all inputs less than $$b$$. Let $$e'$$ be an index for a program which does the same thing as $$e$$ on all inputs less than $$b$$ and immediately halts and outputs $$0$$ on any input greater than $$b$$. Then the program coded by $$e'$$ converges on every input in $$\mathcal{M}$$ and corresponds to the same subset of $$\mathbb{N}$$ as $$e$$.

What if the program index has to be a (standard) natural number?

The next modification proposed by Gro-Tsen is more serious. What if we require that the index $$e$$ be a standard natural number rather than an arbitrary element of $$\mathcal{M}$$? The answer is that with this new requirement, the sets "computable according to $$\mathcal{M}$$ still cannot coincide with the sets computable from some oracle, except in one very special case.

To explain things more clearly, let me make another definition. Let's define the computable standard system of $$\mathcal{M}$$, written $$CSSy(\mathcal{M})$$, to be the set $$\{x \subseteq \mathbb{N} \mid \exists e \in \mathbb{N} \, \forall n \in \mathbb{N} \, (\mathcal{M} \models \varphi_e(n)\downarrow \text{ and } (n \in x \iff \mathcal{M} \models \varphi_e(n) = 1)\}$$ (note that this is not standard terminology). As Joel David Hamkins pointed out in his answer, $$CSSy(\mathcal{M})$$ can never be equal to $$SSy(\mathcal{M})$$ for any nonstandard model. The question is then: when is $$CSSy(\mathcal{M})$$ equal to the set of reals computable from some oracle?

The answer is that this can only occur if $$CSSy(\mathcal{M})$$ is exactly the set of computable reals. However, unlike the situation above, this can occur even if $$\mathcal{M}$$ is nonstandard.

For example, suppose $$\mathcal{M}$$ is a model of the true first order theory of the natural numbers. Then for any $$e\in \mathbb{N}$$, the program coded by $$e$$ will have the same behavior in $$\mathcal{M}$$ as it does in the "real world" so $$CSSy(\mathcal{M})$$ will not contain any noncomputable reals. And by compactness, it is possible for $$\mathcal{M}$$ to be nonstandard.

However, if $$CSSy(\mathcal{M})$$ contains any noncomputable real then it must actually be a Scott set and thus cannot be equal to the set of reals computable from some oracle. The only difficult part of this is to show that $$CSSy(\mathcal{M})$$ is closed under finding infinite paths through infinite binary trees so here's a proof of that part.

First, suppose $$e \in \mathbb{N}$$ is an index for a program and $$n \in \mathbb{N}$$ is an input such that $$\varphi_e(n)$$ diverges but $$\mathcal{M}$$ believes it converges (such an $$e$$ and $$n$$ must exist if $$CSSy(\mathcal{M})$$ contains any noncomputable sets). Let $$T$$ be an infinite binary tree which is in $$CSSy(\mathcal{M})$$. Let $$a$$ be the program which does the following on input $$i$$: first, it waits for $$\varphi_e(n)$$ to converge. If it converges after $$m$$ steps then $$a$$ looks for the largest $$k \leq m$$ such that $$T$$ contains a path of length $$k$$. If $$i \leq k$$ then it prints the $$i^\text{th}$$ element of the leftmost path of length $$k$$ in $$T$$. Otherwise it prints $$0$$. By overspill, $$\mathcal{M}$$ believes $$T$$ contains a path of nonstandard length so in $$\mathcal{M}$$ the program coded by $$a$$ will print a valid path through ($$\mathcal{M}$$'s version of) $$T$$ and when restricted to $$\mathbb{N}$$ that is an honest infinite path through $$T$$. However, since the description we gave above of $$a$$ only depended on the standard numbers $$e$$ and $$n$$, $$a$$ is itself standard and thus this infinite path is in $$CSSy(\mathcal{M})$$.

What if we require the program to converge on all inputs in $$\mathcal{M}$$?

In the definition of $$CSSy(\mathcal{M})$$ above, I only required the program $$e$$ to converge on all inputs in $$\mathbb{N}$$, not all inputs in $$\mathcal{M}$$. What if we change this? It turns out this doesn't really change anything about the above proof (basically because we were able to ensure that $$a$$ converges on all inputs) and so in this new version, $$CSSy(\mathcal{M})$$ is still either the set of computable reals or a Scott set (though perhaps a different Scott set than under the old definition).

What if we don't intersect with $$\mathbb{N}$$ in the definitions above?

It might seem a bit funny that when we looked at sets "computed according to $$\mathcal{M}$$ we were always taking an intersection with $$\mathbb{N}$$—i.e. we looked at $$\{n \in \mathbb{N} \mid \varphi_e(n) = 1\}$$ rather than $$\{n \in M \mid \varphi_e(n) = 1\}$$. This is for good reason. As mentioned by Joel David Hamkins, overspill implies that any set of the latter form is either finite or contains nonstandard numbers. So if we are ultimately interested in sets of natural numbers then this version of the question is very boring (the only sets of natural numbers "computable according to $$\mathcal{M}$$" are finite sets).

What are the sets of Turing degrees in each of these scenarios?

Gro-Tsen also asked about the possible sets of Turing degrees corresponding to each definition of "computable according to $$\mathcal{M}$$." Here, there is a pretty good partial answer. For each non-trivial definition above, the reals "computable according to $$\mathcal{M}$$" must always comprise a Scott set (though the converse is not clear). And quite a lot is known about sets of Turing degrees which form a Scott set so quite a lot is known about sets of Turing degrees which are those "computable according to $$\mathcal{M}$$" for some nonstandard $$\mathcal{M}$$.

• Could you provide some references (or arguments) for the statements you assert in the paragraph beginning with “It is known that the standard system of a nonstandard model of PA has some special properties”? Jan 16 at 9:54
• IIUC, your answer tells us that sets (of standard integers) which are “computable according to $\mathcal{M}$” are the same as the standard system (viꝫ. “encodable as a tuple according to $\mathcal{M}$”). But one could also inquire about sets which are “computable according to $\mathcal{M}$ but with a standard index” (i.e., there is a standard program that might not terminate in standard time on certain indexes but terminates in times in $\mathcal{M}$). I'm not sure if the OP was more interested in the former or the latter (both seem worth looking at). Jan 16 at 9:59
• This should be the accepted answer. The main point is that the standard system is the focal concept in this vicinity. Jan 19 at 14:15
• Than you for the great update @PatrickLutz. Given that Joel recommended it too, I accepted this as the answer. I will certainly have to look more into this and I am glad I asked the question because I didn't think there is such a technical connection involving Scott sets and realizability as seem to be suggested by those notes. Jan 19 at 21:01
• Also thank @Gro-Tsen for the much clearer exposition of what I had more or less in mind Jan 19 at 21:12

Let address the version of the question posed by Gro-Tsen in his comments.

• Sets (a) and (c) are the same, and these are exactly the standard system of the model $$M$$, as mentioned in the answer of Patrick Lutz. The standard system is equivalently defined as the set of traces on the standard numbers of any sequence that is definable from parameters in $$M$$, whether or not it is computable in $$M$$, since every (possibly nonstandard) finite initial segment of a definable sequence is an element of $$M$$. Any sequence as in (a) or (c) will be the standard part of a definable sequence in $$M$$ and thus in the standard system, and conversely, any set in the standard system is the standard part of a pseudo finite sequence in $$M$$, which can be hard-coded into a (nonstandard) program $$e$$ in $$M$$, fulfilling (a) or (c).

• Set (b) consists of the sets of natural numbers that are the trace of a set that is computably enumerable in $$M$$ by a standard program $$e$$, such that this program gives output on all standard input. This is equivalent to the sets of natural numbers such that both it and its complement are the standard parts of sets that $$M$$ thinks are computably enumerable using a standard program. In a model of true arithmetic, this would be exactly the computably decidable sets, since the operation of a standard program $$e$$ would be the same in $$\mathbb{N}$$ as in $$M$$ in this case. Thus, this set can be strictly smaller than the sets in (a) and (c). Meanwhile, the universal algorithm (see also Arithmetic potentialism and the universal algorithm (arXiv:1801.04599) shows that any given set of natural numbers can be placed into set (b) for a suitable choice of $$M$$, since the universal algorithm $$e$$, which is a standard program, can compute any set in a suitable model $$M$$ of PA, and by arranging that the program enumerate the set in increasing order, one will also be able to compute the complement with a standard program. Nevertheless, set (b) is never equal to the sets in (a) and (c), because the model $$M$$ can unify the sets of (b) into a single subset of $$\mathbb{N}\times\mathbb{N}$$, using program $$e$$ on slice $$e$$. This will be a set in the standard system, from which all sets in (b) are computable, but the standard system must have sets not computable from any given set.

• Set (d) consists of the standard parts of the sets that $$M$$ thinks are computably decidable by a standard program. In a model of true arithmetic, these are exactly the computably decidable sets, but by using the universal algorithm as above, we can place any given set into set (d). The difference between set (d) and set (b) is that the programs in (b) must halt only on all standard input, but in (d) they must halt on all input. So set (d) is contained in set (b). I would have to think harder whether the sets can differ. But the argument I gave above shows that (d) is never equal to (a) or (c).

• Sets (e) and (f) consists exactly of the finite sets of natural numbers. Any finite set of natural numbers has the property in (e) and (f), and conversely, if a set is infinite and definable in a nonstandard model $$M$$ of PA, then it must have nonstandard elements, since otherwise it would stand as a counterexample to induction in $$M$$.

A modified version of (e) would be the property (e'), asserting that $$X\subset\mathbb{N}$$ and there is some program $$e\in M$$ that halts on all input in $$M$$, such that $$\forall i\in \mathbb{N} (i\in X\iff \{e\}(i)\downarrow=1)$$. This would be equivalent to (a) and (c).

• I do not agree that (e) coincides with the standard system of $\mathcal{M}$. Indeed, by exactly the argument you mention for (f), (e) should just consist of all finite sets of natural numbers. See also my comment to Gro-Tsen above. Jan 16 at 16:09
• You are right, I had misread (e) to the be the (more interesting) case (e') with $\forall i\in\mathbb{N}$. As stated (e) is silly because of my argument for (f). I have now edited. Jan 16 at 16:44
• Ah yes, sorry, I missed (e′) in my attempt to find every conceivable wording of the question! But then I also missed (f′) asserting that there is some $e\in\mathbb{N}$ that halts on all input in $\mathcal{M}$ and that $\forall i\in\mathbb{N} . (i\in X \Leftrightarrow e\bullet i = 1)$. Jan 16 at 18:48
• @JoelDavidHamkins If I'm not mistaken, your (e') is just Gro-Tsen's original (c). Jan 19 at 9:34
• @Gro-Tsen It seems to me that your (f') is just the same as your (d) but maybe I'm missing something. I really do think you covered all possible permutations. You seem to be varying three parameters: is $e$ in $\mathbb{N}$ or just in $M$, is it required to halt on all inputs in $M$ or just in $\mathbb{N}$ and is it required to match $X$ exactly or only on inputs in $\mathbb{N}$? So there are $8$ possibilities and $2$ are incoherent (if the program doesn't converge everywhere in $M$ we should not use it to define a subset of all of $M$). Jan 19 at 9:37