Turing degree of a turing machine with access to an (arbitrary) nonstandard integer

Question

Let us consider Turing machines (or other Turing-complete model of computation) that, in addition to their regular input, are given some integer $H$, where $H$ is positive nonstandard. This means, in particular, that $H$ is greater than any standard integer. What would be the Turing degree of such a machine?

The machine can solve the halting problem for standard turing machines. To see this, just run a machine for $H$ steps. If it halts before $H$ steps, the machine halts, of course. If it has not halted by then, it never will (since a halting standard turing machine always halts after a standard number of steps).

To be more specific, when I say the Turing degree of such a machine, I mean the machine with an oracle that can simulate such a machine on any standard input (it may diverge on nonstandard input). We also only consider them able to solve decision problems.

Note: When I talk about nonstandard integers, I have something like this in mind.

Answer 1

Joel has given one interpretation of this question; let me give another one.

I'll begin by recapitulating an observation made above, but I'll phrase it differently: I claim that viewing the nonstandard number as providing power via its size runs into serious problems in general. In particular, you state that a machine equipped with a nonstandard number $\alpha$ can solve the Halting Problem by asking, "Does $\Phi_e(e)$ halt by time $\alpha$?" However, nonstandard models of PA can believe false $\Sigma^0_1$ facts - maybe $\Phi_e(e)$ doesn't actually halt, but our model thinks it halts at some nonstandard stage $\beta$.

For example, let $\Phi_e$ be the Turing machine that ignores its input and just searches for a contradiction in PA. Of course $\Phi_e(e)$ doesn't halt; but supposing $M\models$ PA + $\neg$Con(PA), $M$ will think that it halts, and so your idea of a computation will get the halting problem wrong. (More generally, the informal idea you've described will merely let you compute a possibly proper superset of the halting problem.)

---

