https://www.scottaaronson.com/blog/?p=5661 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! --------------------------------------------------------------------- << Steven Weinberg (1933-2021): a personal view Striking new Beeping Busy Beaver champion For the past few days, I was bummed about the sooner-than-expected loss of Steven Weinberg. Even after putting up my post, I spent hours just watching old interviews with Steve on YouTube and reading his old essays for gems of insight that I'd missed. (Someday, I'll tackle Steve's celebrated quantum field theory and general relativity textbooks ... but that day is not today.) Looking for something to cheer me up, I was delighted when Shtetl-Optimized reader Nick Drozd reported a significant new discovery in BusyBeaverology--one that, I'm proud to say, was directly inspired by my Busy Beaver survey article from last summer (see here for blog post). Recall that BB(n), the n^th Busy Beaver number (technically, "Busy Beaver shift number"), is defined as the maximum number of steps that an n-state Turing machine, with 1 tape and 2 symbols, can make on an initially all-0 tape before it invokes a Halt transition. Famously, BB(n) is not only uncomputable, it grows faster than any computable function of n--indeed, computing anything that grows as quickly as Busy Beaver is equivalent to solving the halting problem. As of 2021, here is the extent of human knowledge about concrete values of this function: * BB(1) = 1 (trivial) * BB(2) = 6 (Lin 1963) * BB(3) = 21 (Lin 1963) * BB(4) = 107 (Brady 1983) * BB(5) >= 47,176,870 (Marxen and Buntrock 1990) * BB(6) > 7.4 x 10^36,534 (Kropitz 2010) * BB(7) > 10^2x10^10^10^18,705,352 ("Wythagoras" 2014) As you can see, the function is reasonably under control for n<=4, then "achieves liftoff" at n=5. In my survey, inspired by a suggestion of Harvey Friedman, I defined a variant called Beeping Busy Beaver, or BBB. Define a beeping Turing machine to be a TM that has a single designated state where it emits a "beep." The beeping number of such a machine M, denoted b(M), is the largest t such that M beeps on step t, or [?] if there's no finite maximum. Then BBB(n) is the largest finite value of b(M), among all n-state machines M. I noted that the BBB function grows uncomputably even given an oracle for the ordinary BB function. In fact, computing anything that grows as quickly as BBB is equivalent to solving any problem in the second level of the arithmetical hierarchy (where the computable functions are in the zeroth level, and the halting problem is in the first level). Which means that pinning down the first few values of BBB should be even more breathtakingly fun than doing the same for BB! In my survey, I noted the following four concrete results: * BBB(1) = 1 = BB(1) * BBB(2) = 6 = BB(2) * BBB(3) >= 55 > 21 = BB(3) * BBB(4) >= 2,819 > 107 = BB(4) The first three of these, I managed to get on my own, with the help of a little program I wrote. The fourth one was communicated to me by Nick Drozd even before I finished my survey. So as of last summer, we knew that BBB coincides with the ordinary Busy Beaver function for n=1 and n=2, then breaks away starting at n= 3. We didn't know how quickly BBB "achieves liftoff." But Nick continued plugging away at the problem all year, and he now claims to have resolved the question. More concretely, he claims the following two results: * BBB(3) = 55 (via exhaustive enumeration of cases) * BBB(4) >= 32,779,478 (via a newly-discovered machine) For more, see Nick's announcement on the Foundations of Mathematics email list, or his own blog post. Nick actually writes in terms of yet another Busy Beaver variant, which he calls BLB, or "Blanking Beaver." He defines BLB(n) to be the maximum finite number of steps that an n-state Turing machine can take before it first "wipes its tape clean"--that is, sets all the tape squares to 0, as they were at the very beginning of the computation, but as they were not at intermediate times. Nick has discovered a 4-state machine that takes 32,779,477 steps to blank out its tape, thereby proving that * BLB(4) >= 32,779,477. Nick's construction, when investigated, turns out to be based on a "Collatz-like" iterative process--exactly like the BB(5) champion and most of the other strong Busy Beaver contenders currently known. A simple modification of his construction yields the lower bound on BBB. Note that the Blanking Beaver function does not have the same sort of super-uncomputable growth that Beeping Busy Beaver has: it merely grows "normally" uncomputably fast, like the original BB function did. Yet we see that BLB, just like BBB, already "achieves liftoff" by n=4, rather than n=5. So the real lesson here is that 4-state Turing machines can already do fantastically complicated things on blank tapes. It's just that the usual definitions of the BB function artificially prevent us from seeing that; they hide the uncomputable insanity until we get to 5 states. This entry was posted on Tuesday, July 27th, 2021 at 5:43 pm and is filed under Announcements, Procrastination. 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. 16 Responses to "Striking new Beeping Busy Beaver champion" 1. Bram Cohen Says: Comment #1 July 27th, 2021 at 6:44 pm Those two numbers are suspiciously off by one. Are they the same machine? 2. Charlie Harrison Says: Comment #2 July 27th, 2021 at 8:23 pm I was confused about how both BBB(n) and BLB(n) were not bounded above by BB(n) until I clicked through to Nick's announcement and realized none of these machines will halt 3. Scott Says: Comment #3 July 27th, 2021 at 8:38 pm Bram #1: I believe the same machine with a trivial modification (designating one of the states as a beep state). If Nick is reading this, hopefully he can explain how the two bounds come to differ by 1. 4. Nick Drozd Says: Comment #4 July 27th, 2021 at 10:12 pm Bram #1, Scott #3 It's the same machine, and it exhibits both behaviors at different times. The tape is blank after 32,779,477 steps, and then it takes one more step and then gets stuck in one state forever. So the number for measuring quasihalting is one more than the one for measuring tape-blanking. ("Quasihalting" is the word I've been using instead of "designated-beep-state-stops-beeping".) This is not always the case. The BLB(3) champion quasihalts after 6 steps, but leaves the tape blank after 34 steps. (If anyone is looking for a Turing machine challenge, try writing that program by hand. Hint: unlike other Busy Beaver champions, this one has a clear modular construction.) If a program exhibits more than one termination condition, which one is the right one to use to describe its behavior? If this new champion program could talk, how would it describe itself? My feeling is that it would say "I verify that a certain strange and uninteresting Collatz-like function will, when applied repeatedly to 2, eventually reaches 0, at which point the tape will be blank." The program doesn't have a plan for what happens after that, or even an understanding that there will be an "after that". The fact that it quasihalts after wiping the tape is like rigor mortis setting in. One reason for thinking this is that the blank tape was how I actually found the thing. Searching for quasihalting programs is unpleasant. The obvious way to do it is to run a list of programs for some number of steps and record the last time each state was hit, and then check the results to see if it looks like any of them are quasihalters. But it's difficult to distinguish quasihalting programs from programs that just haven't reached some period again, and this leads to a lot of false positives. In contrast, the blank tape can be detected with perfect reliability and for practically free. If you were a program and you wanted to be found, erasing the tape would be a good strategy. That sends out a strong clear signal that could actually be received. (You can tell I've been at this too long because I keep ascribing thoughts and desires to programs. And not just any programs, but programs that weren't even written by anybody!) 5. zuminator Says: Comment #5 July 28th, 2021 at 1:37 am Don't be fooled by the lower bound, BBB(4) and BLB(4) likely differ by quite a bit but the ability to calculate the exact values is limited. It's as if some ancient scientist concluded that the number of stars in the sky was at least 1000 and the number of grains of sand in a handful was also at least 1000, because his abacus only went to 1000. His estimates would have technically not been "wrong", but in actuality the numbers are neither close to 1000 nor to each other. 6. TonyK Says: Comment #6 July 28th, 2021 at 4:38 am Scott, I think you have a misprint: is BLB(4) 32,779,447 or 32,779,477? 7. Noah Stephens-Davidowitz Says: Comment #7 July 28th, 2021 at 7:40 am Buzzy Beaver 8. Scott Says: Comment #8 July 28th, 2021 at 7:52 am TonyK #6: Duhhhh, thanks!! Fixed. 9. Scott Says: Comment #9 July 28th, 2021 at 8:00 am zuminator #5: No, in the case at hand we really, genuinely don't yet know whether we're seeing the limits of our abacuses or (close to) the actual limits of what 4-state Turing machines can do. It's like: imagine if, after seeing the 107-step champion for BB (4), someone had sagely said, "don't be fooled by the lower bound! The real value of BB(4) is surely incomprehensibly greater than that." But then no, Allan Brady proved in 1983 that BB(4) simply is 107. Likewise, Nick tells me that he's enumerated cases enough to confirm that BBB(3) simply is 55, the "naive" lower bound that I managed to get with QBasic. As for BLB vs. BBB, we know on abstract grounds that they eventually need to pull away from each other, but there's no good reason why they need to do so by n=4--again, they might or might not. Unlike most of us, Nick is actually putting in the work to find out! 10. fred Says: Comment #10 July 28th, 2021 at 9:59 am Scott, what do you think of the notion of "computational irreducibility" that S. Wolfram is always throwing around https://en.wikipedia.org/wiki/Computational_irreducibility I guess you'll probably say that it's really obvious But I think Wolfram's real claim is that most of the interesting processes (i.e. the emergence of complexity) happening in our physical world are actually like the BB, there's no simpler algorithm that can bypass running the actual thing, step by step. I do wonder: for a given size of automata/programs, what proportion do have that property. But that's probably impossible to answer as well, it's just like asking "what strings of 1 and 0 are random?". 11. Scott Says: Comment #11 July 28th, 2021 at 10:38 am fred #10: Well yes, it is pretty obvious that for a huge number of physical systems, even if we know the dynamical laws and the initial state to suitable precision (which usually we don't), there might be no computational shortcut to predicting the system's behavior, other than just recapitulating its time evolution. A limited amount is gained by giving that observation a name and wrongly claiming to be the first to discover it. Even that, though, is totally different from saying that most physical systems are "like Busy Beaver computations." I don't think that's true at all. Busy Beavers are painstakingly optimized for doing the greatest possible number of things with the least possible number of states. They're wildly atypical among Turing machines, or among physical processes more generally. Indeed, if you choose an n-state Turing machine at random, the probability that it will exhibit "BB(n)-like behavior" is negligibly small, most likely 1/exp(n) for some reasonable formalization of what we mean by "BB(n)-like behavior" (although I don't know how to prove such a statement). That's part of what makes these machines so interesting! 12. Luke W Says: Comment #12 July 28th, 2021 at 11:27 am I have a question about the original Yedida-Aaronson BB(7918) eludes ZFC+SRP paper. I've never quite understood what makes the argument work. It goes: Statement 1: There must be some k such that BB(k) is unknowable in any axiomatic system A. Proof: Assume S1 is false. Therefore, all BB(n) are knowable. There also exists a Turing Machine M such that M halts iff there is a contradiction in A. This machine M has some finite number of states k. But A can't determine the value of BB(k). If it could, A would need to prove M ran forever, which would prove the consistency of A, which violates Godel's Theorem. QED, S1 is true. Why does A determining the value of BB(k) imply A would need to prove M ran forever? 13. Scott Says: Comment #13 July 28th, 2021 at 11:47 am Luke W #12: A needs to prove that M runs forever because, if M halted after some number of steps that was much larger than the supposed Busy Beaver champion, then that champion wouldn't be the champion--M would beat it. In other words, proving the value of BB (n), by its very nature, entails proving that every non-halting n-state Turing machine actually doesn't halt. That includes any machines that enumerate the theorems of some axiomatic system, halting iff they find a contradiction. Incidentally, one should be careful about the quantifiers: the right statement is that for every axiomatic system A, there exists a k such that A can't prove the value of BB(k). Note on the other hand that for every k, there exists an A such that A does prove the value of BB(k). 14. Alex Says: Comment #14 July 28th, 2021 at 12:26 pm 10^(2x10^10^10^18,705,352) is a very funny-looking lower bound, specifically because of the factor of 2 in the exponent. 10^10^10 ^10^18,705,352.0001 is far larger than that, so if the bound had been given as 10^10^10^10^18,705,352, I would assume that of course that's a loose lower bound that almost certainly could be refined to something far larger than 10^(2x10^10^10^18,705,352) if you bothered to take more space to express it. This makes me curious where that 2 came from, and if it's a typo. 15. Scott Says: Comment #15 July 28th, 2021 at 1:23 pm Alex #14: No, it's not a typo, that's just how Wythagoras stated the bound, surely as a byproduct of how it was obtained. I thought of omitting the "2x" when I quoted the bound, since it's so comically irrelevant for numbers of that magnitude, but on further reflection decided just to leave it as it was. 16. LK2 Says: Comment #16 July 28th, 2021 at 1:35 pm ABSOLUTELY fascinating. Even from my point of view which is that of a physicist working on "fundamental" physics. I feel the need to write in C(++) something similar to what you did with Qbasic (wonderful language if my youth..). Leave a Reply Comment Policy: All comments are placed in moderation and reviewed prior to appearing. Comments can be left in moderation for any reason, but in particular, for ad-hominem attacks, hatred of groups of people, or snide and patronizing tone. Also: comments that link to a paper or article and, in effect, challenge me to respond to it are at severe risk of being left in moderation, as such comments place demands on my time that I can no longer meet. You'll have a much better chance of a response from me if you formulate your own argument here, rather than outsourcing the job to someone else. 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. You can now use rich HTML in comments! You can also use basic TeX, by enclosing it within $$ $$ for displayed equations or \( \) for inline equations. [ ] Name (required) [ ] Mail (will not be published) (required) [ ] Website [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [Submit Comment] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] --------------------------------------------------------------------- Shtetl-Optimized is proudly powered by WordPress Entries (RSS) and Comments (RSS).