Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

BusyBeaver(6) Is Quite Large

scottaaronson.blog

Post reply on HN
Print view View original

131–140 of 232 posts

Re: BusyBeaver(6) Is Quite Large

#131

Post by woopsn »

tromp wrote: post #57
Scarblac wrote: post #4

It boggles my mind that a number (an uncomputable number, granted) like BB(748) can be "independent of ZFC". It feels like a category error or something.

What makes BB(748) independent of ZFC is not its value, but the fact that one of the 748-state machines (call it TM_ZFC_INC) looks for an inconsistency (proof of FALSE) in ZFC and only halts upon finding one. Thus, any proof that BB(748) = N must either show that TM_ZF_INC halts within N steps or never halts. By Gödel's famous results, neither of those cases is possible if ZFC is assumed to be consistent.

Does the fact that BB(k)=N is provable up to some k < 748 mean that all halting problems for machines with k states are answered by a proof in ZFC?

Re: BusyBeaver(6) Is Quite Large

#132

Post by adgjlsfhk1 »

pinkmuffinere wrote: post #130
adgjlsfhk1 wrote: post #125

Earlier quoted context omitted.

one of the things that does come out of BB is that BB(n)^2>>BB(n+c) for some very small constant c (I would be surprised if c>2)

Sure, but the example I'm providing is just meant to illustrate that BB(n) is not greater than arbitrary f(n). I'm not trying to provide the biggest number, I'm trying to illustrate that the sketched-out proof is incorrect. If you want me to provide a bigger number, I suppose another easy example is to define f(n) = BB(BB(n)). Edit: Oh sorry, I see I misread the direction of your greater than signs. Leaving comments…

oops, my greater than signs are in the wrong direction. specifically, for any computable function f, there exists some constant c such that f(BB(n))<<BB(n+c)

Re: BusyBeaver(6) Is Quite Large

#133

Post by ryandrake »

Bjartr wrote: post #128
ryandrake wrote: post #123

> For those tuning in from home, here BB(6) is the 6th Busy Beaver number, i.e. the maximum number of steps that a 6-state Turing machine with a {0,1} alphanet can take before halting, when run on an initially all-0 input tape. Oh! Of course! That sure clears things up for this non-expert. This is clearly a hardcore blog for people who have been doing this kind of research for decades. Kind of awesome to stumble upon…

That should be enough for someone with an undergrad CS education to at least get a sense of what's going on if they haven't encountered the busy beaver problem before. Is it niche jargon, absolutely, but to say it's only accessible to people who have put in decades is selling yourself short.

Hmm, interesting. It’s been 30 years since my engineering degree (not CS) and I’d have to look up what a Turing machine is. I think I remember one professor briefly mentioned it as “This is something the CS majors care deeply about but nobody else in the industry does.” Where I was, the CS degree was essentially a math degree dressed up in a hoodie.

Re: BusyBeaver(6) Is Quite Large

#134

Post by cvoss »

drdeca wrote: post #69
Scarblac wrote: post #4

It boggles my mind that a number (an uncomputable number, granted) like BB(748) can be "independent of ZFC". It feels like a category error or something.

No individual number is uncomputable. There’s no pair of a number and proof in ZFC that [that number] is the value of BB(748). And, so, there’s no program which ZFC proves to output the value of BB(748). There is a program that outputs BB(748) though, just like for any other number.

I think your mistake is your claim that BB(748) is a natural number. For you to know that, you would necessarily have to know an upper bound for the number of steps it takes for the BB-748 machine (whichever machine it is) to halt. But you definitely don't know that.

Related: It's incorrect to claim that each machine either halts or doesn't halt. To know that that dichotomy holds would require having a halting problem algorithm.

Re: BusyBeaver(6) Is Quite Large

#135

Post by gpm »

pinkmuffinere wrote: post #124
gpm wrote: post #96

Earlier quoted context omitted.

I can't pretend to be an expert, but I'll argue BB(7) is probably larger than Graham's number. BB has to grow faster than any computable sequence. What exactly that means concretely for BB(7) is... nothing other than handwaving... but it sort of means it needs to walk up the "operator strength" ladder very quickly... it eventually needs to grow faster than any computable operator we define (including, for example, up…

Apologies if this feels adversarial, but I think your informal proof has an error, and I think I can explain it! Your proof rests primarily on this assertion: > BB has to grow faster than any computable sequence. This is almost true! BB(n) has to grow faster than any computable sequence _defined by an n-state Turing machine_. That last part is really important. (Note that my restatement is probably incorrect too, it…

Math's a cooperative endeavor, I want to know if I'm wrong!

I'm not sure I understand the distinction you're trying to make though, and I'm not sure it's right...

The argument that BB has to grow faster than any computable sequence is that if we have a computable f(n) where for all n f(n) > BB(n) then we can solve the halting problem by simulating turing machines of size n for f(n) steps and checking if they halt. Even if we can't prove f(n) > BB(n) the mere existence of this f would mean we could solve the halting problem (even though we couldn't prove we had done so).

I agree my "proof" (intuition really) rests on that assertion.

> As an easy example, consider f(n) = BB(n)^2.

This, like BB(n), isn't computable?

Re: BusyBeaver(6) Is Quite Large

#136

Post by Bjartr »

ryandrake wrote: post #133
Bjartr wrote: post #128

Earlier quoted context omitted.

That should be enough for someone with an undergrad CS education to at least get a sense of what's going on if they haven't encountered the busy beaver problem before. Is it niche jargon, absolutely, but to say it's only accessible to people who have put in decades is selling yourself short.

