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

51–60 of 232 posts

Re: BusyBeaver(6) Is Quite Large

#51

Post by Dylan16807 »

falcor84 wrote: post #49
lupire wrote: post #32

Earlier quoted context omitted.

Only if you believe that a number you can't count is a number. You can believe that, but it's a leap.

Couldn't you make the same argument for sqrt(2), or better yet for zero [0]? [0] https://en.wikipedia.org/wiki/Zero:_The_Biography_of_a_Dange...

For sqrt(2) I can tell you the order of magnitude and output as many digits as you want. I think that's plenty specific for this use case.

For zero I can not only do that, I can also count to it if you let me count both up and down, which seems like a very simple ask.

Re: BusyBeaver(6) Is Quite Large

#52

Post by azan_ »

Xcelerate wrote: post #40
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.

It boggles my mind that we ever thought a small amount of text that fits comfortably on a napkin (the axioms of ZFC) would ever be “good enough” to capture the arithmetic truths or approximate those aspects of physical reality that are primarily relevant to the endeavors of humanity. That the behavior of a six state Turing machine might be unpredictable via a few lines of text does not surprise me in the slightest. A…

> As soon as Gödel published his first incompleteness theorem, I would have thought the entire field of mathematics would have gone full throttle on trying to find more axioms.

But why? Gödel's theorem does not depend on number of axioms but on them being recursively enumerable.

Re: BusyBeaver(6) Is Quite Large

#53

Post by alexeldeib »

refulgentis wrote: post #45
lupire wrote: post #35

Earlier quoted context omitted.

https://www.sligocki.com/ hasn't posted since April, and the very first link on that blog is a link to... Scott Aaronson.

Could I bother you for some more info? I spent 5 minutes trying to verify any link in the post above links to Scott Aaronson, or mentions him, and found nothing. :\ (both the siglocki, and when I found nothing there, the busy beaver site)

The "first" link (after the home button) on bbchallenge is the header bar link to https://bbchallenge.org/story which cites Aaronson in the first sentence (double first!). I would not describe it like OP for someone trying to find the actual link ;)

"One Collatz Coincidence", the 2nd story on the blog, also mentions Aaronson

Re: BusyBeaver(6) Is Quite Large

#54

Post by tialaramex »

griffzhowl wrote: post #29
sedatk wrote: post #17

> Also, the left-superscript means tetration, or iterated exponentiation: for example, 1510 means 10 to the 10 to the 10 and so on 15 times. I thought it was a typo. First time I encounter tetration.

Continuing the theme of iteration: it was the first time I encountered pentation

One of the reasons I like the use of the number line in schools is that on the line it's more obvious when you're shown addition and multiplication and then later exponeniation that this is a pattern. With the number line, two natural questions arise and, hopefully by the time you're taught exponentiation the Math teacher knows enough math to confidently affirm the answer to both. Yes, it keeps going like this forever, that's called Hyperoperation. And yes, we did (probably) skip one, it's known as Successor-of and you were probably not explicitly shown this operator but it's the near end of that infinite succession.

When arithmetic is introduced just as a way to, for example, count money, it's more directly practical in the moment, but you're not seeing the larger pattern.

Re: BusyBeaver(6) Is Quite Large

#55

Post by bmacho »

Straw wrote: post #13
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.

The category error is in thinking that BB(748) is in fact, a number. It's merely a mathematical concept.

Let S be a statement. S is called semidecidible (also: Turing recognizable, most commonly "recursively enumerable", abbreviated as "r.e.", but I hate that one) if there is a Turing machine that halts if and only if S is true.

With this definition, we can say that "ZFC is inconsistent" is semidecidible: you run a program that searches for a contradiction.

The question BB(748) =/= 1000 is similarly semidecidable. You can run a program that will rule out 1000 if it is not BB(748).

So they are in the same "category", at least regarding their undecidability.

Also, if you turn "ZFC is consistent" into a number: {1 if ZFC is consistent; 0 if ZFC is inconsistent}, you will see, that BB(748) is not very much different, both are defined (well, equivalently) using the halting of Turing machines, or, the result of an infinite search.

Re: BusyBeaver(6) Is Quite Large

#56

Post by tliltocatl »

azan_ wrote: post #52
Xcelerate wrote: post #40

Earlier quoted context omitted.

It boggles my mind that we ever thought a small amount of text that fits comfortably on a napkin (the axioms of ZFC) would ever be “good enough” to capture the arithmetic truths or approximate those aspects of physical reality that are primarily relevant to the endeavors of humanity. That the behavior of a six state Turing machine might be unpredictable via a few lines of text does not surprise me in the slightest. A…

> As soon as Gödel published his first incompleteness theorem, I would have thought the entire field of mathematics would have gone full throttle on trying to find more axioms. But why? Gödel's theorem does not depend on number of axioms but on them being recursively enumerable.

Gödel's theorem shows that you need an infinite number of axioms to describe reality (given that available reality isn't finite), so any existing axiomatic system isn't enough.

Re: BusyBeaver(6) Is Quite Large

#57

Post by tromp »

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.

Re: BusyBeaver(6) Is Quite Large

#58

Post by LegionMammal978 »

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.

Let X = "1 if ZF is consistent, 0 otherwise". Then the statements "X = 0" and "X = 1" are independent of ZF. Whether the definition of X is a satisfactory definition of a particular number is a question of mathematical philosophy.

BB(748) is very similar, in that I'd call it a 'definition' independent of ZF rather than a 'number' independent of ZF.

Re: BusyBeaver(6) Is Quite Large

#59

Post by azan_ »

tliltocatl wrote: post #56
azan_ wrote: post #52

Earlier quoted context omitted.

> As soon as Gödel published his first incompleteness theorem, I would have thought the entire field of mathematics would have gone full throttle on trying to find more axioms. But why? Gödel's theorem does not depend on number of axioms but on them being recursively enumerable.

Gödel's theorem shows that you need an infinite number of axioms to describe reality (given that available reality isn't finite), so any existing axiomatic system isn't enough.

Well, obviously we could simply take every true sentence of Peano arithmetic as an axiom to obtain a consistent and complete system, but if we think in that spirit, then almost every mathematician in the world is working on finding a better set of axioms (because every proof would either give us new axiom or show that something should not be included as axiom), right?

Re: BusyBeaver(6) Is Quite Large

#60

Post by charcircuit »

refulgentis wrote: post #44
moralestapia wrote: post #27

Earlier quoted context omitted.

>Unlike Aaronson, he actually is on the forefront of Busy Beaver research [...] Extremely bad ad hominem , I enjoyed Aaronson's read, nothing wrong with it.

Gently, seconding peer: that is not ad hominem :) Colloquially, I understand it's easy to think it means "saying something about someone that could be interpreted negatively" because that's the context it is read in it when it is used. The meaning is saying a logical argument is incorrect because of who wrote the argument.

But the comment is not just saying something negative.

It is implying that claims from the article like "Then, three days ago, Tristan wrote again to say that mxdys has improved the bound again, to BB(6)>9_2_2_2" are not real results. The justification for these not being real results is solely based off whether author is actually on the forefront of research.

Post reply on HN