35
$\begingroup$

I've been pondering some stuff on Shtetl Optimized where Yedidia and Aaronson construct Turing machines that will only halt if (e.g.) the Riemann Hypothesis is false, or Goldbach's conjecture is false. The significance is that if you took the number of states in one of these machines, and knew the Busy Beaver number for that number of states, you could just run the machine for that many iterations, and you would know the truth or falsehood of these conjectures based on whether the machine stopped in time or not.

Ignoring the practicality of such a method of proof (the BB numbers are nauseatingly big compared to just about anything you could name), I'm still having trouble squaring this proof method with Gödel's proof that any axiomatic system will have true statements that can't be proved within that system. (I was even of the understanding that Riemann's and/or Goldbach's might, terrifyingly, even be examples of such true-but-unprovable statements.) It would seem to me that any ZF statement could be encoded as a Turing machine, and then proven as true or false by running the machine for BB(n) steps.

So where would the Busy Beaver approach fall over, to leave room for the true-but-unprovable statements? I've been pondering this without much success. I'm thinking I might be wrong either in a) my assumption that any ZF statement could be encoded as a Turing machine, or b) that maybe BB(n) itself is not determinable within ZF. The latter seems more likely, given the difficulty of proving even BB(5), but any BB number seems to me, in principle at least, determinable. So neither resolution seems right to me.

$\endgroup$
13
  • 2
    $\begingroup$ What is the source of your intuition that BB(n) is determinable in principle? $\endgroup$
    – Will Sawin
    Commented Jan 4 at 16:35
  • 4
    $\begingroup$ In a nutshell, the problem is that even if someone hands you a machine which happens to be the true busy beaver (which runs BB(n) steps and then halts), someone else could hand you another Turing machine M which runs longer than BB(n) steps. In reality, M won't halt, but you might have no way of proving that M will never halt. That is, you have no way to rigorously rule out the possibility that M is the true busy beaver. $\endgroup$ Commented Jan 4 at 17:56
  • 1
    $\begingroup$ Fundamentally this is not different than the belief "for each $n$ there is some $N$ so that for any statement of size $\leq n$, there is either a proof of it or of its negation of size $\leq N$." (Of course, you have to be a little careful about what we mean by "size" of a statement/proof, but you can imagine a definition.) If we knew the right $N$ for a given $n$, and had a statement we wanted to check of size $\leq n$, we could simply test all proofs/disproofs of size $\leq N$. But in the end this belief is misguided because there are statements independent of our axiomatic system. $\endgroup$ Commented Jan 4 at 18:45
  • 1
    $\begingroup$ @TimothyChow to me, that appears to confuse two notions of determinable, i.e. of course BB(n) is not computable by reduction from halting, but it's much less obvious that BB(n) could be independent of ZFC. $\endgroup$
    – usul
    Commented Jan 6 at 2:29
  • 1
    $\begingroup$ @schnitzi If I understand your question correctly, this is what Joel David Hamkins is saying in his answer below. $\endgroup$ Commented Jan 7 at 13:02

3 Answers 3

32
$\begingroup$

Indeed, the second option is a problem: the BB($n$) cannot be computed in ZF for $n$ large (an explicit bound $n\ge 7910$ was given by Aaronson-Yedidia in their article A Relatively Small Turing Machine Whose Behavior Is Independant of ZFC you refer to, and $n\ge 748$ seems to be the current bound due to Riebel), the reason being you cannot prove within ZF some Turing machines which do not seem to halt actually do not halt.

