[HN Gopher] BusyBeaver(6) Is Quite Large
___________________________________________________________________
BusyBeaver(6) Is Quite Large
Author : bdr
Score : 158 points
Date : 2025-06-28 16:53 UTC (6 hours ago)
(HTM) web link (scottaaronson.blog)
(TXT) w3m dump (scottaaronson.blog)
| seeknotfind wrote:
| > So I said, imagine you had 10,000,000sub10 grains of sand. Then
| you could ... well, uh ... you could fill about 10,000,000sub10
| copies of the observable universe with that sand.
|
| I don't get this part. Is it really rounding away the volume of
| the observable universe divided by the average volume of a grain
| of sand? That is many more orders of magnitude than the amount of
| mass in the universe, which is a more usual comparison.
| Scarblac wrote:
| Yes, that's only some normal number amount of orders of
| magnitude. Even 10,000,000^10,000,000 is already so large that
| it doesnt matter, let alone after exponentiating _the exponent_
| nine times more.
| mckeed wrote:
| With tetration you're not dealing with orders of magnitude
| anymore, but orders of magnitude of orders of magnitude.
| Chirono wrote:
| Exactly. This number is so so much bigger than 10^100000 or
| however many grains of sand would fit, that dividing by that
| amount doesn't really change it, certainly not enough to bring
| it down closer to 9,999,999sub10
| Straw wrote:
| Yes, that's right, dividing by that ratio essentially barely
| affects the number in a sense that 'adjacent' numbers in that
| notation give a much bigger change.
|
| 10||10,000,000 / (sand grains per universe) is vastly larger
| than, say, 10||9,999,999
|
| So on system we're using to write these numbers, there's really
| no better way to write (very big)/ (only universally big) than
| by writing exactly that, and then in the notation for very big,
| it pretty much rounds to just (very big).
| lupire wrote:
| 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.
| Nevermark wrote:
| 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!
| fjfaase wrote:
| I wonder if the visible universe is large enough to write down
| the exact value of BB(6).
| Scarblac wrote:
| It's not.
| Alive-in-2025 wrote:
| I want some easier to comprehend number for BB(6), in decimal
| notation. But it's such a massive number I would need to
| invent a new notation to express that. I love this new (to
| me) concept of tetration number representation. 10-million
| sub 10, what is the number?
|
| Look at 3 sub 10 = which is (10^(10^10)). So that is 10 to
| the power of 10 billion. In regular decimal notation, that is
| a "1" with 10 billion "0"s following it. It takes 10
| gigabytes of ram to represent the number in decimal notation,
| naively.
|
| The number of atoms in the universe is only 10^80, or
| 1,000...000 (80 zeroes). 10-million sub 10 is so huge, how
| much ram to represent it.
|
| This example is from
| https://www.statisticshowto.com/tetration-function-simple-
| de...
| kaashif wrote:
| It definitely isn't. The amount of information you can store in
| the universe is something like 10^120 bits. Even if I'm off by
| a trillion orders of magnitude it doesn't matter.
| aeve890 wrote:
| If you treat the observable universe as a closed system, you
| could try to apply the Bekenstein bound using - R [?] 46.5
| billion light-years (radius of the observable universe) - E [?]
| total mass-energy content of the observable universe
|
| The mass-energy includes ordinary matter, dark matter, and dark
| energy. Current estimates suggest the observable universe
| contains roughly 10^53 kg of mass-energy equivalent.
|
| Plugging these into S <= 2pER/c gives someting on the order of
| 10^120 bits of maximum information content.
|
| S <= 2pER/c
|
| S <= (2 x 3.141593 x 3.036e+71 x 4.399e+26)/(1.055e-34 x
| 299792458)
|
| S <= 2.654135e+124
|
| S <= 10^120
|
| So, no.
| Dylan16807 wrote:
| Just the starting number in the article is 1510. That means
| it's 10^(1410). That means it has 1410 digits. So no, you
| can't.
| Scarblac wrote:
| 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.
| ChadNauseam wrote:
| The number itself is not independent of ZFC. (Every integer can
| be expressed in ZFC.) What's independent of ZFC is the process
| of computing BB(748).
| Straw wrote:
| Sure, if someone just gives you the number, ZFC can represent
| it. But ZFC cannot prove that the value is correct, so how do
| you know you have the right number? Use a stronger proof
| system? Go a bit bigger and same issue.
| ajkjk wrote:
| Not an expert, but I've read about this a bit because it
| bothered me also and I think this is the answer:
|
| 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 for a loop).
|
| So presumably the independence of a number from ZFC is like
| that also: you can't prove it's the value of BB(745)
| because you won't know if you've proved it; the only way to
| prove it is essentially to run those Turing machines until
| they stop and you'll never know if you're done.
|
| I'm guessing that for the very small Turing machines there
| is not enough structure possible to encode whatever
| infinitely complex states end up being impossible to deduce
| halting from, so they end up being Collatz-like and then
| you can go prove things about them using math. As you add
| states the possible iteration steps go wild and eventually
| do stuff that is beyond ZFC to analyze.
|
| So the finite value 745 isn't really where the
| infinity/uncomputability comes from-it comes from the
| infinite tape that can produce arbitrarily complex
| functions. (I wonder if over a certain number of states it
| becomes possible to encoding a larger Turing machine in the
| tape somehow, causing a sort of divergence to infinite
| complexity?)
| lupire wrote:
| It has to come from a finite value (specifically, the
| amount of complexity that can be enocoded in 745 pieces
| of information
| https://turingmachinesimulator.com/shared/vgimygpuwi),
| because the finite size 745 with infinite tape leads to
| uncomputability, but the size 5 does not.
|
| In a very real sense, a deep kind of infinite complexity
| can be generated from 745 objects of certain kind, but
| not from 5 objects of that kind..
|
| Turing machines have infinite tape, not infinite state.
| The entire set of all halting machines of a given size
| collectively only use finite tape. Totally finite. Only
| (some of) the non-halting machines use infinite tape.
|
| The problem is that we don't know in advance how large
| the (definitely finite) upper bound on the amount of tape
| all the size-N halting machines use, until after enough
| of them (one per known equivalence class) halt. And we
| don't know (in general) how to run all the halting ones
| until they halt, without also running a non-halting
| program for an unbounded amount of time.
|
| TL:DR: unbounded is not infinite, but big enough to be a
| problem.
| ajkjk wrote:
| I am aware it's an infinite tape and finite state (maybe
| I misspoke somewhere), as well as the halting machines
| using finite tape (because of course they do).
|
| But the overall 'complexity' (at a timestep, say) is
| going to be due to the states and the tape together. The
| BB(5) example that was analyzed, iirc, was a Collatz-like
| problem (Aaronson describes it here:
| https://scottaaronson.blog/?p=8088 ). My interpretation
| of this is that:
|
| 1. collatz-like functions have a lot of complexity just
| due to math alone 2. 5 states turned out to be enough to
| "reach" that one that 3. more states means you're going
| to reach more possible Collatz-like functions (they don't
| have to be Collatz-like; it's just easier to think about
| them like that) 4. eventually you reach ones that ZFC
| cannot show to halt, because there is effectively no way
| to prove it other than running them, and then you would
| have to solve the halting problem.
|
| The part that was helpful for me to be less unsettle by
| BB(745) being independent of the ZFC was the notion that
| it eventually boils down to a halting problem, and asking
| ZFC to "solve" it... which is more agreeable than the
| idea that "ZFC cannot compute a function that seems to be
| solvable by brute force".
| dtech wrote:
| 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.
| ajkjk wrote:
| 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, Godel'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 Godel-numbering stuff is essentially an antiquated
| proof. I remember seeing this in a great paper which I
| can't find now, but it's also mentioned as an aside in
| this blog post: https://scottaaronson.blog/?p=710
|
| wait jk I found it: https://arxiv.org/abs/1909.04569
| LegionMammal978 wrote:
| > What _happens_ at whatever number it starts true at?
|
| Usually, "what _happens_ " is that the machines become
| large enough to represent a form of induction too strong
| for the axioms to 'reason' about. It's a function of the
| axioms of your theory, and you can add more axioms to
| stave it off, but of course you can't prove that your new
| axioms are consistent without even more axioms.
|
| > There is a presentation of it that is in like less than
| one page in terms of the halting problem---all of the
| Godel-numbering stuff is essentially an antiquated proof.
|
| Only insofar as you can put faith into the Church-Turing
| thesis to sort out all the technicalities of enumerating
| and verifying proofs. There still must be an encoding,
| just not the usual Godel numbering.
| thaumasiotes wrote:
| > Incidentally, Godel'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 Godel's theorem is easy to prove if you have
| results about the halting problem. Your first one says
| that in order to prove Godel's theorem, you need to
| establish results about the halting problem.
| ajkjk wrote:
| I'm saying that if you want to understand why Godel's
| theorem is true, look at the one-paragraph proof based on
| the halting problem, not the like 20-page one with Godel
| numbers.
| SAI_Peregrinus wrote:
| Independence from ZFC means we can't prove that any given
| number is BB(643) _using ZFC_. It doesn 't mean we can't
| prove it at all, e.g. one could use a stronger set theory
| like NBG which can prove the consistency of ZFC to verify
| the value of BB(643). But there would be some n for which
| BB(n) is independent of _that_ set theory, requiring a
| yet-stronger theory, and so on ad infinitum.
|
| ZF & ZFC are as important as they are because they're the
| _weakest_ set theories capable of working as the
| foundations of mathematics that we 've found. We can
| always add axioms, but taking axioms away & still having
| a usable theory on which to base mathematics is much more
| difficult.
| Scarblac wrote:
| And also, if BB were computable, then it could be used to
| solve the halting problem: run the Turing machine of size
| n for BB(n) steps, and if it hasn't halted yet, it never
| will. So the BB function is clearly not computable.
|
| But to me as a layman that seems true regardless of
| formal axioms chosen, but I guess I need to read that
| linked thesis.
| ajkjk wrote:
| That is the standard argument for why BB is uncomputable
| for general n, but it's not the same as why BB(n) would
| be independent of ZFC for fixed n.
| thechao wrote:
| We need to distinguish between a computer that's equivalent
| to BB(n), and a computer big enough to compute the value of
| the number that is BB(n). By (terrible) analogy: a 4004 can
| be made to write a finite loop that describes how many
| FLOPs the number 1 supercomputer can compute without,
| itself, being able to usefully perform the computations of
| that supercomputer. (The 4004 will run out of
| memory/addressable disk space.) Similarly, we can no longer
| build _decidable_ programs in ZFC that can compute the
| number BB(748). Scott is saying that they now think this
| "disassociation" might occur at BB(7)!
| nyrikki wrote:
| 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 intuition why, and the latter
| explains why IMHO.
|
| In ZFC, C actually ends up implying PEM, which is why using
| constructionism as a form of reverse math helped it click for
| me .
|
| This is because in the presence of excluded middle, every
| sequentially complete metric space is a complete space, and
| we tend to care about useful things, but for me just how huge
| the search space grows was hidden due to the typical (and
| useful) a priori assumption of PEM.
|
| If you have a (in my view) dislike for the constrictive
| approach or don't want/have to invest in learning an obscure
| school of it, This recent paper[3] on the limits for finding
| a quantum theory of everything is another lens.
|
| Yet another path is through Type 2 TMs and the Borel
| hierarchy, where while you can have a uncomputable number on
| the input tape you algorithms themselves cannot use them,
| while you can produce uncomputable numbers by randomly
| selecting and/or changing an infinite sequence.
|
| Really it is the difference between expressability and
| algorithms working within what you can express.
|
| Hopefully someone else can provide more accessible resources.
| I think a partial understanding of the limits of algorithms
| and computation will become more important in this new era.
|
| [1] https://arxiv.org/abs/chao-dyn/9407003 [2]
| https://arxiv.org/abs/1804.05495 [3]
| https://arxiv.org/abs/2505.11773
| drdeca wrote:
| Looking at [3], they seem to argue that the system isn't
| complete for the usual Godel 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 much specificity as
| such past states actually determine the future states. It
| should not be expected to answer "given a physical setup
| where a Turing machine has been built, is there a time at
| which it halts?" but rather to answer "after N seconds,
| what state is the machine (as part of the physical system)
| in?" (for any particular choice of N).
|
| Whether a particular statement expressed in the language of
| the theory is provable in the theory, is not a claim about
| the finite-time behavior of a physical system, unless your
| model of physics involves like, oracle machines or
| something like that.
|
| Edit: it later says: " Chaitin's theorem states that there
| exists a constant K_{F_{QG}} , determined by the axioms of
| F_{QG} , such that no statement S with Kolmogorov
| complexity K(S) > K_{F_{QG}} can be proven within F_{QG} ."
|
| But this, unless I'm badly misinterpreting it, seems very
| wrong? Most formal systems of interest have infinitely many
| distinct theorems. Given an infinite set of strings, there
| is no finite universal upper bound on the Kolmogorov
| complexity of the strings in that set.
|
| Maybe this was just a typo or something?
|
| They do then mention something about the Bekenstein bound,
| which I haven't considered carefully yet but seems somewhat
| more promising than the parts of the article that preceded
| it.
| tromp wrote:
| 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.
| nyrikki wrote:
| 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_{F_{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?
| bo1024 wrote:
| I think the more correct statement is that there are
| different models of ZFC in which BB(748) are different
| numbers. People find that weird because they don't think
| about non-standard models, as arguably they shouldn't.
| Straw wrote:
| The category error is in thinking that BB(748) is in fact, a
| number. It's merely a mathematical concept.
| Almondsetat wrote:
| As if numbers weren't merely mathematical concepts
| jerf wrote:
| No, that's one of the freakiest things about things like the
| Busy Beaver function. There is an exact integer that BB(748)
| defines. You can add one to it and then it would no longer be
| that number anymore.
|
| If you are refering to the idea that nothing that can't exist
| in the real universe "really exists", then the "Busy Beaver"
| portion of that idea is extraneous, as 100% of integers can't
| exist in the real universe, and therefore, 100% of integers
| are equally just "mathematical concepts". That one of them is
| identified by BB(748) isn't a particularly important aspect.
| But certainly, a very specific number is identified by that
| designation, though nothing in this universe is going to know
| what it is in any meaningful sense.
| perthmad wrote:
| This integer only exists if you assume classical logic.
| Otherwise, there is no such integer a priori, and actually
| there is none in general.
| nyssos wrote:
| Classical logic is the presumed default for mathematics,
| if someone is working in a different system they will say
| so explicitly.
| gylterud wrote:
| Pondering mathematical objects such as BB(n) is exactly
| the kind of stuff which rooks one's faith in classical
| logic.
| jerf wrote:
| 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 that proof is
| somehow flawed. The definition of a Turing Machine is
| effectively the axiom set for this particular case. There
| is a finite set of 748-state Turing machines, and it is
| absolutely the case that there is a set of them that loop
| infinitely, the complementary set that do not, and that
| there is a maximum length amoung the set that do not.
| 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.
|
| For that to be the case, there would _have_ to be some
| symbol under the tape and some state the machine is in
| for which the action the machine takes and the next state
| it goes to would depend on the axioms taken somehow.
| There is no place where the Turing Machine has somehow
| been running for so long and just gotten so large that
| its behavior becomes non-deterministic somehow.
|
| What this means is that even if we lived in a universe
| where we had the unfathomable resources to actually have
| this number somehow meaningfully "in hand", we would be
| unable to prove that it was the correct one with just
| ZFC. Maybe one of the really quite numerous other
| machines still spinning away would in fact terminate in
| the future and be the real BB winner, because even this
| staggeringly monstrously large universe is still piddling
| nothing next to infinity and the other machines still
| require infinite resources to run them to discover they
| never terminate. But that doesn't do anything to affect
| whether or not there in fact is a single concrete integer
| that corresponds to BB(748).
|
| Although one imagines that any universe with the
| resources to "have" BB(748) in it might also have some
| much more powerful axiom systems to play with in the
| process. The amount of computational power this universe
| apparently possesses is beyond all comprehension and who
| knows what they could know. But even if they used a more
| powerful system, it wouldn't change what BB(748) is... it
| just might affect whether or not they were _correct_
| about it.
| LegionMammal978 wrote:
| > 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 proofs, etc., outside of the formalism. If a formal
| statement and its negation do not differ regarding any
| natural numbers small enough to actually exist (in
| whatever sense), then neither is more true than the
| other." In particular, consistency statements may have no
| definite truth value, if the hypothetical proof of an
| inconsistency would be too large.
|
| Of course, metamathematics tells us "you can't do that,
| in principle you could tell the lie if you wrote out the
| whole proof!" But that principle also presupposes the
| existence of arbitrarily-long proofs.
|
| (Personally, hearing some of the arguments people make
| about BB numbers, I've become attracted to agnosticism
| toward ultrafinitist ideas.)
| jerf wrote:
| 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.
| LegionMammal978 wrote:
| > 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.
| Dylan16807 wrote:
| > 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 numbers in their
| head. If you replace "a number" with "some text and code
| and data", people wouldn't say it's surprising that "some
| text and code and data" can be unprovable in ZFC.
|
| Technically a photograph is a number, but _primarily_ it 's
| something else. BB(748) is the same, technically a number
| but primarily it's a series of detailed computer
| calculations.
| gnramires wrote:
| > 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 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!
|
| [1]: Everything that we believe to be finite and of
| interest, that is. We don't know presently anything that
| could be used in reality (a music, picture, etc.) that
| can't in principle be encoded as a large enough number.
|
| I think this is quite interesting, because this encoding
| is critical, and it completes the system. You essentially
| need a machine to turn things into numbers and numbers
| into things; and this is unavoidable. You can actually
| encode this machine itself with numbers! This number
| (which encodes this transcoding machine) can even be
| decoded by its own machine! But we cannot actually avoid
| the machine itself, some actual realization in the real
| world, because any number, in order to represent
| something, can only be translated by one "machine" (which
| can be essentially a computer, or a mind, etc.).
|
| Instead of thinking of machines, you can also think of
| conventions. So you can have a convention that say the
| number '5' encodes the concept 'word', or maybe it simply
| encodes the string of letters "word" ("w"+"o"+"r"+"d").
| But the convention interpretation isn't complete, because
| you still need someone, or something, to interpret this
| convention in practice and potentially turn concepts into
| reality, or simply manipulate those concepts in
| significant and useful ways.
|
| Some more examples: (1) you can encode objects by
| describing a series of solid operations, essentially CAD
| modelling, so you have numbers that represent solids. The
| machine that interprets this number and is able to
| translate it for example into a picture, a series of
| instructions to be interpreted by a 3d printer, of
| performs operations (inferences) about the relevant solid
| model (for example, a structural analysis) is your
| "machine", i.e. your software, without which a number, or
| string of bits by itself doesn't mean anything (except
| the quantity associated with that binary number,
| perhaps), and again this encoding or number is
| essentially arbitrary, it could be very different. (2) a
| JPEG file for example encodes an image that is read by a
| software stack (jpeg decoder+picture viewer+operating
| system+display driver) and forwarded to your monitor to
| be viewed as a pixel array. Again the string of bits
| associated with any image could in principle represent
| anything else representable.
|
| Information (Shannon information in particular) simply
| implies the encoding possible.
|
| It's really interesting that a lot of the time we are
| performing essentially translations between different
| representations of a thing: a series of bits into states
| of pixels on a screen (a picture), [a series of bits]
| into a 3d printed object, into a visualization of an
| object on a screen, etc. (one way), or a reading of a
| camera sensor (photograph) into a series of bits, a
| conception of an object (3d modelling), a conception of a
| story (writing), etc. (the other way). We of course can
| (and must for them to be built of course) conceptualize
| those "machines" themselves (e.g. the software part),
| represent them in some way (our encoding), and then turn
| this representation into a realization of those machines
| (a software, a piece of hardware, or just a
| representation convention, etc.).
|
| In other words, the mind or computer itself is always an
| integral part of the process, and information in a vacuum
| doesn't represent anything necessarily.
|
| Finally, most of what we do is some kind of translation,
| inference, and construction -- everything to assist our
| lives. Of course some "machines" are capable of
| generating new concepts, those are very interesting
| "machines" :)
| Dylan16807 wrote:
| > 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 still 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.
| dtech wrote:
| It's as much a number as 12
| lupire wrote:
| Only if you believe that a number you can't count is a
| number. You can believe that, but it's a leap.
| falcor84 wrote:
| 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...
| Dylan16807 wrote:
| 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.
| falcor84 wrote:
| But that's the thing - each generation struggles with
| whether some new thing is a number. We're typically very
| inclusive, accepting imaginary numbers and even weirder
| things like surreal numbers, which we definitely can't
| count.
|
| But as someone in this generation, I see a good argument
| for rejecting the big busy beaver numbers, which are
| provably outside of the realm of calculating with all the
| resources of our universe's runtime, from being fully
| accepted as numbers, any more than the first
| uninteresting number [0].
|
| [0]
| https://en.wikipedia.org/wiki/Interesting_number_paradox
| Scarblac wrote:
| There is a finite number of Turing machines of size 748. The
| number of them that eventually halt is thus also finite, and
| BB(748) is the highest number of steps in the finite list of
| how many steps each took to halt. It has to be a number.
|
| We just can't prove which number it is, we don't know which
| of the machines halt.
| gylterud wrote:
| A constructive mathematician would indeed deny that BB(748)
| is a well defined number. One could define it as a predicate
| on natural numbers, but lest we find a contradiction in ZFC
| we cannot hope to constructively prove that it holds for any
| number.
| bmacho wrote:
| 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.
| Xcelerate wrote:
| 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.
|
| As soon as Godel 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. Instead, over
| the almost century since then, Godel's work has been treated
| more as an odd fact largely confined to niche foundational
| studies rather than any sort of mainstream program (I'm aware
| of Feferman, Friedman, etc., but my point is there is
| significantly less research in this area compared to most other
| topics in mathematics).
| azan_ wrote:
| > As soon as Godel 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? Godel's theorem does not depend on number of axioms
| but on them being recursively enumerable.
| tliltocatl wrote:
| Godel'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.
| azan_ wrote:
| 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?
| Xcelerate wrote:
| > obviously we could simply take every true sentence of
| Peano arithmetic as an axiom to obtain a consistent and
| complete system
|
| If you're talking about every true sentence in the
| _language of PA_ , then not all such sentences are
| derivable via the theory of PA. If you are talking about
| the theorems of PA, then these are missing an infinite
| number of true statements in the language of PA.
|
| Harvey Friedman's "grand conjecture" is that virtually
| every theorem that working mathematicians actually
| publish can already be proved in Elementary Function
| Arithmetic (much weaker than PA in fact). So the majority
| of mathematicians are not pushing the boundaries of the
| existing foundational theories of mathematics, although
| there is certainly plenty of activity regardless.
| Xcelerate wrote:
| Right, Hilbert's goal was (loosely speaking) to "find a
| finitely describable formal system" sufficient to "capture
| all truths". When Godel showed that can't be done, that
| shouldn't imply we just stop with the best theory we have
| so far and call it a day--it means there are an infinite
| number of more powerful theories (with necessarily longer
| minimal descriptions) waiting to be discovered.
|
| In fact, both Godel and Turing worked on this problem quite
| a bit. Godel thought we might be able to find some sort of
| "meta-principle" that could guide us toward discovering an
| ever increasing hierarchy of more powerful axioms, and
| Turing's work on ordinal progressions followed exactly this
| line of thinking as well. Feferman's completeness theorem
| even showed that all arithmetical truths could be
| discovered via an infinite process. (Now of course this
| process is not finitely axiomatizable, but one can
| certainly extract some useful finite axioms out of it --
| the strength of PA after all is equivalent to the recursive
| iteration up to e_0 of 'Q_{n+1} = Q_n + Q_n is consistent'
| where Q_0 is Robinson arithmetic).
| czbot wrote:
| Within ZFC one can prove that any two models of second order
| PA are isomorphic. ZFC proves that PA is consistent. ZFC is
| good enough to capture arithmetical truth.
| cevi wrote:
| 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-algorithm-a-new-
| simple...
| czbot wrote:
| 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. They
| are countable externally and not internally.
| hyperpape wrote:
| This ignores the fact that it is not so easy to find natural
| interesting statements that are independent of ZFC.
|
| Statements that are independent of ZFC are a dime a dozen
| when doing foundations of mathematics, but they're not so
| common in many other areas of math. Harvey Friedman has done
| interesting work on finding "natural" statements that are
| independent of ZFC, but there's dispute about how natural
| they are. https://mathoverflow.net/questions/1924/what-are-
| some-reason...
|
| In fact, it turns out that a huge amount of mathematics does
| not even require set theory, it is just a habit for
| mathematicians to work in set theory.
| https://en.wikipedia.org/wiki/Reverse_mathematics.
| Xcelerate wrote:
| Yeah, I'm quite familiar with Friedman's work. I mentioned
| him and his Grand Conjecture in another comment.
|
| > This ignores the fact that it is not so easy to find
| natural interesting statements that are independent of ZFC.
|
| I'm not ignoring this fact--just observing that the sheer
| difficulty of the task seems to have encouraged
| mathematicians to pursue other areas of work beside
| foundational topics, which is a bit unfortunate in my
| opinion.
| hyperpape wrote:
| I agree most working mathematicians have limited interest
| in foundational topics. To me, that seems harmless
| enough.
|
| > approximate those aspects of physical reality that are
| primarily relevant to the endeavors of humanity.
|
| This is the comment that made me think that you were
| saying we needed more work on foundations for math as it
| is used in the sciences, and that doesn't match my
| understanding. Did I read it differently than you meant
| it?
| tromp wrote:
| 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 Godel's
| famous results, neither of those cases is possible if ZFC is
| assumed to be consistent.
| Scarblac wrote:
| I don't understand, surely if we assume ZFC is consistent
| then it's obvious that it won't halt? Even if its consistency
| can't be proven, neither can its inconsistency, so it won't
| halt. Or is _that_ only provable outside of ZFC?
|
| I guess it's also hard when we have an _arbitrary_ Turing
| machine and have to prove that what it 's doing isn't
| equilavent to trying to prove an undecibable statement.
| tromp wrote:
| If we assume ZFC to be consistent, then Godel's 2nd
| incompleteness theorem tells us that it cannot prove its
| own consistency. So in particular it cannot prove than
| TM_ZFC_INC will never halt.
| LegionMammal978 wrote:
| If you believe that ZF is consistent, then you believe that
| the machine cannot halt (assuming you trust its
| construction). But you cannot write a _proof in ZF_ that
| the machine cannot halt. Such a proof must include a new
| axiom "ZF is consistent", or some stronger axiom.
| Diggsey wrote:
| 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.
| LegionMammal978 wrote:
| 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.
| eapriv wrote:
| It's not "an uncomputable number".
| drdeca wrote:
| 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.
| boothby wrote:
| Individual numbers can be uncomputable! For example, take
| your favorite enumeration of Turing machines, (T1, T2...) and
| write down a real number in binary where the first bit is 0
| if T1 halts and 1 otherwise, second bit is 0 if T2 halts...
| clearly this number is real and between 0 and 1, but it
| cannot be computed in finite time.
| Vecr wrote:
| If it had a finite size it would be computable.
| bo1024 wrote:
| 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 of
| ZFC where BB(748) are two different numbers.
|
| * We can take one of these to be the "standard model"[1] that
| we all think of when we picture a Turing Machine. However, the
| other would be a strange "non-standard" model that includes
| finite "natural numbers" that are not in the set {0,1,2,3,...}
| and it includes Turing Machines that halt in "finite" time that
| we would not say halt at all in the standard model.
|
| * So BB(748) is indeed a number as far as the standard model is
| concerned, the problem only comes from non-standard models.
|
| TL;DR this is more about the fact that ZFC axioms allow weird
| models of Turing Machines that don't match how we think Turing
| Machines usually work.
|
| [1] https://en.wikipedia.org/wiki/Non-
| standard_model_of_arithmet...
| red75prime wrote:
| > 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.
| sedatk wrote:
| > 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.
| griffzhowl wrote:
| Continuing the theme of iteration: it was the first time I
| encountered pentation
| tialaramex wrote:
| 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.
| Nevermark wrote:
| Don't forget identity. Its range is small but important!
| tialaramex wrote:
| Fair!
| lbourdages wrote:
| 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
| NooneAtAll3 wrote:
| 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
| moralestapia wrote:
| >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.
| lupire wrote:
| That's not _ad hominem_ at all.
| refulgentis wrote:
| 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.
| charcircuit wrote:
| 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.
| refulgentis wrote:
| I think you're touching on something important here.
|
| OP isn't making a ad hominem fallacy in a logical
| argument sense - it's not saying "Aaronson is wrong
| because he's not a frontline researcher."
|
| But you're absolutely right to feel uncomfortable with
| their approach. There's something off-putting about
| dismissing someone's reporting of research developments,
| even if you prefer more comprehensive coverage, or
| there's more interesting things to say.
|
| The thing is, if that's ad hominem, so is _any
| recommendation preferring one second-hand reporting over
| another_ -- ex. "if you want the _actual_ news, read
| Tucker, not Krugman " isn't an ad hominem towards
| Krugman.
|
| Another example we see often on HN: saying "you should
| read the actual paper instead of this pop science" is a
| quite frequent, quite agreeable, and yet dull,
| contribution on say, a Quanta article. Yet, I imagine we
| agree this isn't an ad hominem.
|
| The real issue might be that OP conflates two different
| things: being a primary researcher versus being a good
| science communicator who accurately reports on others'
| work.
|
| Both roles have value, and questioning whether someone
| has filled one role doesn't necessarily invalidate their
| ability to fill the other.
|
| (this helped me understand my odd frustration with the
| dull comments on science articles: I emotionally engage
| with it as being mean / out of bounds, but its true, and
| in reality, what I'm frustrated with is there could
| always be a more detailed article, or even paper, but yet
| we all must publish)
| charcircuit wrote:
| >ex. "if you want the actual news, read Tucker, not
| Krugman" isn't an ad hominem towards Krugman.
|
| But how you justify that could be one. If you are just
| attacking the person instead of their reporting I would
| call that ad hominem.
| moralestapia wrote:
| The wording implies that Aaronson does not know what he's
| talking about.
|
| >If you want to learn about _actual_ Busy Beaver results
| [...]
|
| This is saying there is no discussion of the results in the
| article, which is not true.
|
| >Unlike Aaronson, he actually is on the forefront of Busy
| Beaver research [...]
|
| This implies Aaronson has no (or lesser) authority on the
| subject and suggests we should listen to somebody else who
| purportedly has more.
|
| Nowhere in @NooneAtAll3's comment is there an argument made
| against/for the contents of the article, an example of that
| would be:
|
| "Aaronson mentions X but this is not correct because Y" or
| something along those lines.
|
| Instead, the comment, in it's full extent, is either
| discrediting (perhaps unintentionally) and/or appealing to
| the authority of people involved. That's _ad hominem_.
| tedunangst wrote:
| Can you elaborate on what's wrong with this post?
| lupire wrote:
| https://www.sligocki.com/ hasn't posted since April, and the
| very first link on that blog is a link to... Scott Aaronson.
| refulgentis wrote:
| 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)
| alexeldeib wrote:
| 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
| renewiltord wrote:
| I don't get it. What's wrong with the post? And
| https://arxiv.org/abs/1605.04343 is interesting, no?
| charcircuit wrote:
| >imagine you had 10,000,000_10 grains of sand. Then you could ...
| well, uh ... you could fill about 10,000,000_10 copies of the
| observable universe with that sand. I hope that helps people
| visualize it!
|
| People can't visualize numbers that big. There's more ways to
| express numbers than just counting them. For example a single
| grain of sand has infinite states it can be in (there are an
| infinite amount of real numbers), so you could say a single grain
| of sand could represent BB(6). Combinations can grow
| exponentially, so that may be something useful to try and express
| it.
| Xcelerate wrote:
| At some point big numbers become much more about the
| consistency strength of formal systems than "large quantities".
|
| I.e., how well can a system fake being inconsistent before that
| fact it discovered? An inconsistent system faking consistency
| via BB(3) will be "found out" much quicker than a system faking
| consistency via BB(6). (What I mean by faking consistency is
| claiming that all programs that run longer than BB(n) steps for
| some n never halt.)
| unsnap_biceps wrote:
| I'm confused about this example, isn't the count of grains of
| sand equal to the count of observable universes so it'd be a
| single grain of sand per universe?
| heftig wrote:
| The "about" does a lot of heavy lifting in this example.
| Dividing 10,000,000_10 by the number of grains that fit into
| one universe doesn't change it much. The 10,000,000 would get
| smaller somewhere in the deep depths of the decimal fraction.
| Dylan16807 wrote:
| If the universe rounds to the nearest Planck unit, then a grain
| of sand suddenly has not all that many states.
|
| Using infinite precision to make things seem tractable is
| sleight of hand in my book. Stick with integers when you're
| describing scale.
| MichaelDickens wrote:
| It's known that BB(14) is bigger than Graham's number, but this
| new finding leads me to believe that BB(7) is probably bigger
| than Graham's number. Intuitively, the technology required to go
| from pentation to Graham's number feels simpler than the
| technology required to go from `47,176,870` to `2 <pentate> 5`.
| tromp wrote:
| Thanks for sharing; your post would fit well as an answer to
| mine about Graham's number...
| phs wrote:
| So what is the richest logic whose proofs can be enumerated with
| only a five state TM?
| tromp wrote:
| That entirely depends on how you want to interpret a finite
| binary string as an enumeration of logic proofs?!
| tromp wrote:
| People on the bbchallenge Discord server are keen to speculate on
| how many Turing Machine states are needed to surpass Graham's
| Number, which is vastly larger than the 2^^2^^2^^9 achieved by
| the latest BB(6) champion.
|
| We know from the functional busy beaver [1] that Graham behaviour
| can come surprisingly early; a 49-bit lambda term suffices. There
| are only 77519927606 closed lambda terms of at most that size
| [2], compared to 4^12*23836540=399910780272640 unique 6-state
| Turing Machines [3].
|
| With the achievement of pentation in only 6 states, several
| people now believe that 7 states should suffice to surpass
| Graham's. I would still find that rather surprising. A few days
| ago, I made a large bet with one of them on whether we would see
| proof of BB(7)>Graham's within the next 10 years.
|
| What do people here think?
|
| [1] https://oeis.org/A333479
|
| [2] https://oeis.org/A114852
|
| [3] https://oeis.org/A107668
| gpm wrote:
| 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-arrow^n, and up-arrow^f(n) for any
| computable f).
|
| My gut feeling is that the growth between 47 million and
| 2^^2^^2^^9 is qualitatively larger than the growth between
| 2^^2^^2^^9 and graham's number in terms of how strong the
| operator we need is (with gramah's number being g_64 and g here
| being roughly one step "above" up_arrow^n). So probably we
| should have BB(7)>Graham's number.
| d_silin wrote:
| Any time I see such results from computation complexity theory, I
| realize that any current zeitgeist of "super-intelligent AI are
| gods" is complete bullshit.
|
| You can convert every atom of observable Universe into a
| substrate for supercomputer, you can harness energies of
| supermassive black holes to power it, but running a humble BB(6)
| to halting state would be forever out of its reach.
| istjohn wrote:
| That strawman never stood a chance.
___________________________________________________________________
(page generated 2025-06-28 23:00 UTC)