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

181–190 of 232 posts

Re: BusyBeaver(6) Is Quite Large

#181

Post by drdeca »

cvoss wrote: post #134
drdeca wrote: post #69

Earlier quoted context omitted.

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 proble…

I don’t know it in a constructive sense, sure.

It’s still true though. I’m not wrong.

Re: BusyBeaver(6) Is Quite Large

#182

Post by thaumasiotes »

Scarblac wrote: post #160
thaumasiotes wrote: post #122

Earlier quoted context omitted.

> Most of these 'uncomputable' problems are uncomputable in the sense of the halting problem: you can write down an algorithm that should compute them, but it might never halt. That's the sense in which BB(x) is uncomputable: you won't know if you're done ever, because you can't distinguish a machine that never halts from one that just hasn't halted yet (since it has an infinite number of states, you can't just wait…

What happens if you take the larger of a and b and run all the Turing machines for that many steps?

What are a and b?

Re: BusyBeaver(6) Is Quite Large

#183

Post by raincole »

wat10000 wrote: post #177
raincole wrote: post #176

Earlier quoted context omitted.

> ultrafinitism I'm not sure what flavor of ultrafinitism you're referring here. If it's the "very big numbers, like TREE(3), are not natural numbers as they are far bigger than the number of atoms in this universe..." kind, then it has nothing to do with what this is about. > physical representation > your own eyes Non standard models of ZFC have nothing to do with our physical world. That's why no physicist or engi…

> ZFC doesn't prevent us from defining a non-standard model where Bar halts after a non-standard number of steps. But it does prevent you from defining a non-standard model where Bar halts after a finite number of steps. Since BB is finite by definition, the non-standard number of steps after which Bar halts cannot be BB(748). I’m pretty sure you and the other commenter have this mixed up. The fact that BB(748) is in…

> I’m pretty sure you and the other commenter have this mixed up.

We really don't.

> that BB(748) is independent of ZFC

> there are different models that have different values of BB(748)

> ZFC is insufficient to determine the value of BB(748)

These three statements are equivalent.

f(n)=X is independent of ZFC means there are different models of ZFC that have different values of f(n). It's a very trivial theorem[0]. If you don't like it, I can't convince you otherwise.

> that doesn’t actually change anything

Changing the model will not change how any machine works in our physical, mechanical universe. However, it does change the value of BB(748).

I understand your line of thinking: There is only one mechanical universe, which is the one where we exist. We can build Turing machines in this universe. BB(n) depends on Turning machines. Since there is only one single universe, there is only one single value of BB(n).

It's a perfectly fine mental model for most cases. This was exactly how I thought when the first time I heard about BB(n). But it's not the kind of math than Scott Aaronson et al. are doing.

Bar keeps running in our mechanical universe. But it can also halt in some non-standard number of steps. This weird, absurd-sounding proposition works because non-standard numbers simply don't map to anything in mechanical universe. They're purely abstract objects living in ZFC+~Con(ZFC).

[0]: Given f(n)=X is independent of ZFC. Which means f(n)=X and ~(f(n)=X) are both consistent relative to ZFC. Therefore, if there is any model of ZFC, there is a model M1 that entails ZFC+(f(n)=X), and a model M2 that entails ZFC+~(f(n)=X). The value of f(n) cannot be the same in M1 and M2.

Re: BusyBeaver(6) Is Quite Large

#184

Post by dloranc »

NooneAtAll3 wrote: post #22

If you want to learn about actual Busy Beaver results, I suggest reading https://www.sligocki.com/ instead Unlike Aaronson, he actually is on the forefront of Busy Beaver research, and is one of the people behind the https://bbchallenge.org website

Maybe Scott isn't at the forefront of the research by some standards, but I still consider him a prominent figure in the field. Independence of ZFC, Busy Baver Frontier paper, "Who Can Name the Bigger Number?" essay. He did a lot to popularise the topic and posed some interesting ideas or conjectures (Beeping Busy Beavers for example).

Re: BusyBeaver(6) Is Quite Large

#185

Post by wasabi991011 »

ajkjk wrote: post #43
dtech wrote: post #24

Earlier quoted context omitted.

I am also not an expert, but this does not sound right to me. Godel's incompleteness theorem shows that there are certain things that cannot be proven. Being independent of ZFC means that something is such a case. So BB(643) being independent of ZFC means that we cannot prove or disprove that a certain number is BB(643). Aka we don't have the math to know for certain.

Yeah, but the vexing part is "how can that be true for e.g. N=643 but not N=642"? What happens at whatever number it starts true at? Incidentally, Gödel's theorem eventually comes down to a halting-like argument as well (well, a diagonal argument). There is a presentation of it that is in like less than one page in terms of the halting problem---all of the Gödel-numbering stuff is essentially an antiquated proof. I r…

Wow that might be the best, most entertaining, and most elucidating academic article I've ever read. Thanks for sharing.

Re: BusyBeaver(6) Is Quite Large

#186

Post by bo1024 »

wat10000 wrote: post #175
Kranar wrote: post #146

Earlier quoted context omitted.

There is a lot of nuance you are skipping over that needs to be fully appreciated if you wish to understand this topic.

