47,176,870

July 4, 2024 1:45 AM

The search for the busy beaver is ultimately a trophy hunt. The specific value of BB(5) doesn’t have applications in other areas of computer science. But for busy beaver hunters, the hard-fought victory over mathematical impossibility is its own reward. It may be the last battle they’ll ever win. from With Fifth Busy Beaver, Researchers Approach Computation’s Limits [Quanta; ungated]
posted by chavenet (9 comments total)

The bbchallenge announcement post also has lots of information.
posted by Rhomboid at 2:59 AM on July 4 [3 favorites]

“Obviously, you cannot do this,” Ligocki said. “And even if you could, no one would believe you.”
*closes notebook, walks away*
posted by HearHere at 3:55 AM on July 4 [2 favorites]

This was a delightful read that took me back to university when I was a (fairly average) student of computer science.
posted by freethefeet at 4:14 AM on July 4 [2 favorites]

Love this kind of thing - my MSc was in computational theory so familiar with Coq but busy beaver numbers are new to me - thx for post.
posted by whatevernot at 4:45 AM on July 4 [2 favorites]

my usual response to reading this kind of stuff below a glancing depth.
posted by lalochezia at 5:02 AM on July 4 [4 favorites]

Fascinating stuff, and an excellent exposition of it. Back in the '00s, I took a class on the theory of computation from one of my physics professors in graduate school, who had become fascinated by it in his attempt to understand quantum computation. (He later published his lecture notes.)

I remember my mind being blown by the concept of an uncomputable number back at the time. The proof that such numbers exist — in fact, that most numbers are incomputable — is pretty straightforward if you understand the concept of countable & uncountable sets. But somehow, saying that "there is no computer program that can calculate this number to an arbitrary precision" feels really weird.
posted by Johnny Assay at 5:18 AM on July 4 [6 favorites]

Thanks for posting this, I got sucked into it yesterday. The most interesting parts of this to me are the cryptids, simple Turing machines that calculate various unproven mathematical hypotheses. If the machine ever terminates, the hypothesis is disproven. But since the hypothesis has not yet been proven, we don't know if the machine will run forever either, so it is in that liminal state of infinite perplexion. We just dunno!
posted by seanmpuckett at 6:10 AM on July 4 [7 favorites]

That was an excellent article. Thank you for posting it.
posted by Tell Me No Lies at 6:14 AM on July 4 [3 favorites]

I love that some random anonymous guy shows up and codifies everything in like a month and then disappears.
posted by Literaryhero at 11:51 PM on July 4 [1 favorite]