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

101–110 of 232 posts

Re: BusyBeaver(6) Is Quite Large

#101

Post by jerf »

LegionMammal978 wrote: post #95
jerf wrote: post #86

Earlier quoted context omitted.

I'm fairly certain that's wrong, and I see a couple of other people may be making that mistake elsewhere in this conversation too. A Turing Machine is a Turing Machine. The execution trace of a Turing Machine is fully determined by its ruleset and its initial input. It doesn't matter which axioms you "take", nor does it matter what the intent of the initial construction of the 748-state machine was, or indeed even if…

> There is no situation where "the next step" of the Turing Machine "depends on your axioms" and could thereby be affected by such a decision. That's easy, you just have to be an ultrafinitist, and say, "The definition of a TM presupposes an infinite set of natural numbers for time steps and tape configurations. But there aren't actually infinitely many natural numbers, infinitely long executions, arbitrarily long pr…

To be honest I'm not even particularly impressed by that line of reasoning because even if you accept ultrafinitism, there's still a definite integer that it corresponds to. You can deny the "existence" of integers, and thus that the number "exists", but that's contingent on your definition of "existence". It doesn't change what it would be if it did exist.

Plus, ultafinitism is essentially relative to the universe you find yourself in. I hypothesized a universe in which BB(748) could actually exist, but you can equally hypothesize ones in which not only can it exist, it exists comfortably and is considered a small number by its denizens. We can't conceive of such a thing but there's no particular a priori reason to suppose it couldn't exist. If such a universe does actually "exist" does that mean our ultrafinitism is wrong? I'm actually a sort of a proponent of knowing whether your operating in a math space that corresponds to the universe (see also constructive mathematics), but concretely declaring that nothing could possibly exist that doesn't fit into our universe is a philosophical statement, not a mathematical one.

Re: BusyBeaver(6) Is Quite Large

#102

Post by tialaramex »

Nevermark wrote: post #74
tialaramex wrote: post #54

Earlier quoted context omitted.

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

Don't forget identity. Its range is small but important!

Fair!

Re: BusyBeaver(6) Is Quite Large

#103

Post by LegionMammal978 »

jerf wrote: post #101
LegionMammal978 wrote: post #95

Earlier quoted context omitted.

> There is no situation where "the next step" of the Turing Machine "depends on your axioms" and could thereby be affected by such a decision. That's easy, you just have to be an ultrafinitist, and say, "The definition of a TM presupposes an infinite set of natural numbers for time steps and tape configurations. But there aren't actually infinitely many natural numbers, infinitely long executions, arbitrarily long pr…

To be honest I'm not even particularly impressed by that line of reasoning because even if you accept ultrafinitism, there's still a definite integer that it corresponds to. You can deny the "existence" of integers, and thus that the number "exists", but that's contingent on your definition of "existence". It doesn't change what it would be if it did exist. Plus, ultafinitism is essentially relative to the universe y…

> there's still a definite integer that it corresponds to.

The formalism says that there's still a definite integer that it corresponds to. The ultrafinitist would deny that the formalism keeps capturing truth past where we've verified it to be true, or some unknown distance farther.

> I hypothesized a universe in which BB(748) could actually exist, but you can equally hypothesize ones in which not only can it exist, it exists comfortably and is considered a small number by its denizens.

Sure, but the ultrafinitist would argue, "All this is still just a shallow hypothesis: you've said the words, but that's not enough to breathe much 'life' into the concept. It is but the simplest of approximations that can fit into our heads, and such large things (if they could exist) would likely have an entirely different nature that is incomprehensible to us."

> We can't conceive of such a thing but there's no particular a priori reason to suppose it couldn't exist.

That's why I wouldn't call myself an ultrafinitist, but would prefer an agnostic approach. There may be no great a priori reason to suppose it cannot exist, but I similarly do not see any such reason it must necessarily exist. We empirically notice that our formalism works for numbers small enough to work with, and we pragmatically round it off to "this formalism is true", but one could argue that surprising claims about huge numbers need stronger support than mere pragmatism.

Re: BusyBeaver(6) Is Quite Large

#104

Post by ajkjk »

thaumasiotes wrote: post #83
ajkjk wrote: post #43

Earlier quoted context omitted.

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…

> 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 Those are two very different ideas. Your second sentence says that Gödel's theorem is easy to prove if you have results about the halting problem. Your first one says that in order to prove Gödel's theor…

I'm saying that if you want to understand why Gödel's theorem is true, look at the one-paragraph proof based on the halting problem, not the like 20-page one with Gödel numbers.

Re: BusyBeaver(6) Is Quite Large

#105

Post by tromp »

drdeca wrote: post #91
nyrikki wrote: post #62

Earlier quoted context omitted.

To try and help people digging into this, the following helped me. Two lenses for trying to understand this are potentially Chastain's limits on output of a lisp program being more complex than the program itself [1] or Markov's proof that you can't classify manifolds in d>= 4. If you try the latter and need/want to figure out how the Russian school is so different this is helpful [2] IMHO the former gives an intuiti…

Looking at [3], they seem to argue that the system isn’t complete for the usual Gödel reasons, which, sure, it isn’t, but then they call the claim that the system fails to decide, which is a statement about probability, a “scientific fact”. This seems to me like a mistake? Like, a TOE is not expected to decide all statements expressible in the theory, only to predict particular future states from past states, with as…

