I’d always taken it as a given that, if you don’t have a pre-existing understanding of what’s meant by a “finite positive integer,” then you can’t even get started in doing any kind of math without getting trapped in an infinite regress.

Scott Aaronson

So they had this discussion again about (Beeping) Busy Beavers and Turing machines halting or not, depending on your version of the natural numbers. Scott repeated his argument that you would get trapped in an infinite regress if you conceeded to the objection of the sceptic (dankane) that:

As for whether you should always be assumed to be talking about the “standard integers”, the issue is that actually defining what you mean by the “standard integers” is impossible to do rigorously.

### A formal definition of non-standard natural numbers

Defining non-standard integers is easy. Add the following axioms , , , …, , … to PA. Then is a non-standard integer, and any non-standard model of PA will contain such a . Here is Scott’s argument:

My answer, again, is that the goal is not merely impossible, but

misguided. I.e., even supposing therewerefirst-order axioms that picked out and only , a skeptic could then object that you didn’t define the primitives of first-order logic in terms of yet more basic concepts, and so on, trapping you in an infinite regress.

Is Scott right? Can the skeptic still object that our definition didn’t catch all non-standard integers, because it uses basic concepts from first-order logic that are not basic enough? Sure, the skeptic can complain that we used an infinite set of axioms. But the axioms for PA are also an infinte set, so that objection seems unfair. Now the skeptic points out that we could (or even should) have used Robinson arithmetic instead of PA, which is finitely axiomatized. Uff, well, let’s think: could there be a finite axiomatization of the non-standard integers? Probably not, because otherwise the conjuction of those axioms would be a single formula, and we could wrap it in to get an axiomatization of the standard integers.

### Quasihalting TMs as representations of natural numbers

Let me grant this point to both Scott and the skeptic for the moment, and focus instead on Beeping Busy Beavers and their relation to non-standard integers. Even so a number like BBB(5) is huge, it nevertheless has explicit useful short representations: Any representation of the transition table of a quasihalting 5-state TM running longest (among 5-state TMs) before quasihalting will do. To see how useful it is, let us see what would change in Nick Drozd’s description of adjudicating a BB game:

Scott proposed the Busy Beaver function as a way to win the BNG. But we can also think of each BB value as being its own Bigger Number Game played out, where the number of states available to be used correspond to the size of the “index card”.

This version of the BNG is not a duel; instead, we can imagine that each program in the particular Turing machine class has been submitted by a different contestant. Adjudicating this contest requires figuring out which of the halting programs runs the longest. But it also requires figuring out which ones don’t halt at all.

Figuring out which TMs don’t quasihalt is impossible, but so was figuring out which TMs don’t halt. What about figuring out which quasihalting programs runs the longest before leaving their beeping state the last time? We can run the TMs in parallel, and each time a TM leaves its beeping state, it temporarily becomes one of the winners. After a sufficiently long time, the winners will no longer change, and indeed will coincide with the true winners.

### Oracles for quasihalting TMs that provide proofs for their answers

So a representation of a quasihalting TM is actually a representation of a natural number. Or maybe not, at least according to my pre-existing understanding of a natural number. In my pre-existing understanding, a natural number has the “I know it when I see it” property. (For me, any natural number possesses a representation in a prefix-free encoding, or a morally similar representation.) So if you give me a halting TM as a representation of a natural number, this is OK for me. By running that TM, I will eventually see that it indeed represents a natural number. But a quasihalting TM cannot do that for me.

What about an oracle for quasihalting TMs, that provides me with a halting TM, which runs longer than the quasihalting TM will run before leaving its beeping state the last time? That would be fine for me. Interestingly enough, there are now two different ways that the oracle can lie to me: It can either hand me a TM which will never halt, or it can take forever to describe the TM (i.e. it will provide a TM with infinitely many states).

### Representations of non-standard natural numbers

Now non-halting TMs can be used as representations of at least some non-standard natural numbers. Are there non-standard models of PA were all numbers are represented by halting or non-halting TMs, or will there always also be non-standard numbers that can only be represented by non-quasihalting TMs? Since the non-standard models constructed by the model existence theorem are limit computable, the expectation is that non-standard numbers representable only by non-quasihalting TM will be absent in such models.

What about the opposite, will any non-standard model of PA always contain a number represented by a non-halting TM? No, one could add all true – and -sentences as axioms to PA, the result would still be a first-order theory, and hence there would still be non-standard models. And there would still be undecidable -sentences in that theory, so there would be a non-standard model with a number represented by a non-quasihalting TM. (So an oracle for quasihalting TMs in that non-standard model would be forced to sometimes lie by taking forever to describe the TM, or more precisely by providing a TM with a non-standard number of states.)

### Conclusions?

The axioms for our formal definition of non-standard natural numbers are enumerated by a normal TM. If we have non-standard numbers in our (meta-)model, then it can run a non-standard number of steps, and thereby exclude all our non-standard numbers. So the conclusion in the end will be that our (meta-)model does not qualify as non-standard according to that definition. So the skeptics was right, and we failed to rigorously define non-standard integers. And Scott is right too, in the sense that our whole discussion of course supposed a pre-existing understanding of what we mean by standard and non-standard natural numbers.

But did the skeptic really started with a pre-existing understanding of non-standard natural numbers? I guess that depends on the specific skeptic. Is the skeptic *misguided*? It depends. If he invokes second-order logic, without having any specific idea what second-order logic buys him, then yes. But otherwise? Who cares!