Computing the Uncomputable
johncarlosbaez.wordpress.com
johncarlosbaez.wordpress.com
We can define natural number as an ordinal that's well ordered by its element relation and the reverse of the element relation (all those terms are defined). Or just as a finite ordinal, in the sense of not being equipollent to any strict subset. Or as the ordinals not containing any limit ordinals or being a limit ordinal.
2. This should probably be thought of as the machine doesn't halt, but in some models, we can "prove" that it halts and has any result. This is kind of like how you can rearrange the terms of some series to sum to any number. https://en.wikipedia.org/wiki/Riemann_series_theorem
(I wonder if there's a way to get the computability result from this result by some clever isomorphism.)
Edit: fixed definition and added another one.
It's a bit more subtle. Wikipedia puts it well:
Even for those mathematicians who embrace infinite sets, in certain important contexts, the formal distinction between the finite and the infinite can remain a delicate matter. The difficulty stems from Gödel's incompleteness theorems. One can interpret the theory of hereditarily finite sets within Peano arithmetic (and certainly also vice versa), so the incompleteness of the theory of Peano arithmetic implies that of the theory of hereditarily finite sets. In particular, there exists a plethora of so-called non-standard models of both theories. A seeming paradox, non-standard models of the theory of hereditarily finite sets contain infinite sets - but these infinite sets look finite from within the model. (This can happen when the model lacks the sets or functions necessary to witness the infinitude of these sets.) On account of the incompleteness theorems, no first-order predicate, nor even any recursive scheme of first-order predicates, can characterize the standard part of all such models. So, at least from the point of view of first-order logic, one can only hope to characterize finiteness approximately.
It seemed obvious that defining the natural numbers in the way above results in only such numbers. You can give an intuitive argument that any natural number can be recursively generated from 0 by the successor operator. Is this wrong?
Edit: looks like http://www1.cuni.cz/~svejdar/papers/sv_ybk10_p.pdf says you can get such a model.
>A model M of (some) set theory is non-standard if it contains an ordinal α such that M |= “α is finite”, i.e. M |= “α is less than the first limit ordinal”, but looking from outside, the set of all ordinals β < α is infinite. The proof of the existence of non-standard models of set theory is basically the same as for PA.
Another fun fact is that ZF has a countable model, even though ZF proves that uncountable sets exist. https://en.wikipedia.org/wiki/Skolem%27s_paradox
Take any formal theory T that talks about natural numbers, like PA or ZF. We'll assume that T can be encoded as a computer program, printing out sentences about natural numbers in some simple language with arithmetic and quantifiers. We won't make any other assumptions about the theory's internal workings, it can use any axioms it likes.
Thanks to the miracle of Turing completeness, any facts about that computer program can also be encoded as sentences about natural numbers. So we can construct a sentence called Con(T) which says essentially "the program will never print 0=1", or equivalently "there's no natural number N encoding a proof in T that 0=1". That sentence encodes the idea that "T is a consistent theory" within T itself.
Godel's theorem says that T cannot prove Con(T). Therefore we can extend T with the negation of Con(T), and the resulting "self-hating" theory T+¬Con(T) will be as consistent as T itself. Like all consistent theories, that theory will have a model, which is also a model of the original theory T. In that model, Con(T) is axiomatically false, so the above-defined number N is asserted to exist. But if we assume that T was consistent to begin with, then there's actually no finite proof in T that 0=1, so N can't be a standard natural number. Therefore N is nonstandard, so T has a model with a nonstandard natural number. QED.
I explained this in a bit more detail here:
https://johncarlosbaez.wordpress.com/2016/04/02/computing-th...
Here's a little tidbit that might make you more at peace with what's happening. Imagine that you didn't know anything about Godel's results. If you found some theory that proved its own consistency, would that be a reason to trust that theory more? Not at all! Inconsistent theories also happily prove their own consistency (because they prove all sentences). So it seems like Godel's theorems are thwarting a desire that was wrong-headed to begin with.
Set theory have infinite number of models, each model having different kind of "finite" ordinals.
Perhaps it is fair to say that “finite” does not mean what we have always thought it to mean. What have we always thought it to mean? I used to think that I knew what I had always thought it to mean, but I no longer think so.
If we go down this road, Hamkins’ result takes on a different significance. It says that any subjectivity in the notion of ‘natural number’ may also infect what it means for a Turing machine to halt, and what function a Turing machine computes when it does halt.
Is beautiful. It seems like another proof for a leaky abstraction and incomepleteness.
We have to forget finite or admit that it has bounds on what we can explore with it, as it already defines our model.
"I used to think that I knew what I had always thought it to mean, but I no longer think so".
OR is it that there have to be infinite starting objects? OR should we think of it as having zero and both a successor function and a weirdSuccessor function (whose applications commute) such that > considers the number of weirdSuccessor applications before it looks at the number of successor applications?
For example, consider the set embedded in the rationals as
0, 1/2, 3/4, 7/8 , ... , 1, 3/2, 7/4, 15/8, ...