Hmm, interesting. It’s been 30 years since my engineering degree (not CS) and I’d have to look up what a Turing machine is. I think I remember one professor briefly mentioned it as “This is something the CS majors care deeply about but nobody else in the industry does.” Where I was, the CS degree was essentially a math degree dressed up in a hoodie.

> This is something the CS majors care deeply about but nobody else in the industry does

Correct, the industry cares a lot more about Software Engineering than Computer Science.

> CS degree was essentially a math degree dressed up in a hoodie.

To a first approximation, that's what it's supposed to be. CS is a field of mathematics. It's not a trade school course.

Re: BusyBeaver(6) Is Quite Large

#137

Post by cevi »

czbot wrote: post #100
cevi wrote: post #89

Earlier quoted context omitted.

Unfortunately no, ZFC isn't good enough to capture arithmetical truth. The problem is that there are nonstandard models of ZFC where every single model of second-order PA within is itself nonstandard. There are even models of ZFC where a certain specific computer program, known as the "universal algorithm" [1], solves the halting problem for all standard Turing machines. https://jdh.hamkins.org/the-universal-algorith…

ZFC allows models of second order PA and proves that those models are all isomorphic. Within each model of ZFC there is no such thing as a nonstandard model of second order PA. One can only think it is nonstandard by looking from outside the model, no? What theorem of second order PA is ZFC unable to prove? This is similar to how there are countable models of ZFC but those models think of themselves as uncountable. T…

The consistency of ZFC is (presumably) a theorem of second order PA, and ZFC is unable to prove it (unless ZFC is inconsistent).

Re: BusyBeaver(6) Is Quite Large

#138

Post by wat10000 »

bo1024 wrote: post #126
wat10000 wrote: post #121

Earlier quoted context omitted.

How is that possible? That implies there’s at least one specific program whose execution changes based on the ZFC model. The rules of program execution are so simple, it doesn’t make sense that they’d change based on anything like that.

Because what it means to "halt in finite time" has different meanings in different models, because time is measured with different numbers.

I don’t get it. Let’s say that BB(748) is 10,000. (I realize the true number is somewhat larger, this is just an example that doesn’t change the argument.) That means there’s one or more Turing machines of that size which run for that many steps. All of the others either run for fewer, or never stop.

Running for fewer steps is extremely well defined and I don’t imagine that enters into this.

That means there’s issue is “never stop”? That also seems pretty well defined to me. For BB(748) to vary based on your model, if the machines that run for fewer steps don’t change, then that means one of the machines that never stops in one model will stop in another. Or the BB winner for our model will never stop in another model.

How can changing your model make it so a specific Turing machine goes from stopping after 10,000 steps to never stopping, or from never stopping to stopping after 11,000 steps?

Re: BusyBeaver(6) Is Quite Large

#139

Post by Kranar »

wat10000 wrote: post #138
bo1024 wrote: post #126

Earlier quoted context omitted.

Because what it means to "halt in finite time" has different meanings in different models, because time is measured with different numbers.

I don’t get it. Let’s say that BB(748) is 10,000. (I realize the true number is somewhat larger, this is just an example that doesn’t change the argument.) That means there’s one or more Turing machines of that size which run for that many steps. All of the others either run for fewer, or never stop. Running for fewer steps is extremely well defined and I don’t imagine that enters into this. That means there’s issue…

Yes the issue has to do with "never stops". One of the machines that never stops in one model will stop in another model.

So in one model a Turing Machine called R never stops. In another model R stops after Q steps. But here's the issue... Q isn't an actual natural number, what it is is some mathematical object that satisfies all of the properties of a natural number in ZFC, but is not an actual natural number. What it actually is is some infinitely large object that satisfies all of the Peano axioms of what a natural number is as well as satisfies the following set of rules:

   Q > 0
   Q > 1
   Q > 2
   Q > 3
   ...
Q is basically some infinitely large construct that from within the model appears to be finite, but from outside of the model is not finite.

So within this model, the Turing machine R halts after Q steps, and since from within the model Q is finite then from within this model BB(748) is at least equal to Q.

If BB(748) is actually 10,000, then we can add this as an axiom to ZFC to get a new formal theory ZFC + "BB(748) = 10000".

In this new theory the previous structure that contained Q as an element will not satisfy the definition of a natural number, so we don't have to worry about Q anymore... however, there will exist some number T > 748 where BB(T) is independent of our new theory. For BB(T), there will exist some other model that has its own Q* which satisfies all of our axioms including the axiom that BB(748) = 10000, but also that

    Q* > 0
    Q* > 1
    Q* > 2
    Q* > 3
    ...
And rinse and repeat...

Re: BusyBeaver(6) Is Quite Large

#140

Post by LegionMammal978 »

phs wrote: post #67

So what is the richest logic whose proofs can be enumerated with only a five state TM?

While that question depends on what you count as an 'enumeration', there's the related question of "What's the richest logic that cannot prove the halting status of all 5-state TMs?" That is, what's the richest logic that some 5-state TM's halting status is independent of?

I've pondered that version of the question a bit, but I couldn't get very far due to my lack of expertise in first-order logic. What I do know is that Skelet #17 [0] is one of the toughest machines to prove non-halting on a mathematical level [1], so any theory sufficient to prove that Skelet #17 doesn't halt is likely sufficient to decide the rest of the 5-state machines.

[0] https://bbchallenge.org/1RB---_0LC1RE_0LD1LC_1RA1LB_0RB0RA

[1] https://arxiv.org/abs/2407.02426

Post reply on HN