So I think the "power-through-size" idea can be dangerous (and for instance this is embodied in Joel's observation that there are partial computable functions that are not partial computable with nonstandard help). One response to this difficulty is to restrict attention to a nicer class of models - such as the models of true arithmetic - and as Joel observes, this can give a much more satisfying picture.

I'm going to do something different: I want to look at power-through-structure. The idea here is that we can think of standard natural numbers as finite objects with a lot of properties (e.g. their prime factorizations). A nonstandard natural number carries the same kinds of information, but much more of it. In particular:

Let $M$ be a possibly nonstandard model of PA. For $n\in M$, let $string(n)$ be the infinite binary string whose $k$th bit is $1$ iff $M\models p_k\vert n$, where $p_k$ is the (numeral representing the) $k$th prime.

(Here by "infinite string," I mean infinite string in the usual sense: it has only standard bits. In particular, by overspill $M$ won't "see" any infinite strings in this sense if $M$ is nonstandard.)

Intuitively, computing $string(n)$ from $n$ is a very simple use of $n$: whatever "access to $n$" means, if a Turing machine has access to $n$ it should be able to build $string(n)$.

Now here's the neat part: let the standard system of $M$, $SS(M)$, be $\{string(n): n\in M\}$. If $M$ is standard, this is boring: it consists exactly of those strings with finitely many $1$s. It turns out, though, that if $M$ is nonstandard, the standard system is much more interesting:

If $M$ is a nonstandard model of PA (in fact, much less), then $SS(M)$ is a Scott set: it is closed under Turing reducibility and joins, and if $T$ is an infinite binary tree in $SS(M)$, then there is an infinite path through $T$ in $M$.

(In the language of reverse mathematics, $SS(M)$ is always an $\omega$-model of WKL$_0$ if $M$ is a nonstandard model of PA.)

In fact, this is an exact characterization in the countable case:

Let $A$ be a countable set of infinite binary strings. Then the following are equivalent: (i) $A$ is a Scott set. (ii) $A=SS(M)$ for some countable nonstandard model $M$ of PA.

This is true also if we replace "countable" by "of size $\le \aleph_1$," and whether the size condition can be completely removed is a major open question.

---

OK, now how "powerful" is a Scott set?

It turns out that the answer is, "not very." By iterating the Low Basis Theorem, we can produce a Scott set consisting entirely of low sets - where a set $X$ is low if $X'\equiv_T0'$. In particular, low sets are strictly below $0'$ in the Turing degrees, so this tells us that there are Scott sets not containing $0'$.

We can do better! There is a "universal" computable infinite binary tree $T$: a computable tree $T_{DNR2}$ whose paths are exactly the DNR$_2$ functions - those maps $f:\mathbb{N}\rightarrow\mathbb{N}$ such that $$\varphi_e(e)\downarrow\implies\varphi_e(e)\not=f(e),$$ where $\{\varphi_e\}_{e\in\mathbb{N}}$ is the usual enumeration of partial computable functions. (It's a good exercise to construct $T_{DNR2}$.)

It turns out that any path through $T_{DNR2}$ can compute - uniformly! - paths through all computable trees. Moreover, this construction can be relativized to get a tree $T_{DNR2}^X$, for any set $X$, with the same properties relativized to $X$.

If $Y$ computes a path through $T_{DNR2}$ (resp. $T_{DNR2}^X$), we say $Y$ is a PA degree (resp. PA-over-$X$). The crucial fact about PA degrees is that they are downward dense: if $Y$ is PA over $X$, then there is some $Z\le_TY$ such that $Z$ is PA over $X$ and $Y$ is PA over $Z$. So in fact we have:

Any PA degree bounds a Scott set.

Since all Scott sets contain PA degrees, we also get that given any Scott set, we can find a smaller Scott set.

There's a lot more we can say here - Scott sets and PA degrees are among the most studied objects in computability theory - but hopefully this gives you some idea of what's going on here.

Answer 2

I shall give two different interpretations of the question. (The second interpretation using true arithmetic is modified in this update.)

Using arbitrary nonstandard models of PA. Let us say that a Turing machine program $p$ computes a function $f$ on the natural numbers with nonstandard help, if for any $a\in\mathbb{N}$ and any nonstandard $N\models\text{PA}$ and any nonstandard number $H\in N$, if we run $p$ inside $N$ with input $(n,H)$, then the program halts and gives output $f(n)$, if $n$ is in the domain of $f$, and otherwise it does not halt in $N$.

That is, we run the program inside $N$ with $H$ as an augmented input to $n$, and the program must always compute $f(n)$ in such a situation. The program $p$ must work correctly with any nonstandard help number $H$ and in any nonstandard model $N$.

In this case, we can say exactly what the extra power of this situation is.

Theorem. Assume PA is consistent. Then a total function $f$ is computable with nonstandard help if and only if it is computable.

Proof. Clearly, every computable total function is computable with nonstandard help, since we can simply ignore the extra input $H$.

Suppose conversely that $f$ is a total function computed by program $p$ with nonstandard help. Let $T$ be the theory $\text{PA}$ plus the assertion $0<H$, $1<H$, $2<H$ and so on, asserting that $H$ is a nonstandard number. I claim that $f(n)=m$ just in case $T$ proves that program $p$ on input $(n,H)$ gives output $m$. If $T$ proves this, then in any nonstandard model $N$ of $\text{PA}$ and every nonstandard $H$, the program $p$ on input $(n,H)$ must give output $m$, which must be $m=f(n)$ since $p$ computes $f$ with nonstandard help. And if $m=f(n)$, then in every nonstandard model and every nonstandard $H$, it must be that program $p$ halts on input $(n,H)$ with output $m$, and so $T$ will prove this.

It now follows that $f$ is computable, since the graph of $f$ will be computably enumerable, by searching for proofs in $T$. On input $n$, search for a proof in $T$ that $p$ halts on $(n,H)$ with some specific output $m$, and when this is found, output $m$. $\Box$

This argument shows that your remarks about computing the halting problem and whatnot are incorrect. The reason is that you get false positives with that argument in some nonstandard models of PA. It can happen that some models of PA think a program halts, but it doesn't really halt at any standard stage.

The argument does not work with partial functions.

Theorem. A partial function $f$ on the natural numbers is computable with nonstandard help if and only if it is computable and has decidable domain.

In particular, there are computable functions that are not computable with nonstandard help.

Proof. If the function is computable and has decidable domain, then we can see that it is computable with nonstandard help by the algorithm that first decides if $n$ is in the domain, and then if it is, computes $f(n)$, while ignoring $H$. Since that computation is standard finite, it will work inside a nonstandard model $N$.

Conversely, suppose that $f$ is computable with nonstandard help, by some program $p$. The argument of the theorem above shows that $f(n)=m$ just in case theory $T$ proves that $p$ gives output $m$ on input $(n,H)$. So the graph of $f$ is c.e. and so $f$ is computable. So the domain of $f$ is a c.e. set, enumerated by some program $q$. Let $T^+$ be the theory of $T$ above, plus the assertion that the function $n\mapsto f(n)$ computed by $p$ via $(n,H)$ has domain enumerated by $q$. If the domain of the actual $f$ is not decidable, then there must be a model of $T^+$ in which additional standard elements are enumerated by $q$, for otherwise we could decide the set. Thus, there must be some nonstandard models of PA in which the function computed by $p$ has the wrong domain, a contradiction. $\Box$

So it is a little surprising that not every computable partial function is computable with nonstandard help, since the nonstandard models can get the domain wrong and there is no way to avoid this.

Using only nonstandard models of true arithmetic. A better interpretation is obtained by considering only models of true arithmetic, which I think is closer to what you may have meant by referring to nonstandard analysis.

Let us define that a (partial) function $f$ on the natural numbers is computable by program $p$ with true nonstandard help, if in any nonstandard model $N$ of true arithmetic (that is, an elementary extension of the standard model) and any nonstandard number $H$ in $N$, the program $p$ on input $(n,H)$ halts in $N$ with output $f(n)$, if $n$ is in the domain of $f$, and otherwise does not halt.

One can easily see that $0'$ is computable with true nonstandard help, since one can simulate any Turing machine program for $H$ steps inside any model of true arithmetic, and this will get the right answer for standard input, precisely because the model is a model of true arithmetic. At first, I had thought that we could use that nonstandard fake version of $0'$ and do the same thing to compute $0''$ and $0'''$ and more, but I now think this is wrong. Rather, what is going on is the following:

Theorem. A total function on $\mathbb{N}$ is computable with true nonstandard help if and only if the graph of $f$ has complexity $\Sigma^0_2$.

Proof. If the graph of $f$ is $\Sigma^0_2$, then $f$ is computable from $0'$. Since in any nonstandard model of true arithmetic, we can from any nonstandard number compute an approximation to $0'$ by simulating for $H$ steps, and this will be correct on the standard part. We can therefore use that oracle we generated to compute $f$, and since $f$ is total, we will never need to reach into the nonstandard part of the oracle for any standard input. So $f$ will be computable with true nonstandard help.

Conversely, suppose that $f$ is a total function and computable with true nonstandard help by program $p$. It follows that $p$ on input $(n,H)$ gives output $f(n)$ with any nonstandard model of true arithmetic and any nonstandard $H$. Since any larger $H$ would also work, it follows that $p$ with input $(n,k)$ must give output $f(n)$ for all sufficiently large $k$, including sufficiently large standard $k$. It follows that $f(n)=m$ just in case there is $K$ such that for all $k\geq K$ and all halting computations of program $p$ on input $(n,k)$ gives output $m$. This is a $\Sigma^0_2$-expressible property, and so the theorem is proved. $\Box$

Answer 3

My very short answer is:

any answer to your question depends on the NSA axioms/properties you allow.

My short answer is as follows:

If your Turing machine has to output the same answer for any choice of nonstandard $H$, then underspill tells you immediately that we may replace $H$ by a large enough standard number. Now, underspill follows from Idealisation, and is constructive/effective/... in that this large enough number can be read off from a proof (not involving the other axioms of NSA: Transfer and Standardisation) of this "independence of choice of $H$" property. Hence, such a machine has no extra computational strength.

My long answer is as follows:

In the comments you state that one does not get to pick the nonstandard universe. There are nonstandard universes that do not satisfy the Transfer principle, one of the three main properties of classical NSA. Hence, it is perfectly possible (in such a 'non-standard' universe) that a standard Turing machine (standard index, input, and oracle) runs until time $H+1$, and halts. Transfer actually fails in nonstandard universes satisfying basic intuitionistic axioms, i.e. such universes are not that exotic or 'non-standard'.

Thus, a standard Turing machine only solves the Halting problem in the presence of Transfer (limited to arithmetical formulas). However, translating this fact to the non-NSA world, one just gets the tautology "the Halting problem solves the Halting problem", as Transfer (limited to arithmetical formulas) is translated to a solution to the Halting problem. I even seem to recall that Transfer (limited to arithmetical formulas) is actually equivalent to the property of Turing machines you describe.

Moreover, the Turing machine you describe (with access to $H$) is nonstandard, hence Transfer does not apply to it. Trying to use "that other axiom", namely Standardisation is also a problem: the latter is "even more non-constructive" than Transfer.

Finally, (some advertising) if your are interested in the computational content of NSA, then take a look at my very elementary introductory paper:

https://arxiv.org/abs/1704.00462

In my humble opinion, Nelson's axiomatic approach to NSA is better suited as a framework for such questions than the model theoretic one.