Hacker News Reader

Comment by sgfyd | Hacker News Reader

> Nevertheless, that incomprehensibly huge number is still an exact figure whose magnitude, according to Aaronson, represents “a statement about our current knowledge” of number theory.

This is, of course, contradicted later in the article in which they point out that `BB(800)` (or so) has been proved independent of ZFC; there's no really good reason to believe `BB(27)` is not likewise independent. There may still be a truth of the matter about the value of `BB(800)` or `BB(27)` (as the case may be), since ZFC hardly encompasses all truth, but calling such a number an "exact figure" is a bit like claiming to know the birth date of Julius Caesar down to the millisecond: Implausible to start with, and the closer you look the more you wonder, "what does the question even mean? Relative to what standard?" (In the one case, "of time"; in the other, "of mathematical truth".)

View on HN

> There may still be a truth of the matter about the value of `BB(800)`

The reason for independence of ZFC is that ZFC fails to prove "TM M doesn't halt", for some non-halting 800-state Turing Machine M. It has no problem proving the halting of the busy beaver machine in BB(800) steps.

Unlike the birth-time of Caesar, BB(800) is still well-defined and an "exact figure", because we consider the notion of whether any particular Turing Machine halts or not to be well-defined.

So does this mean that "the machine that halts if ZF is inconsistent" is guaranteed to not halt (and not loop) in less than BB(748) steps?

Or would it be possible for some crazy billionaire to throw immensurable amounts of computing power at the problem and run the machine just to, after a few years, wake up one morning, find that his machine has halted, and tell the world he had proved ZFC to be inconsistent?

Likewise, could he wake up one morning, find his machine caught in an infinite loop, and tell the world "hey, I just proved this machine will never halt, so I proved ZF to be consistent, quod est adsurdum so better forget about ZFC...

A machine looking for inconsistencies cannot enter an infinite loop. The belief that ZFC is consistent is as good as a guarantee that this machine will never halt. It will endlessly search for a non-existing proof of inconsistency.

Btw, even an attempted computation of BB(10) will outlast the heat death of the universe.

Thanks for your answer. But I think this does not address my question (I am genuinely curious from a layman's point of view). As far as I understood from the article:

A well known TM exists with 748 rules, that halts if ZF is inconsistent. Anybody can build and run that machine. Is that correct?

If that is correct, I can run that machine. Imagine I have loads of computing power to run it. Do I have a chance, in principle, even if it is an infinitesimal chance, to either step into a loop or see my machine halting, before BB(748) steps have been done, maybe even within my own lifetime (in principle)? Or is it guaranteed that this machine can not loop or halt before BB(748) steps?

I think it is an interesting question, because in the first case, a proof of ZFC inconsistency would be possible in principle if I get lucky and a halt or loop exists early on (though a proof of consistency would not), in the latter case it would not be possible even in principle because of the limitations of our universe.

Yes, you can run the machine that looks for ZFC inconsistencies. And if it halts, it is necessarily within BB(748) steps, as that forms an upper bound on the halting time of any 748 rule TM. Just know that BB(748) is incomprehensibly larger than BB(10) and the latter can't even be computed within the lifetime of the universe.

But yes, in principle you could stumble upon a ZFC inconsistency that can be proved very easily and takes much fewer steps than even BB(10).

Thanks again, I can see now how my question was nonsensical...

The fact that a number is independent from ZFC does not meant that the number is inexact. The theoretical functioning of a 800 state Turing machine does not obviously depend on your axiom system.

In fact, I find the example a pretty nice argument for 'undecidable' problems having an actual truth value. Specifically because of the thought experiment of 'how would BB(800) not have an actual exact value'.

Reply on news.ycombinator.com