Non-Standard Computation – Relationship Between Non-Standard Computation and TM(Oracle)

computability-theorylo.logic

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?

Best Answer

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}$.