It looks like the authors of [3] misunderstood Chaitin. What Chaitin said about the limits of provability is that no statements of the form "K(x) > c_F" can be proven in formal system F where c_F is some constant depending on F.

Re: BusyBeaver(6) Is Quite Large

#106

Post by Dylan16807 »

gnramires wrote: post #94
Dylan16807 wrote: post #41

Earlier quoted context omitted.

> that's one of the freakiest things about things like the Busy Beaver function Every sentence ever spoken and every view ever looked at is also a number. It's not a freaky thing about "things like" busy beaver, it's a freaky thing about the concept of information. But even though everything is a number, saying "it's crazy that a number can be X" is usually someone making a mistake, using the everyday concept of numb…

> Every sentence ever spoken and every view ever looked at is also a number. It's not a freaky thing about "things like" busy beaver, it's a freaky thing about the concept of information. I'd say that's a bit of a wrong or misleading statement. I think the correct version is "everything[1] can be encoded as a number". The concept of number is a very particular concept! It's pretty absurd to say "a screwdriver is a nu…

> I'd say that's a bit of a wrong or misleading statement. I think the correct version is "everything[1] can be encoded as a number". The concept of number is a very particular concept! It's pretty absurd to say "a screwdriver is a number" or "a word is a number". That is true for the peano axiomatization of numbers; but to me in particular, I believe numbers are a generalization (and formalization) of the idea or concept of quantity. There's a particular idea that refers to say 'two' apples, the quantity of apples. A word is not a quantity, it's a different concept. Even though each of them could be encoded as a number somehow!

Well if we're using a more narrow view, then "BB(748)" isn't a number, it's an encoding of a partial algorithm. And it shouldn't be surprising that an algorithm might be unprovable in ZFC.

The actual number, the quantity, is quite easy to write down inside ZFC. And so is the beaver turing machine itself. The hard part is knowing which of the 748-state machines is the beaver.

Re: BusyBeaver(6) Is Quite Large

#107

Post by Diggsey »

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.

I think what's most unintuitive is that most (all?) "paradoxes" or "unknowables" in mathematics involve infinities. When limiting ourselves to finite whole numbers, paradoxes necessarily disappear.

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.

The execution of the turing machine can be encoded in ZFC, so it really is the value of BB(748) that is the magic ingredient. Somehow even knowledge of the value of this finite number is a more potent axiomatic system than any we've developed.

Re: BusyBeaver(6) Is Quite Large

#108

Post by red75prime »

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 a number (an uncomputable number, granted) like BB(748) can be "independent of ZFC".

It's BB(n) that is incomputable (that is there's no algorithm that outputs the value of BB(n) for arbitrary n).

BB(748) is computable. It's, by definition, a number of ones written by some Turing machine with 748 states. That is this machine computes BB(748).

> It feels like a category error or something.

The number itself is just a literally unimaginably large number. Independence of ZFC comes in when we try to prove that this number is the number we seek. And to do that you need theory more powerful than ZFC to capture properties of a Turing machine with 748 states.

Re: BusyBeaver(6) Is Quite Large

#109

Post by lbourdages »

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.

I've seen it before, but it was using Knuth's up-arrow notation [1], which I like because it generalizes easily.

[1] https://en.wikipedia.org/wiki/Knuth's_up-arrow_notation

Re: BusyBeaver(6) Is Quite Large

#110

Post by nyrikki »

drdeca wrote: post #91
nyrikki wrote: post #62

Earlier quoted context omitted.

To try and help people digging into this, the following helped me. Two lenses for trying to understand this are potentially Chastain's limits on output of a lisp program being more complex than the program itself [1] or Markov's proof that you can't classify manifolds in d>= 4. If you try the latter and need/want to figure out how the Russian school is so different this is helpful [2] IMHO the former gives an intuiti…

Looking at [3], they seem to argue that the system isn’t complete for the usual Gödel reasons, which, sure, it isn’t, but then they call the claim that the system fails to decide, which is a statement about probability, a “scientific fact”. This seems to me like a mistake? Like, a TOE is not expected to decide all statements expressible in the theory, only to predict particular future states from past states, with as…

I will admit that I added that cite mostly because of the very real barriers to even learning RUSS.

By the typos etc.. you. can probably also tell I was doing this on mobile, unfortunately as a passenger in a car.

To quote Chaitin’s explanation here:

> In contrast I would like to measure the power of a set of axioms and rules of inference. I would like to be able to say that if one has ten pounds of axioms and a twenty-pound theorem, then that theorem cannot be derived from those axioms.

This paper's notation does seem to be confusing, but I still think it is essentially complete with the above.

"K_{ℱ_{QG}}" would probably most commonly be L in most descriptions, a natural number that is the upper bound of complexity for provable statements in a formal system S

L is not a limit on complexity, it means that there is no formal proof for S that its Kolmogorov complexity exceeds L, for any string.

You can still prove that there are strings far more complex than L with S, and in fact there will often be far more of those strings than the ones equal to or less than L.

It is a limit on what you can prove about those strings with a greaterKolmogorov complexity in S.

Or to rewrite the above:

"There exists a natural number L such that we can't prove the Kolmogorov complexity of any specific string of bits is more than L."

Does that help or did I miss the mark on your objection?

Post reply on HN