$\endgroup$
2
  • $\begingroup$ I'd point out that ZFC is not the end-all and be-all of set theories; it's possible by appending things like the Tarski-Grothendieck Axiom, we could prove BB(n) for larger n. $\endgroup$
    – prosfilaes
    Commented Jan 4 at 21:46
  • $\begingroup$ @prosfilaes, and from the other direction, if someone manages to prove that the I3 rank-into-rank axiom is necessary to prove the existence of a Laver table with period 32 (currently it's known to be sufficient and unless I've missed a recent proof there's no known proof with weaker assumptions) then that establishes an upper bound of BB(63) being knowable with weaker assumptions. $\endgroup$ Commented Jan 4 at 22:47
28
$\begingroup$

Although the other answers point out correctly that the exact value of $\text{BB}(n)$ is independent of ZF for large enough and even moderately sized values of $n$, nevertheless I should like to point out that the main outline of your proof method is correct. This is a legitimate method of proof.

That is, what I am saying is that if we could somehow know the true value of $\text{BB}(n)$ for certain values of $n$, then indeed we could use that knowledge to determine the truth of the Riemann hypothesis and so forth, for any $\Pi^0_1$ statements whose truth is known to be equivalent to the non-halting of a Turing machine with at most $n$ states. And indeed for every $\Pi^0_1$ statement there is such a Turing machine, since one simply writes the code that goes and looks for a counterexample, halting when found. This machine runs forever if and only if the statement is true. For many classic conjectures, the number of states $n$ would not be very large, although the value of $\text{BB}(n)$ would be enormous, as you mention.

What I am saying is that the theorems would be proved in the theory $\text{ZFC}+\text{BB}(n)=N$, using the additional assumption about the particular value of the busy-beaver function. You would be showing that in every model of ZFC in which the busy-beaver number at $n$ has that value, then indeed the Riemann hypothesis would be true (or false, depending on the outcome of the calculation you propose to undertake).

But furthermore, this very argument can be taken as a proof that the values of $\text{BB}(n)$ cannot all be settled in ZFC (if consistent) even for some small values of $n$. Indeed, the value of $\text{BB}(n)$ for moderate $n$ cannot even be provably bounded by specific numbers, for if we could do this, with $n$ large enough to undertake your proposal with the Rosser sentence, say, and then ZF would have to settle the Rosser sentence, which it does not.

In essence, your proposed argument method becomes a proof that the busy-beaver function values must be independent of ZFC or indeed any foundational theory we might want.

A philosophical can of worms. The method also opens up a certain contentious philosophical debate, however, concerning whether indeed there is a "true" value of $\text{BB}(n)$. If the assumed value of $\text{BB}(n)$ is indeed the true value, then you will get the true value for the Riemann hypothesis and so forth. Many mathematicians believe very strongly that arithmetic assertions of this kind do have a definite absolute truth value, whether or not they can be proved in ZF or ZFC+large cardinals or what have you. The independence phenomenon is seen as a consequence of the necessary weakness of our theories, rather than any difficulty for a robust notion of truth.

But meanwhile, according to the philosophical position known as arithmetic pluralism, there may be no definite fact of the matter for some arithmetic assertions. We already know how different models of ZFC and even ZFC plus the strongest large cardinal axioms we have can have different nonisomorphic arithmetic structures $\mathbb{N}$, with different arithmetic truths, and there seems to be no fully satisfactory argument that arithmetic truth is determinate. Perhaps the most convincing argument is the Dedekind categoricity argument, which shows that there is up to isomorphism a unique arithmetic structure satisfying Dedekind arithmetic, which includes the second-order induction axiom. But since this theory makes reference to second-order structure, essentially arbitrary sets of numbers, it would be basing the definiteness of our concept of the finite upon our concept of "arbitrary set of numbers". But how successful can that be? It would be essentially circular.

$\endgroup$
8
  • $\begingroup$ I have a two questions about the pluralistic viewpoint on arithmetic, if you don't mind. (1) To a pluralist, what might it mean to assert that a formal system is arithmetically sound? (2) Given that the definition of a formal proof itself uses $\mathbb N$, at least to some extent, can we still have a common understanding of what a formal proof is if we adopt the pluralist position? $\endgroup$
    – Joe Lamond
    Commented Jan 5 at 0:03
  • 1
    $\begingroup$ @Joe The arithmetic pluralist sees the metatheory also as pluralist. Every arithmetic context provides a metatheory for the theories and models that can be described there. In effect the object theory/metatheory distinction is replaced with an enormous hierarchy of metatheoretic contexts, each the object theory with respect to another metatheory. So just as there is no fact of the matter of arithmetic truth, there is similarly no fact of the matter about whether a given theory is arithmetically sound or consistent, and so forth. Different metatheories will sometimes disagree on these matters. $\endgroup$ Commented Jan 5 at 0:12
  • 2
    $\begingroup$ @TimothyChow You seem to want a precise mathematical account of how this works, but this is not a reasonable aim, since of course the different metatheories will all have different answers to those questions. The essence of the pluralist view is not to be found in giving a fully formal account of pluralism, but rather in recognizing that the philosophical justification of monism is much weaker than it is commonly taken to be and that we should expect in large part the situation of pluralist answers to these questions. $\endgroup$ Commented Jan 6 at 3:10
  • 2
    $\begingroup$ I don't see pluralism as saying that those statements "have no clear meaning", but rather as saying that the truth value of arithmetic statements depends on the metatheoretic context, and we already know how there can be many different contexts available. $\endgroup$ Commented Jan 6 at 13:54
  • 2
    $\begingroup$ @Jango The circularity arises when one attempts to use the second-order categoricity arguments to try to establish that there is a fact of the matter about the finitary question, such as the value of BB(694). It isn't about the lack of a proof system, but about whether there is even a fact of the matter regarding BB(694). Many mathematicians simply believe that there is, regardless of whether our proofs will find it. But why do we believe that there is a fact of the matter? Some mathematicians point to the categoricity result, and my argument is that this is circular. $\endgroup$ Commented Jan 22 at 19:12
13
$\begingroup$

I'm thinking I might be wrong either in a) my assumption that any ZF statement could be encoded as a Turing machine, or b) that maybe BB(n) itself is not determinable within ZF.

a) is indeed wrong. You can only encode finitely refutable statements (or their negation) into a Turing machine such that the halting behaviour of the Turing machine decides the statement. A simple example of what you cannot encode is Collatz' 3n+1 conjecture, that all sequences terminate at 1, since that has no finite refutation.

b) is correct. While ZFC can of course define the function BB(.), there exists an N such that it cannot prove the value of any BB(n) with n >= N. And Riebel proved that N <= 745.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .