Hacker News Reader

Comment by tromp | Hacker News Reader

Previously discussed at https://news.ycombinator.com/item?id=36658506

Quoting from https://scottaaronson.blog/?p=7388 :

> Johannes Riebel, an undergraduate at the University of Augsburg in Germany, has produced a tour-de-force bachelor’s thesis that contains, among other things, the first careful writeup of Stefan O’Rear’s result from six years ago that the value of BB(748) is independent of the ZFC axioms of set theory. Regular readers might recall that O’Rear’s result substantially improved over the initial result by me and Adam Yedidia, which showed the value of BB(8000) independent of ZFC assuming the consistency of a stronger system. Along the way, Riebel even gets a tiny improvement, showing that BB(745) independent of ZFC.

View on HN

BB(748) - BB(745) is probably the largest value that anyone has ever described as "tiny" :-)

I would assume tiny refers to three.

It's actually really hard to come up with an interesting lower bound that value.

IIRC no one has proven that BB(n) + 1 < BB(n + 1) for large 2

Hm, is there some way to “concatenate” Turing machines which would let you prove something like

BB(n) + BB(m) <= BB(n+m+c)

for some fixed c independent of n and m?

It seems very unlikely: the full joint state space has n*m states, so you're throwing away almost everything for large n and m.

You can, but BB(1) = 1 so that doesn't help with BB(n + 1) > BB(n) + 1

Take the machine for BB(n) with non-end states {1,2,3,…n} and end state E.

In its program, change every transition that goes to state E to go to a new state n+1 instead.

Add transitions “when in state n+1 and on a 1, move right” and “when in state n+1 and on a 0, write a 1 and stop”.

Doesn’t that give you a Turing machine with n+1 states that stops after writing one more 1 than BB(n) writes, thus proving that BB(n+1) is at least one more than BB(n+1)?

yeah, that shows BB(n+1) >= BB(n) + 1, but if you want to make the inequality strict you need to find a way to add another step.

Oops. Reversing your “BB(n) + 1 < BB(n + 1)” turned out to be too difficult for me today. Thanks for the reply.

If BB(745) is independent of ZFC can it even be called a value? It seems like you could easily run into paradoxes if you treated it like just any other value.

just because it's not provably constructable from axioms it doesn't mean it's not just a finite number. that's the really mindbreaking part in this. it's really just like 5. except 5 is provably constructable, describable, nameable. (most numbers are not, just as - for example - angle trisection is impossible with just a straightedge and a compass )

https://en.wikipedia.org/wiki/Set-theoretic_definition_of_na...

http://uu.diva-portal.org/smash/get/diva2:1715729/FULLTEXT01...

There is no paradox and yes, BB(745) is a specific integer, so it's nothing more than a sequence of finite digits.

The fact BB(745) can't be constructed using ZFC only means that there is at least one Turing machine among the set of all 745 state Turing machines that runs forever, but can't be proven to run forever using the axioms of ZFC. You'd need a more powerful axiomatic system to prove that this Turing machine actually runs forever.

This does not imply any kind of paradox or any kind of issue whatsoever in fact. It just means that ZFC is not powerful enough to prove that certain 745 state Turing Machines run forever.

> The fact BB(745) can't be constructed using ZFC only means that [...]

...so what?

The claim wasn't that BB(745) can't be constructed using ZFC, or that it's not computable.

The claim was that its value is independent of ZFC, that the ZFC axioms do not make any logical implication about the value. This necessarily means that there are multiple possible values; if there were only one value, that value would be logically implied by ZFC regardless of whether it was provable in ZFC.

I should also note that these two observations are not compatible with each other:

> BB(745) is a specific integer, so it's nothing more than a sequence of finite digits

> BB(745) can't be constructed using ZFC

All finite digit sequences can be constructed.

>This necessarily means that there are multiple possible values; if there were only one value, that value would be logically implied by ZFC regardless of whether it was provable in ZFC.

This is a false statement. The fact that BB(745) can't be constructed using ZFC does not mean that it has multiple values. All it means is that there is at least one Turing Machine that never halts but can't be proven to run forever using ZFC, that is it.

BB(745) is one specific integer, there is nothing really special about ZFC in this sense, it's just one axiomatic system that happens to be very useful as the foundation of most of the mathematics that is studied, but one could just as easily work with a different axiomatic system instead.

There are values of BB(n) that have no construction using Peano arithmetic but do have a construction in ZF, and there are values of BB(n) that do not have a construction in ZF but have one in ZFC, and there are values of BB(n) that do not have a construction in ZFC but do have one in ZFC + Inaccessible Cardinal Axiom, so on so forth.

ZFC does not have some kind of authoritative status in the universe of mathematics; it's possible that an alien race is doing mathematics using a far more powerful axiomatic system in which case BB(745) is constructible but BB(7450) is not.

>All finite digit sequences can be constructed.

A construction is a proof that provides a means of calculating a given value [1]. The set of all theorems that can be enumerated in ZFC do not contain a construction for the value of BB(745).

[1] https://en.wikipedia.org/wiki/Constructive_proof

> A construction is a proof that provides a means of calculating a given value [1]. The set of all theorems that can be enumerated in ZFC do not contain a construction for the value of BB(745).

Of course they do. They just don't contain a proof that that value has the relevant properties that define the Busy Beaver sequence.

There's a big difference between constructing the value 107 and proving that that same value satisfies a given set of constraints.

We'll agree to disagree on this point then. My stance is you're using the word construction in a more layman like manner whereas I am using it in the more formal sense. It's not a particularly big deal either way.

Think of it this way:

Is it possible to construct the value 2?

Is it possible to construct 3?

Is it possible to construct 4?

[...]

The answer to all of these questions is obviously "yes".

Is BB(745) one of those constructible numbers? This is harder to answer, except that you have firmly taken the position that it is. Hence it must be constructible.

> The claim was that its value is independent of ZFC, that the ZFC axioms do not make any logical implication about the value.

This is not what "independent from ZFC" means: e.g. ZFC easily proves that BB(745) is larger than 10000. It even proves that BB(745) is a sum of at most six primes.

Independence here just means that for any fixed (meta-theoretic) numeral n, ZFC cannot prove that BB(745) is exactly n -- unless ZFC is inconsistent, a possibility we can't really rule out.

