Return to Answer

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 is misguided. 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$.

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

So I think the "power-through-size" idea is 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.

Instead, 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:

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:

Now 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:

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

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

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:

(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:

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.