I can accept that there is a lot of nuance on the math side that I’m completely missing, but the Turing machine side is really straightforward. A Turing machine either never stops, or it stops after a finite number of steps. If it stops, the number of steps that it runs is a finite whole number, no different from “three” in its relationship to infinity or its theoretical ability to be written down. This doesn’t depen…

The point is that when it "never stops", there are models of ZFC in which the "infinity" number of steps it runs for isn't considered infinity by the model, it's a made-up "nonstandard" number that is smaller than infinity but larger than any integer. And that model considers that to be "halting", so that model says the TM halts.

Re: BusyBeaver(6) Is Quite Large

#187

Post by bo1024 »

bo1024 wrote: post #78
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.

Many replies don't seem to understand Godel and independence (and one that might is heavily downvoted). Cliff notes: * ZFC is a set of axioms. A "model" is a structure that respects the axioms. * By Godel, we know that ZFC proves a statement if and only if the statement is true in all models of ZFC. * Therefore, the statement "BB(748) is independent of ZFC" is the same as the statement "There are two different models…

I would edit my last line to say: weird models of numbers that don't match how we think "halts in finite steps" usually works.

Re: BusyBeaver(6) Is Quite Large

#188

Post by panpog »

Diggsey wrote: post #172
edanm wrote: post #163

Earlier quoted context omitted.

> BB(748) is by definition a finite number, and it has some value - we just don't know what it is. If an oracle told us the number, and we ran TM_ZFC_INC that many steps we would know for sure whether ZFC was consistent or not based on whether it terminated. This doesn't sound right to me. You can prove that ZFC is consistent. You could do it today, with or without the magic number, using a stronger axiom system. If…

> This doesn't sound right to me. Which bit? > You can prove that ZFC is consistent. You could do it today, with or without the magic number, using a stronger axiom system. Right but then just replace ZFC with that stronger system and you're back where you started - the point is that whatever the "strongest" system is that we've yet considered, BB(N) for sufficiently large N is stronger than that - and in all likelih…

There is only one integer k that we can actually write down (given much more paper than could fit in the universe) such that ZFC+ “BB(748)=k” is consistent. However, given that same k, ZFC+ “BB(748)≠k” is also consistent. ZFC+ “BB(748)≠k” has theorems that can be thought of as it being wrong about what “finite” means.

Re: BusyBeaver(6) Is Quite Large

#189

Post by red75prime »

raincole wrote: post #176
red75prime wrote: post #168

Earlier quoted context omitted.

> The point is not that Q exists in some physical sense in real life Ultrafinitism? If you'd run the Turing machine that performs BB(748) steps in a physical universe that admits it, you'd get a physical representation of BB(748). If you have a competing theory about which Turing machine computes BB(748), you can run them both alongside in this universe and see with your own eyes which one finishes first. I guess fro…

> ultrafinitism I'm not sure what flavor of ultrafinitism you're referring here. If it's the "very big numbers, like TREE(3), are not natural numbers as they are far bigger than the number of atoms in this universe..." kind, then it has nothing to do with what this is about. > physical representation > your own eyes Non standard models of ZFC have nothing to do with our physical world. That's why no physicist or engi…

> The "non-standard number of steps" is as nonsense as it sounds.

That is we can add a nonsensical axiom and get a consistent nonsensical theory that has nothing to do with actually running Turing machines (no matter in which physical or abstract universe they run). Er, OK, fine I guess.

A universally inapplicable theory.

No. I can't wrap my head around it. Successors for the tape state are defined for the initial segment of a non-standard natural numbers. How the proof of termination would even look like? Something non-constructive that doesn't allow to choose the machine among a finite number of the machines?

Re: BusyBeaver(6) Is Quite Large

#190

Post by fwip »

Nevermark wrote: post #70
lupire wrote: post #30

Earlier quoted context omitted.

Here's a more common example of this sort of comparison: In significant figures, 1.0 billion minus 1.0 million equals 1.0 billion.

True but this is a ratio. However many universes in question, there is a qualitative difference between that many empty universes (with 1 grain), and that many completely packed with grain. Ask anybody who lives in one!

At very large numbers, even ratios don't really matter.

For instance, if you personally owed $100 trillion, you wouldn't be much relieved by a court order that reduced your liability by 99%. Or, if you're looking at numbers in scientific notation, you don't much care about the difference between 2e40 and 5e40.

In this case, the ratio is around 10^200. An incomprehensibly vast number, to be sure.

But because tetration is the next operator up from exponentiation (the way exponents are from multiplication), any fixed divisor ceases to "matter" very quickly. The difference between 10^^10,000,000 and 10^^10,000,001 is (10^^10,000,000 to the tenth power), if my understanding is right.

There's basically no way to get it into comprehensible territory even with repeated divisions. 10^^1 = 10, 10^^2 = 10^10 (ten billion), and 10^^3 is 10^(10^10) = 10^10,000,000. Already, dividing by 10^200 isn't going to meaningfully affect your number (10^99,999,800).

10^^10,000,000 is that kind of incomprehensible growth that we just saw from 1 to 2 to 3, repeated 10 million times.

Post reply on HN