This implies that ZFC (again, if it's consistent) does not suffice to establish an explicit upper bound BB(745) < n either. But that's very far from ZFC not making _any_ logical implications about the value.

> This is not what "independent from ZFC" means: e.g. ZFC easily proves that BB(745) is larger than 10000. It even proves that BB(745) is a sum of at most six primes.

I would respond to the first example by noting that you're correct, but I am limited to using a finite number of words when I talk, and to the second one by not considering it a contradiction of what I said. (Though I'm making the assumption here that you're applying a theorem that holds for every integer to BB(745).)

> Independence here just means that for any fixed (meta-theoretic) numeral n, ZFC cannot prove that BB(745) is exactly n -- unless ZFC is inconsistent, a possibility we can't really rule out.

My understanding was that the independence of the continuum hypothesis takes the following form:

(1) If ZFC is consistent, then ZFC ∪ {CH} is also consistent.

(2) If ZFC is consistent, then ZFC ∪ {¬CH} is also consistent.

This is quite explicit that independence allows for the selection of (one of) multiple values. It happens to be an exact match to what is given on Wikipedia right now:

> The answer to this problem is independent of ZFC, so that either the continuum hypothesis or its negation can be added as an axiom to ZFC set theory, with the resulting theory being consistent if and only if ZFC is consistent.

You appear to be saying that a proposition that is entailed by ZFC, but not proven by ZFC, is nevertheless independent of ZFC, but I don't think that can be right?

"The proposition CH is independent of ZFC" and "the value of BB(745) is independent of ZFC" are two different statements.

A proposition P is independent of ZFC if it's not possible to prove P and not possible to prove its negation ~P either.

If P(-) is a unary predicate, we say that the value of an integer v with definition P(-) is independent of ZFC if ZFC proves that there is a unique integer v such that P(v), but fails to prove that P(v) implies v=n for any specific (meta-theoretic) numeral n. This means that no propositions of the form v=n are provable in ZFC. It does not imply that all propositions of the form v=n (v≠n) are independent of ZFC!

Basically, two different (but not unrelated) senses of independent.

Thanks!

> This means that no propositions of the form v=n are provable in ZFC. It does not imply that all propositions of the form v=n (v≠n) are independent of ZFC!

Doesn't it mean that there are at least two such propositions, v=n_1 and v=n_2, which are both independent of ZFC?

Assume there is a fixed unique integer i such that i = BB(745).

We know that v=n is unprovable for all n, including i.

We know that v≠i is unprovable because (a) it is a false statement; and (b) we assumed ZFC was consistent.

All that remains to be shown is that there is some other integer j for which v≠j is unprovable. This must be the case: if v≠j were provable for all integers j not equal to i, that would constitute a proof that v=i,† and v=i is unprovable.

So v=i and v=j are both simple truth-valued propositions that are independent of ZFC.

Why are i and j not equally valid choices for the value of v?

† because "ZFC proves that there is a unique integer v such that P(v)"

Sure you are right there would be at least two propositions with different values of n_1 and n_2 that are independent of ZFC. But this does not mean that BB(745) has two values that are actually true, it just means that ZFC is unable to determine which of those two propositions is correct and which one is incorrect.

In fact, from outside of ZFC, it's trivial to see that the correct value would be whichever of the two standard integers is larger, if n_1 is a standard integer and is greater than n_2 then BB(745) would be n_1, otherwise it would be n_2. If there are X such propositions involving standard integers that are independent of ZFC then the actual value of BB(745) would be max(n_1, n_2, ..., n_X).

Of course ZFC can't prove this but that doesn't mean that the real value is unknowable or that the actual value is ambiguous or could take on different values. All it means is that ZFC does not have a sufficiently powerful axiom to prove which of the two values is the true value.

Furthermore because the busy beaver function is co-recursively enumerable, then it follows that any axiomatic system that was able to prove that BB(745) is a different standard integer from max(n_1, n_2, ..., n_X) would be inconsistent, even though ZFC would be unable to prove its inconsistency.

As I said before, ZFC holds no special status or authority on the nature of the busy beaver function so just because ZFC is not powerful enough to discriminate between a set of propositions about what the value of BB(745) is does not mean that BB(745) can actually take on multiple values depending on your interpretation.

> In fact, from outside of ZFC, it's trivial to see that the correct value would be whichever of the two standard integers is larger, if n_1 is a standard integer and is greater than n_2 then BB(745) would be n_1, otherwise it would be n_2. If there are X such propositions involving standard integers that are independent of ZFC then the actual value of BB(745) would be max(n_1, n_2, ..., n_X).

This doesn't sound trivial to me. It's easy to see that the largest such value is an upper bound on BB(745), but even that isn't worth much. There could be an infinite number of such values. (In which case your definition of which value was correct would contradict the earlier statement that ZFC proves a unique value of BB(745) exists!)

Also...

> In fact, from outside of ZFC, it's trivial to see that the correct value would be whichever of the two standard integers is larger

What part of your analysis takes place outside of ZFC? This looks to me like you're about to propose that ZFC contains a proof of the value of BB(745), contradicting the stipulation that it doesn't.

-----

In particular, let's say that we have two values, n_1 < n_2, for which BB(745)≠n [either n] cannot be proved.

The definition of the busy beaver sequence tells us that BB(745) is the maximum number of steps a 745-state Turing machine can take without halting, if it's ever going to halt at all.

Describing a 745-state Turing machine which halts after k > n_1 steps would prove BB(745)≠n_1, and therefore cannot be done. But unless we believe that there are Turing machines which ZFC is not able to describe, this would also mean that no such Turing machine exists (since existence would imply description, and description would prove the unprovable). That would make n_1 the "true" value.

But now we have the problem that we just proved v=n_1, which also can't be done.

Did I make a mistake somewhere? Where did we leave ZFC?

>It's easy to see that the largest such value is an upper bound on BB(745), but even that isn't worth much.

Having an upper bound on the value of a BB(N) is all you need to solve BB(N). Why? Because if you have an upper bound called U, then you know that any Turing Machine that runs for more than U steps will run forever. So an upper bound is as good as a solution.

>There could be an infinite number of such values.

No there can't be an infinite number of these because the number of 745 state Turing Machines is finite and each Turing Machine represents one possible value for what BB(N) can be. The number of possible binary Turing Machines with N states is 6 * (N + 1) ^ (3 * N).

As for the rest of your post, I think to address it we should step back from busy beavers and just focus on one specific aspect of it that is easier to reason about.

Let's say there's some Turing Machine H, and whether H halts is independent of ZFC, that is ZFC is unable to prove whether H halts or runs forever. Does this mean that in fact H can both halt and not halt depending on our interpretation? Is it possible that H both halts and does not halt? Can we as humans just decide to choose one axiomatic system where H halts, or we can decide to choose another axiomatic system where H does not halt and both systems are perfectly valid and legitimate?

Of course not. If whether H halts or runs forever is independent of ZFC, then in fact H never halts. It's not a matter of personal choice, or a matter of interpretation, or something we can just arbitrarily choose, H simply runs forever.

We can tell from outside of ZFC that H must run forever, even though from inside of ZFC the proposition is unprovable. That does not mean that ZFC is able to prove that H halts; what it means is that ZFC is unable to precisely define what a natural number is and that from inside of ZFC there are two possible systems of natural numbers:

In one system of natural numbers H runs forever, which is the system of natural numbers that corresponds to the actual truth. This system of natural numbers is what we call the standard model of arithmetic and is the intended interpretation of the natural numbers [1].

In another system of natural numbers, the nonstandard model of arithmetic, H halts after X steps where X is a nonstandard natural number [2]. You can think of a nonstandard natural number as a number that is larger than any standard natural number, for example imagine a whole number with an infinite number of digits. Now we know that a natural number is only supposed to have a finite number of digits, but ZFC is not powerful enough to define natural numbers this way, so it can not eliminate every model of natural numbers that have infinite digits and in one such model H does halt.

In fact, no consistent first order system is powerful enough to define natural numbers in such a way that they only have a finite number of digits, every single first order system will have some model of natural numbers that have an infinite number of digits.

So no, the fact that HALT(H) is independent of ZFC does not mean that we can just decide to pick an axiomatic system where H halts or one where it does not halt and both are valid choices, because in the system where H halts we are no longer working with the actual natural numbers. It's only in the axiomatic system where H never halts that we get to work with the natural numbers.

Given these concepts, you can now apply them to better understand how the busy beaver function can only have one single value. Yes there are propositions of ZFC where BB(745) = n1, and BB(745) = n2, and both of these propositions are independent of ZFC. No, that does not mean that BB(745) can actually be either n1 or n2 and the choice is a matter of preference. Only one axiomatic system represents the actual natural numbers, and the other ones represent the nonstandard natural numbers whose values can be infinitely large and have infinitely many digits.

[1] https://en.wikipedia.org/wiki/Interpretation_(logic)#Intende...

[2] https://en.wikipedia.org/wiki/Non-standard_model_of_arithmet...

I think this is wrong. Because we can run the Turing machines for max(n1, n2) steps. If a machine halts after that many steps, then it rules out the lesser value. If none of them halts after that many steps it rules out the greater value.

So our only uncertainty is between one specific number, and some unspecific bigger number that forever recedes into the distance as we try to approach it.

You propose that the issue is some pesky non-standard numbers that are bigger than any other number. But I'm thinking the issue is rather the for-all symbol.

Like from the outside of the theory we can see that we can prove a certain property for 1, for 2, for 3 etc, in fact we can prove this property for any number. But inside the theory we cannot prove that for-all n the property holds. So there is a divergence between what we want for-all to mean and what it actually ends up meaning?

Or using the there-exists perspective, if there exists an actual object inside a theory that satisfies a property P, then there-exists x such that P(x) will be true. But it can also be true without such an actual object existing.

The more I think about this the more I start to doubt it..

No at all, you are absolutely correct and what you describe is known as omega-consistency!

https://en.wikipedia.org/wiki/%CE%A9-consistent_theory

However, your description is just another way of saying what I'm saying about nonstandard numbers. From outside of the theory you can prove P(1), P(2), P(n) for any N that is an actual natural number, but from inside of the theory you can't do that. Why not? Because from inside of the theory there is a model that is completely consistent with Peano arithmetic but contains some object E that is greater than any standard natural number. The theory can not eliminate the existence of this E and in fact it's possible to construct an E such that P(E) is false.

> All finite digit sequences can be constructed.

You can construct the particular natural number that it is, obviously. Constructing BB(745) means providing that number and a proof that it's the right one.

BB(745) is some specific number N. Numbers cannot be independent of ZFC.

Only boolean valued formulas can be.

In this case, the relevant formula F expresses that all 745 state TMs that do not halt within N steps, will never halt. Assuming consistency of ZFC, formula F is true but unprovable in ZFC, and thus independent.

Another formula G expresses that some specific 745 state TM halts in exactly N steps. Formula G is true and provable in ZFC. F and G together imply that BB(745) = N.

It's hard to comprehend just how big that number is. It may indeed be among the largest numbers ever conceived, and we'd have no clue. I wouldn't be surprised if it is larger the number of possible permutations of all particles in the observable universe, for instance. I'd be more surprised if it was less than that.

Graham's number used to be the largest number ever used in a proof, but BB(745) is much larger—Graham's number has been proven to be smaller than BB(16)[1] (although I don't know how carefully the proof has been checked).

[1] https://www.sligocki.com/2022/07/11/bb-16-graham.html

A number much larger than Graham's can be represented in less than 64 bits [1], using a functional flavored Busy Beaver function [2].

[1] https://googology.fandom.com/wiki/User_blog:JohnTromp/The_la...

[2] https://oeis.org/A333479

A commonly quoted number for the number of particles in the observable universe is 10^80 give or take a few orders of magnitude an they have very roughly 10^10^10^2 permutations if you consider all particles distinguishable. The best known lower bound for BB(6, 2) seems to be 10^10^10^10^10^10^10^10^10^10^10^10^10^10^10 which is more like the number of permutations of permutations of permutations of permutations of permutations of permutations of permutations of permutations of permutations of permutations of permutations of permutations of the particles in the universe. Trying to comprehend or compare the size of BB(745) is just futile. Here [1] is a well known attempt to convey the size of 52!, the number of permutations of a deck of cards.

[1] https://www.youtube.com/watch?v=ObiqJzfyACM&t=947s

Right, but we are talking about the difference between two busy beavers here.

Sure, but BB(n) - BB(n - 1) ≈ BB(n) because the function grows so quickly that BB(n - 1) is essentially zero compared to BB(n). Even for factorials the difference between n! and (n - 1)! is essentially n! [1] and the busy beaver function grows much faster.

BB(748) and BB(748) - BB(745) will have the same number of digits and if you compare them left to right, they will agree for way more digits than there are permutations of particles in the observable way before you find the first difference.

[1] (1 - 1/n) n! to be precise.

I agree intuitively, but do you have a formal proof of such? This thread seems to struggle to find one: https://news.ycombinator.com/item?id=38121507

First a correction, I got the lower bound for BB(6, 2) wrong, what I quoted is the runtime, the number of ones is only 10^18267 which is tiny compared to the number of permutations of the particles in the observable universe.

I think proofing a good estimate of the difference will be hard to impossible. We have lower bounds but by definition we can not have a computable upper bound, at least not for arbitrary n. But we need both because we would have to find the difference between the lower bound for BB(748) and the upper bound for BB(745) in order to get an lower bound on the difference between the two.

So yes, in principle the difference BB(748) - BB(745) could be small, but given that the difference BB(n) - BB(n - 1) itself grows faster than any computable function [1] that would be quite surprising. Which is of course a terrible argument.

For BB(748) we have three additional states that we can use to modify the machine for BB(745). And it does not seem completely implausible that we could kind of stretch one state transition, instead of going from state A to state B writing one 1 we go through one of the additional states in between and write another one, writing twice as many 1s as before.

But finding a general construction that provably works for all relevant Turing machines is probably at least not trivial and might as well be impossible. But if one could show this, then we would get something like BB(748) >= 2 * BB(745) and therefore BB(748) - BB(745) >= BB(745). And this we could then combine with a lower bound for BB(745).

[1] If it would not, we could have a computable upper bound for the differences BB(n) - BB(n - 1) which we could turn into a computable upper bound for BB(n) by just summing the bound for the differences up to n.

Just because the difference between values is not computable does not mean that it grows faster than any computable function. The sequence iBB(n) = -1/BB(n) also has incomputable deltas, but it grows more slowly than any increasing computable function.

That’s not to say the entries aren’t large, I agree that they almost certainly are, but rather that the derivative is interesting in it’s own right, and making interesting statements about it is more difficult yet fun than guessing.

We know that asymptotically BB(n) > f(n) for every computable function f. Assume there is a computable upper bound d for the difference so that BB(n) - BB(n - 1) <= d(n). But now note that this gives you BB(n) <= d(1) + d(2) + ... + d(n) and that the right hand side is computable by assumption but that this contradicts the fact that there is no computable upper bound for BB(n). Therefore our assumption was incorrect, there is no computable upper bound for the differences, hence the differences themselves grow faster than any computable function.

The assumption was indeed incorrect, but it was that there exists a computable upper bound d(n) for all n.

My claim is that there may be a computable upper bound for some n. For instance it might be that particular d(n) values represent local maxima wherein a particular "mode" of computation is "unlocked" that uncomputably increases BB(n), leaving BB(n+ε) only computably greater for small natural numbers ε.

Sure, that could potentially be the case. But as said before, I would argue that it does not seem unreasonable to me that you generally can increase BB(n) to twice BB(n) with one or a few additional states by slightly tweaking the machine. And that would be enough to get BB(n) - BB(n - 1) >= BB(n) which together with the size of BB(n) prevents really small differences. But I of course see that proving that you can increase the length of the output of any busy beaver by some constant using some number of additional states is far from trivial.

That must of course be BB(n) - BB(n - 1) >= BB(n - 1). Also I have to retract the correction from a few comments ago, the currently best lower bound for BB(6, 2) is indeed 10 ⇈ 15, I looked at an outdated source when writing the correction.

Reply on news.ycombinator.com