https://scottaaronson.blog/?p=6673 Shtetl-Optimized The Blog of Scott Aaronson If you take nothing else from this blog: quantum computers won't solve hard problems instantly by just trying all solutions in parallel. Also, next pandemic, let's approve the vaccines faster! --------------------------------------------------------------------- << That Financial Times QC skepticism piece My Quantum Information Science II Lecture Notes: The wait is over! >> Busy Beaver Updates: Now Even Busier Way back in the covid-filled summer of 2020, I wrote a survey article about the ridiculously-rapidly-growing Busy Beaver function. My survey then expanded to nearly twice its original length, with the ideas, observations, and open problems of commenters on this blog. Ever since, I've felt a sort of duty to blog later developments in BusyBeaverology as well. It's like, I've built my dam, I've built my lodge, I'm here in the pond to stay! So without further ado: * This May, Pavel Kropitz found a machine demonstrating that $$ BB (6) \ge 10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^ {10}}}}}}}}}}}}}} $$ (15 times)--thereby blasting through his own 2010 record, that BB(6)>=10^36,534. Or, for those tuning in from home: Kropitz constructed a 6-state, 2-symbol, 1-tape Turing machine that runs for at least the above number of steps, when started on an initially blank tape, and then halt. The machine was analyzed and verified by Pascal Michel, the modern keeper of Busy Beaver lore. In my 2020 survey, I'd relayed an open problem posed by my then 7-year-old daughter Lily: namely, what's the first n such that BB(n) exceeds A(n), the n^th value of the Ackermann function? All that's been proven is that this n is at least 5 and at most 18. Kropitz and Michel's discovery doesn't settle the question--titanic though it is, the new lower bound on BB(6) is still less than A(6) (!!)--but in light of this result, I now strongly conjecture that the crossover happens at either n=6 or n=7. Huge congratulations to Pavel and Pascal! * Tristan Sterin and Damien Woods wrote to tell me about a new collaborative initiative they've launched called BB Challenge. With the participation of other leading figures in the neither-large-nor-sprawling Busy Beaver world, Tristan and Damien are aiming, not only to pin down the value of BB(5)--proving or disproving the longstanding conjecture that BB(5)=47,176,870--but to do so in a formally verified way, with none of the old ambiguities about which Turing machines have or haven't been satisfactorily analyzed. In my survey article, I'd passed along a claim that, of all the 5-state machines, only 25 remained to be analyzed, to understand whether or not they run forever--the "default guess" being that they all do, but that proving it for some of them might require fearsomely difficult number theory. With their more formal and cautious approach, Tristan and Damien still count 1.5 million (!) holdout machines, but they hope to cut down that number extremely rapidly. If you're feeling yourself successfully nerd-sniped, please join the quest and help them out! Email, RSSEmail, RSS Follow This entry was posted on Tuesday, August 30th, 2022 at 5:38 pm and is filed under Announcements, Nerd Interest. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site. 35 Responses to "Busy Beaver Updates: Now Even Busier" 1. Shawn Ligocki Says: Comment #1 August 30th, 2022 at 8:55 pm For anyone interested in exploring the inner workings of this record breaker, I wrote up an analysis on my blog in June: https: //www.sligocki.com/2022/06/21/bb-6-2-t15.html . It requires a bit of number theory (Euler's totient theorem) to prove since this number is not only too long to run any simulator for directly, but also to large to even write all the digits directly! 2. Scott Says: Comment #2 August 30th, 2022 at 9:40 pm Shawn Ligocki #1: Thanks so much!! 3. Justin Kee Says: Comment #3 August 30th, 2022 at 11:16 pm I have a question for Scott. If the BB problem is uncomputable, how do people compute upper and lower bounds for the runtime? Isn't the whole point that the BB problem is uncomputable and thus the answer cannot be computed to exactitude without it being full run, i.e. computed. If there are shortcuts to provide bounds, doesn't that imply that there exists computable aspects to the actual termination points that exist without doing the ultimate computations? I am genuinely interested in this answer. 4. Scott Says: Comment #4 August 31st, 2022 at 4:01 am Justin Kee #3: For BB(n) to be uncomputable means that there's no general algorithm that takes n as input and always halts after finitely many steps with BB(n) as its output. It doesn't mean that we can't hope to figure out BB(n) for any specific values of n. We can--and it's precisely the general uncomputability that makes the quest fun and interesting. More concretely: for each n, there are only finitely many Turing machines with n states. You can try running all of them in parallel. Whenever one of the machines halts, that tells you a new lower bound on BB(n). Eventually, the last n-state machine ever to halt will do so, and then you'll "know" BB(n) itself. But wait, how is that consistent with BB's uncomputability? Well, the trouble is that you won't know that you know the correct value! For what about all the machines that haven't halted yet: how do you know none of them ever will? That requires a proof of non-termination, a separate one for each non-halting machine. Turing tells us that there can be no systematic method to find such proofs (if there were, then BB and the halting problem would be computable), and Godel tells us that, in any fixed axiomatic theory, the proofs don't even always exist. Nevertheless, by hook or by crook, by a combination of automated methods and case-by-case cleverness, people managed to find proofs of non-termination for all the non-halting 3-state machines (in the 1960s) and 4-state machines (in the 1980s). They're now trying to do the same for the 5-state machines, and thereby prove that a 5-state candidate discovered by Marxen and Buntrock in 1990 is actually the Busy Beaver. Even if they succeed, it's entirely plausible that our civilization will never be able to do this for the 6-state machines. Or maybe the superintelligent AIs that take over from us will manage, but then they'll struggle forever with the 7-state machines. 5. pku Says: Comment #5 August 31st, 2022 at 5:39 am A philosophical question: You've shown before that there's an N (iirc about 700) for which BB(N) is undefined under ZFC. Would that mean it's not a concretely specified finite number? Would you accept BB(1000) as a contestant in a "who can name the biggest number" contest? what about BB(BB(1000))? 6. Scott Says: Comment #6 August 31st, 2022 at 7:55 am pku #5: The correct answer to your philosophical question is that BB(n) is perfectly well-defined for every value of n--it's just that the particular theory ZFC doesn't prove its values after some finite point, and you need to learn to distinguish those two concepts, and the BB function itself is as good a place as any to learn. I mean, consider this: for every k for which the statement is true, ZFC actually does prove that BB(1000)>=k, since you just need to simulate the appropriate 1000-state Turing machine for k steps and see that it doesn't halt. The problem is "merely" that there are other 1000-state Turing machines that run forever, but for which ZFC can't prove it (as shown by Stefan O'Rear's improvement to my and Yedidia's result). But I don't see why that problem should in any way disqualify BB (1000) from the biggest number contest. After all, if the other contestant writes anything that's naive to computability theory--Ackermann(1000000) or whatever--then not only will it be true that BB(1000) vastly exceeds that, but by the above argument, it will actually be a theorem of ZFC! 7. fred Says: Comment #7 August 31st, 2022 at 8:33 am I can't wrap my mind around the type of math/proof required to come up with numbers that big. At some point the number "15" has to come up as a parameter, no? Btw, isn't there a compact notation to represent (...(((((10^10)^ 10)....^10), like 10@15? [edit] I saw in that first comment link that it's 10||15. 8. pku Says: Comment #8 August 31st, 2022 at 8:49 am Hm, is there some concrete finite computational problem in this style that you could make undecidable? E.g. using the beeping busy beaver numbers, I think you've shown that for large k BBB (k)>BB(k+1). But is it decidable to, say, compare BBB(1000) and BB(1002)? (Or if there's some bound that solves that specific one, is there some way to build non-zfc comparable finite numbers using these methods)? I guess this isn't really any worse than "is 1>x, where x is 2 if the continuum hypothesis is true and 0 otherwise". But it feels like BB numbers have a specific definition in ways that CC doesn't, so it feels weirder. 9. Nick Drozd Says: Comment #9 August 31st, 2022 at 9:09 am In the Bigger Number Game, contestants write down descriptions of numbers on index cards. Assuming a minimum character size, there are only finitely many such descriptions, and in principle they could all be enumerated and compared. Scott proposed the Busy Beaver function as a way to win the BNG. But we can also think of each BB value as being its own Bigger Number Game played out, where the number of states available to be used correspond to the size of the "index card". This version of the BNG is not a duel; instead, we can imagine that each program in the particular Turing machine class has been submitted by a different contestant. Adjudicating this contest requires figuring out which of the halting programs runs the longest. But it also requires figuring out which ones don't halt at all. The number of contest entries gets out of hand fast, growing like O(n^n) (what do you call that kind of growth?) with the number of states. Even with just three states it isn't feasible to look at each entry individually. Instead, the review process has to be automated. You write up some code that will detect certain patterns, typically patterns that prove non-halting. Then you pass each entry through that detector, and any matches can be discarded. Anything left over afterwards gets reviewed manually. But the difficulties have only just begun. Any "holdout" programs that have made it to manual review by definition exhibit novel or unusual behavior, for otherwise they would have been detected earlier. So the holdouts are an especially difficult set of programs to analyze. And for any given automated detector, the number of holdouts will also grow exponentially with the number of states. And remember, it's not known whether the holdouts halt or not. For all that you (the judge) know, some of them might halt! In principle a program that actually does halt can be proved to halt, but in practice this can be quite difficult. Look at Shawn #1 to see how the sausage is made. Proving non-haltingness is even worse, since that might be uncomputable even in principle. And that's just for a single entry to be considered! Again, there are an awful lot of them to go through. 10. dankane Says: Comment #10 August 31st, 2022 at 9:49 am Scott #6: Actually, I think that whether or not BB(n) is well defined depends on your philosophical interpretation. If you are a formalist, then the fact that BB(10,000) is independent of ZFC means that there are different models of set theory in which BB (10,000) is actually a different number. According to this view, the correct answer to the question of what BB(10,000) is would be to ask what exactly the questioner means by a Turing machine running forever. 11. f3et Says: Comment #11 August 31st, 2022 at 10:32 am Oh lucky day ! Another subject (beside go and go programs) where I can boast of expert knowledge. So first, as mind-boggling as is the Ackerman function, it is dwarfed by the fast-growing herarchy (https://en.wikipedia.org/wiki/Fast-growing_hierarchy), itself dwarfed, of course, by things like the function TREE (and similar things for which the pertinent ordinal is not known ; see https:/ /en.wikipedia.org/wiki/Kruskal%27s_tree_theorem#TREE(3) ). Then come non computable functions like BB, and the winner (for the game of the biggest number) is Rayo's number : https:// en.wikipedia.org/wiki/Rayo%27s_number. 12. Scott Says: Comment #12 August 31st, 2022 at 11:16 am pku #8: But is it decidable to, say, compare BBB(1000) and BB(1002)? Yes, it should be! ZFC and even PA almost certainly prove that BBB(1000) is vastly larger. Crucially, to do so, they don't need to determine the actual value of either number. They just need to prove that 1000-state beeping TMs can suitably simulate (and thereby dominate) 1002-state ordinary TMs for the purpose of running for huge finite amounts of time. Admittedly, I don't know off the top of my head exactly how to do that, but I strongly conjecture that it can be done. It's actually a great question. Does anyone here have ideas? "In practice," in a bigger-number contest, if one contestant used a more powerful naming formalism than the other, then the hope would be that the contestant who used the weaker formalism would simply concede, seeing how untenable their situation was. If they actually demanded to see proof that their number was smaller, in many cases that would require a large and tedious mathematical effort, but it should normally be possible in principle. 13. Scott Says: Comment #13 August 31st, 2022 at 11:23 am dankane #10: Actually, I think that whether or not BB(n) is well defined depends on your philosophical interpretation. Yeah, I'm asserting that the philosophical interpretations according to which BB(n) isn't well-defined are simply wrong. If we're unwilling to say that there's a fact of the matter about whether a given TM halts or runs forever on a blank tape, then there also need not be any fact of the matter about Goldbach's Conjecture, the Riemann Hypothesis, or any other arithmetical statement. Or rather, it's only a proof or disproof that would create a fact of the matter about these statements. But why on earth would we want to talk in such a convoluted way--one, indeed, that seems to lead to an infinite regress, where there need not even be a fact of the matter about whether a given statement is provable, whether it's provable that it's provable, and so on? Why not just distinguish the set of statements that have definite truth-values (which includes, at the least, all arithmetical statements), from the smaller set of statements that have definite truth-values that we can prove from a given system of axioms? That, at any rate, was Godel's position, and he was right. 14. Josh Jordan Says: Comment #14 August 31st, 2022 at 11:23 am dankane #10: Why do you need ZFC to define what it means for a Turing machine to run forever? You should be able to define that even in Peano Arithmetic with something like: a machine halts on a tape if there exists a natural number N such that the machine is in the halt state after N steps (starting with the initial tape). Now Peano Arithmetic may not be able to prove that a particular machine runs forever, but that's a separate issue from whether halting is well-defined in the first place. 15. Scott Says: Comment #15 August 31st, 2022 at 11:34 am Josh Jordan #14: Dan would presumably reply that in PA, you can't distinguish whether N is a standard or a nonstandard integer. The response to that is that if you talk about arithmetic in the straightforward, realist way that Godel did and I do, then there's no need to treat "nonstandard integers" as anything more important than artifacts of the incompleteness of various formal systems. Or rather: if you didn't already have a clear enough conception of what a "standard positive integer" was, prior to any formal system, then why were you doing math in the first place? For that matter, why did you even have a clear conception of what a formal system was? 16. dubious Says: Comment #16 August 31st, 2022 at 12:36 pm Nick Drozd #9: What you write depends on unbounded external information: accepted definitions and notations. This would include even the symbols you can write. What if we define `BB_n (m)` as `BB(BB(BB...(m))`? What if we come up with something else that in turn uses this? I take "index card" to be a constraint intended to make one think sooner of better options that a long sequence of 9s. 17. dankane Says: Comment #17 August 31st, 2022 at 12:51 pm Scott #13: In order for those statements to have definite truth values, you need to first specify exactly what model of the natural numbers you are talking about. For any given model of PA, Goldbach is either definitively true or definitively false, but given that we don't know a proof or disproof it is plausible that there are valid models in both camps. If this were known to be true, the formalist response to the question "is every even integer at least 4 the sum of two primes" would be "what exactly do you mean by 'integer'?" Now for statements about the integers, there is at least a reasonable philosophical argument that there really is a natural set of natural numbers that we just can't uniquely specify using any decidable set of axioms. However, for things like the continuum hypothesis, it seems like whether or not it is true really does depend on what exactly you mean by a set. 18. asdf Says: Comment #18 August 31st, 2022 at 1:01 pm Pku #8, I think if M is a 1000 state TM, then there is an obvious 1001 state TM whose initial state simply jumps to the initial state of the 1000 state TM. So if the longest running halting 1000 state TM halts after N steps, the corresponding 1001 state TM halts after N+1 steps. Therefore BB(1001) is least 1 greater than BB(1000). 19. Scott Says: Comment #19 August 31st, 2022 at 1:17 pm dankane #17: Already addressed the point about nonstandard models (see comment #15). When people say "integer," it should always be understood to mean "standard integer" unless specified otherwise. Now for statements about the integers, there is at least a reasonable philosophical argument that there really is a natural set of natural numbers that we just can't uniquely specify using any decidable set of axioms. I'd say not merely "reasonable," but utterly compelling! Again: if this weren't true, then why should we even trust our manipulations of first-order statements, which already presuppose an understanding of basic arithmetic (e.g., to check whether the parentheses are balanced or not)? In this way, the extreme formalist position, the one that denies the reality even of N, seems to me to collapse in internal inconsistency. In other words: it's simply a mistake to think that a formal system like PA could "make the positive integers meaningful," and not only because of Godel. If the positive integers weren't already meaningful, then we couldn't even work sensibly with PA itself. However, for things like the continuum hypothesis, it seems like whether or not it is true really does depend on what exactly you mean by a set. Aha, here I completely agree with you! Note, in particular, that my "sawing off the branch you're sitting on" argument no longer applies once we're dealing with transfinite statements like CH, which could indeed be plausibly argued to have no meaning outside the formal systems we use to discuss them. Of course, this has no effect on the well-definedness of the BB function (by, for example, the Shoenfield Absoluteness Theorem, which shows that the truth or falsehood of statements like AC or CH has no effect on purely arithmetical questions). 20. Shawn Ligocki Says: Comment #20 August 31st, 2022 at 1:49 pm I can slightly lower the upper bound for Ackermann dominance: $$ BB(16) >> A(16) $$ Specifically, Daniel Nagaj found a 16-stage TM which runs more than Graham's number steps (\(\approx A^{64}(4) >> A(16)\)). I wrote up a detailed analysis last month : https:// www.sligocki.com/2022/07/11/bb-16-graham.html . This upper bound could be easily lowered several more steps by simplifying this machine since beating Ackermann is much easier than beating Graham's number. As for prediction on the actual value where BB passes A, I agree with Scott's prediction that \(BB(7) > A(7) \approx 2\uparrow^5 10\) and could certainly believe that \(BB(6) > A(6) \approx 2\ uparrow^4 9\) . However, I'm very worried we will never be able to prove these things. For example, in April I found some BBB(5) (Beeping Busy Beaver) machines that seem like they will probably quasihalt, but require solving a Collatz-like problem in order to actually prove. If they do quasihalt, they would be the current BBB(5) champions. (See https://www.sligocki.com/2022/04/03/ mother-of-giants.html ). I expect this same sort of problem to come up in BB(6) or BB(7) and then we'll need some new math to make any progress! 21. dankane Says: Comment #21 August 31st, 2022 at 2:01 pm Scott #19: You can check whether parentheses are balanced or not without knowing exactly which model of PA you are working in. The truth of any statement of the form "Turing machine T on input X runs for exactly N rounds and returns Y" should be independent of your model of arithmetic. In fact, you can do the kinds of finitistic manipulations needed to check proofs in PA without using anywhere near the full power of PA (just like you *also* don't need to use ZFC to check the validity of proofs). As for whether you should always be assumed to be talking about the "standard integers", the issue is that actually defining what you mean by the "standard integers" is impossible to do rigorously. 22. Scott Says: Comment #22 August 31st, 2022 at 2:38 pm Shawn Ligocki #20: Thanks so much for the updates!! I completely agree that determining BB(6) or BB(7) would surely require solving ridiculously-hard Collatz-like problems, but what about just proving that they dominate A(6) or A(7), if that's indeed the case? 23. Scott Says: Comment #23 August 31st, 2022 at 2:51 pm dankane #21: You can check whether parentheses are balanced or not without knowing exactly which model of PA you are working in. The truth of any statement of the form "Turing machine T on input X runs for exactly N rounds and returns Y" should be independent of your model of arithmetic. So maybe the core of the matter is that I've never understood the point of denying the Law of the Excluded Middle. If there's no n for which it's a fact that my TM halts in n steps, then I'm just going to go ahead and declare it a fact that my TM never halts--regardless of whether that fact can ever be known to humans. Do you agree that, once we're willing to make that move, we're then basically Platonists about N? As for whether you should always be assumed to be talking about the "standard integers", the issue is that actually defining what you mean by the "standard integers" is impossible to do rigorously. My answer, again, is that the goal is not merely impossible, but misguided. I.e., even supposing there were first-order axioms that picked out N and only N, a skeptic could then object that you didn't define the primitives of first-order logic in terms of yet more basic concepts, and so on, trapping you in an infinite regress. For this reason, I maintain that we might as well start with N, a clear-enough conception of which appears as soon as the Sumerians (or a toddler) start engaging in mathematical reasoning at all. 24. dankane Says: Comment #24 August 31st, 2022 at 2:59 pm Scott #23: This isn't the law of the excluded middle, which is about being able to prove "X OR (NOT X)" whether or not one can prove either "X" or prove "NOT X". This is about omega-completeness. And the issue of course is what do you mean by when you say that *for each n* it is a theorem that your TM doesn't halt in n steps. As for the naive conception of the integers, I'm not convinced that the ancient Summarians or toddlers have a conception that allows them to think about 10^10^10^10^10^10^10^10^10^10^10^10^10^10^10 in a way that usefully distinguishes it from a supernatural number. 25. Scott Says: Comment #25 August 31st, 2022 at 3:13 pm dankane #24: Alright then, the "generalized" Law of the Excluded Middle, which you can't actually apply as an inference rule (since it involves countably many input statements) but which nevertheless holds Platonically. If I couldn't even say that any given TM either halts or doesn't halt, then I'd give up and not even try to do math or TCS. But I think we've already made our respective positions clear! 26. asdf Says: Comment #26 August 31st, 2022 at 3:41 pm Dsnkane #21, whether the TM halts can depend on your model of PA. Maybe it does not halt in the standard model, but halts after N steps in a nonstandard model, where N is a nonstandard number. 27. Nick Drozd Says: Comment #27 August 31st, 2022 at 3:58 pm dankane #21 As for whether you should always be assumed to be talking about the "standard integers", the issue is that actually defining what you mean by the "standard integers" is impossible to do rigorously. They may be impossible to define rigorously, but they can certainly be defined in an I-know-it-when-I-see-it sense. Here are some of the official rules of the Busy Beaver game, as defined by Rado: iii. [The contestant] submits their entry, as well as the shift-number s, to any member (in good standing) of the International Busy Beaver Club. iv. The umpire first verifies that the entry actually stops exactly after s steps. Note that this is a decidable issue; the umpire merely operates the entry, persisting through not more than the specified number s of shifts. If the entry fails to stop after s shifts, it is rejected... An entry program has to be accompanied by a number, and the program has to halt within that many steps. I can tell you that if you attempt to submit a nonstandard number, the International Busy Beaver Club will not be impressed. How would you even specify it? Is it possible to meaningfully refer to a particular nonstandard number? 28. Mario Says: Comment #28 August 31st, 2022 at 4:08 pm How long does it take to simulate the current BB(5) champion? I have been wondering this since the present champion is at 47,176,870 steps, which is big, but not unreasonable big considering modern hardware. Of course, I have dozens of minutes in this subject so I may have missed something. 29. Ben Says: Comment #29 August 31st, 2022 at 4:12 pm pku #8 It is provable that BB(n) < BB(n+1) - just take the busy beaver for n and add a starting state that transitions into it. But if you have 2 slightly different formal machines, it is likely impossible to prove whether the variant of BB for the one machine is larger or smaller than the variant of BB for the other machine. Scott #13 We disagree on philosophy. In particular I believe that concepts are only meaningful to the extent that we can understand them. Formalization is a method of understanding. Therefore finite is only a meaningful concept to the extent that we can formalize it. BB(n) requires us to accept the finiteness or not of something for which a human-understandable formalization cannot possibly exist. This is as meaningless a concept as asking whether the omnipotence of God allows Him to make a rock that He can't move. And my invocation of God is relevant. Godel, who you invoked, firmly believed in the existence of God, and settled the question of what was REALLY true on God's infinite wisdom. As an atheist, this approach to accepting infinite and unknowable things as facts is not something I can accept. 30. Shawn Ligocki Says: Comment #30 August 31st, 2022 at 4:28 pm Scott #22 Yeah, I certainly agree that proving that BB(n) > A(n) is much easier than proving the exact value of BB(n) (or even evaluating the runtime of the longest TM if the Busy Beaver God hands it to you). My concern is: What if BB(6) > A(6), but all 6-state TMs which run longer than A(6) have some complex Collatz-like behavior that makes them unanalyzable to us for the foreseeable future? I think it could go either way. As it is, we sort of got "lucky" with the current BB(6) champion. It happened to have rules that we were able to accelerate using Euler's totient theorem magic. But if you tweak those rules slightly you get the "Mother of Giants" type stuff that will require solving Collatz-like problems. Of course, when I say that we were lucky, I really mean that we were only able to search effectively in the space of machines which could be accelerated like this. Pavel has said that he thinks that we might have found all the machines which were acceleratable using this procedure in the 6-state space, so my concern is that most/many of the remaining machines that beat it might be "Mother of Giants" types. In other words, perhaps BB(6) > A(6), but maybe the best we can do is prove BB(8) > A(8) without having to solve a Collatz-like problem. Of course, who knows, maybe next year, someone will be able to find an analyzable TM that beats A(6) 31. Scott Says: Comment #31 August 31st, 2022 at 4:30 pm Ben #29: I enthusiastically endorse the motto of Paul Erdos: "You don't have to believe in God, but you should believe in the Book" (the one wherein God records the most beautiful proof of each theorem). More seriously, though, regardless of the Platonic definiteness of the BB function, would you at least agree that there's a clear meaning to statements like "BB(5)>=47,000,000" or "BB(n+1)>BB(n) for all n" or "BB(1000) is independent of ZFC," and that we can know each of these statements to be true by means of proving them? If you don't, then your philosophy actually gets in the way of (a corner of) my mathematical research, so I have no choice but to fight back! 32. Scott Says: Comment #32 August 31st, 2022 at 4:33 pm Mario #28: Simulating the current BB(5) champion is easy enough that I was able to do it in about 10 seconds on my laptop, using QBasic. If you want to be precise, though, it takes 47,176,870 Turing machine steps. 33. Shawn Ligocki Says: Comment #33 August 31st, 2022 at 4:33 pm Mario #28 I can simulate the 5-state champion in 0.2s. Simulating it is easy, but proving that no other TM halts at a later time, that is the trick! At this point I have about 7500 5-state TMs that have not been proven to ever halt. Maybe about 100 are really quite hard for a human to figure out. The concern is that one of these might run a googolplex steps and then halt or something similar. 34. Justin Kee Says: Comment #34 August 31st, 2022 at 4:55 pm Scott, thanks for the answer to #3 above. I am trying to understand what process causes that TM to actually halt. From the linked page, it appears that there is some modulo mathematics going on and when the remainder is 0 the TM takes the branch into the halting state. Would that be a fair assessment? Also, the decrementing of the exponents in the values of A sub n and K sub n, in the chart under the section Finishing Evaluation, reminds me of the decreasing ordinals used to demonstrate that the generalized Goodstein sequence terminates, even if that fact is unprovable in ordinary arithmetic. Would that be roughly analogous here? Disclosure: I am not a mathematician by any stretch. 35. Scott Says: Comment #35 August 31st, 2022 at 5:19 pm Justin Kee #34: I'm going to hand you off to Shawn Ligocki or the other experts on this thread--both because (1) while I took the time to understand exactly what the BB(5) champ is doing, I haven't yet taken that time for the BB(6) champ, and because (2) I just arrived in Toronto for the CQIQC conference--my first trip to Canada since before covid--and I need to run to the banquet! Leave a Reply You can use rich HTML in comments! You can also use basic TeX, by enclosing it within $$ $$ for displayed equations or \( \) for inline equations. Comment Policies: 1. All comments are placed in moderation and reviewed prior to appearing. 2. You'll also be sent a verification email to the email address you provided. YOU MUST CLICK THE LINK IN YOUR VERIFICATION EMAIL BEFORE YOUR COMMENT CAN APPEAR. WHY IS THIS BOLD, UNDERLINED, ALL-CAPS, AND IN RED? BECAUSE PEOPLE ARE STILL FORGETTING TO DO IT. 3. Comments can be left in moderation for any reason, but in particular, for ad-hominem attacks, hatred of groups of people, snide and patronizing tone, trollishness, disingenuousness, or presumptuousness (e.g., linking to a long paper or article and challenging me to respond to it). 4. Even when no individual comment violates policy, when there are dozens of comments from a single commenter hammering home the same few themes, and the commenter shows no interest in changing their views or learning from anyone else, the commenter will receive a warning followed by a 3-month ban. 5. Whenever I'm in doubt, I'll forward comments to Shtetl-Optimized Committee of Guardians, and respect SOCG's judgments on whether those comments should appear. 6. I sometimes accidentally miss perfectly reasonable comments in the moderation queue, or they get caught in the spam filter. If you feel this may have been the case with your comment, shoot me an email. [ ] Name (required) [ ] Mail (will not be published) (required) [ ] Website [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [Submit Comment] [ ] [ ] [ ] [ ] [ ] [ ] [ ] D[ ] --------------------------------------------------------------------- Shtetl-Optimized is proudly powered by WordPress Entries (RSS) and Comments (RSS).