Shtetl-Optimized

Q1: Who will you be voting for in November?

A: Kamala Harris (and mainstream Democrats all down the ballot), of course.

Q2: Of course?

A: If the alternative is Trump, I would’ve voted for Biden’s rotting corpse. Or for Hunter Biden. Or for…

Q3: Why can’t you see this is just your Trump Derangement Syndrome talking?

A: Look, my basic moral commitments remain pretty much as they’ve been since childhood. Namely, that I’m on the side of reason, Enlightenment, scientific and technological progress, secular government, pragmatism, democracy, individual liberty, justice, intellectual honesty, an American-led peaceful world order, preservation of the natural world, mitigation of existential risks, and human flourishing. (Crazy and radical, I know.)

Only when choosing between candidates who all espouse such values, do I even get the luxury of judging them on any lower-order bits. Sadly, I don’t have that luxury today. Trump’s values, such as they are, would seem to be “America First,” protectionism, vengeance, humiliation of enemies, winning at all costs, authoritarianism, the veneration of foreign autocrats, and the veneration of himself. No amount of squinting can ever reconcile those with the values I listed before.

Q4: Is that all that’s wrong with him?

A: No, there are also the lies, and worst of all the “Big Lie.” Trump is the first president in US history to incite a mob to try to overturn the results of an election. He was serious! He very nearly succeeded, and probably would have, had Mike Pence been someone else. It’s now inarguable that Trump rejects the basic rules of our system, or “accepts” them only when he wins. We’re numb from having heard it so many times, but it’s a big deal, as big a deal as the Civil War was.

Q5: Oh, so this is about your precious “democracy.” Why do you care? Haven’t you of all people learned that the masses are mostly idiots and bullies, who don’t deserve power? As Curtis Yarvin keeps trying to explain to you, instead of “democracy,” you should want a benevolent king or dictator-CEO, who could offer a privileged position to the competent scientists like yourself.

A: Yeah, so how many examples does history furnish where that worked out well? I suppose you might make a partial case for Napoleon, or Ataturk? More to the point: even if benevolent, science-and-reason-loving authoritarian strongmen are possible in theory, do you really expect me to believe that Trump could be one of them? I still love how Scott Alexander put it in 2016:

Can anyone honestly say that Trump or his movement promote epistemic virtue? That in the long-term, we’ll be glad that we encouraged this sort of thing, that we gave it power and attention and all the nutrients it needed to grow? That the road to whatever vision of a just and rational society we imagine, something quiet and austere with a lot of old-growth trees and Greek-looking columns, runs through LOCK HER UP?

I don’t like having to vote for the lesser of two evils. But at least I feel like I know who it is.

Q6: But what about J. D. Vance? He got his start in Silicon Valley, was championed by Peter Thiel, and is obviously highly intelligent. Doesn’t he seem like someone who might listen to and empower tech nerds like yourself?

A: Who can say what J. D. Vance believes? Here are a few choice quotes of his from eight years ago:

I’m obviously outraged at Trump’s rhetoric, and I worry most of all about how welcome Muslim citizens feel in their own country. But I also think that people have always believed crazy shit (I remember a poll from a few years back suggesting that a near majority of democratic voters blame ‘the Jews’ for the financial crisis). And there have always been demagogues willing to exploit the people who believe crazy shit.

The more white people feel like voting for trump, the more black people will suffer. I really believe that.

[Trump is] just a bad man. A morally reprehensible human being.

To get from that to being Trump’s running mate is a Simone-Biles-like feat of moral acrobatics. Vance reminds me of the famous saying by L. Ron Hubbard from his pre-Dianetics days: “If a man really wants to make a million dollars, the best way would be to start his own religion.” (And I feel like Harris’s whole campaign strategy should just be to replay Vance’s earlier musings in wall-to-wall ads while emphasizing her agreement with them.) No, Vance is not someone I trust to share my values, if he has values at all.

Q7: What about the other side’s values, or lack thereof? I mean, don’t you care that the whole Democratic establishment—including Harris—colluded to cover up that Biden was senile and cognitively unfit to be president now, let alone for another term?

A: Look, we’ve all seen what happens as a relative gets old. It’s gradual. It’s hard for anyone to say at which specific moment they can no longer drive a car, or be President of the United States, or whatever. This means that I don’t necessarily read evil intent into the attempts to cover up Biden’s decline—merely an epic, catastrophic failure of foresight. That failure of foresight itself would’ve been a huge deal in normal circumstances, but these are not normal circumstances—not if you believe, as I do, that the alternative is the beginning of the end of a 250-year-old democratic experiment.

Q8: Oh stop being so melodramatic. What terrible thing happened to you because of Trump’s first term? Did you lose your job? Did fascist goons rough you up in the street?

A: Well, my Iranian PhD student came close to having his visa revoked, and it became all but impossible to recruit PhD students from China. That sucked, since I care about my students’ welfare like I care about my own. Also, the downfall of Roe v. Wade, which enabled Texas’ draconian new abortion laws, made it much harder for us to recruit faculty at UT Austin. But I doubt any of that will impress you. “Go recruit American students,” you’ll say. “Go recruit conservative faculty who are fine with abortion being banned.”

The real issue is that Trump was severely restrained in his first term, by being surrounded by people who (even if, in many cases, they started out loyal to him) were also somewhat sane and valued the survival of the Republic. Alas, he learned from that, and he won’t repeat that mistake the next time.

Q9: Why do you care so much about Trump’s lies? Don’t you realize that all politicians lie?

A: Yes, but there are importantly different kinds of lies. There are white lies. There are scheming, 20-dimensional Machiavellian lies, like a secret agent’s cover story (or is that only in fiction?). There are the farcical, desperate, ever-shifting lies of the murderer to the police detective or the cheating undergrad to the professor. And then there are the lies of bullies and mob bosses and populist autocrats, which are special and worse.

These last, call them power-lies, are distinguished by the fact that they aren’t even helped by plausibility. Often, as with conspiracy theories (which strongly overlap with power-lies), the more absurd the better. Obama was born in Kenya. Trump’s crowd was the biggest in history. The 2020 election was stolen by a shadowy conspiracy involving George Soros and Dominion and Venezuela.

The central goal of a power-lie is just to demonstrate your power to coerce others into repeating it, much like with the Party making Winston Smith affirm 2+2=5, or Petruchio making Katharina call the sun the moon in The Taming of the Shrew. A closely-related goal is as a loyalty test for your own retinue.

It’s Trump’s embrace of the power-lie that puts him beyond the pale for me.

Q10: But Scott, we haven’t even played our “Trump” card yet. Starting on October 7, 2023, did you not witness thousands of your supposed allies, the educated secular progressives on “the right side of history,” cheer the sadistic mass-murder of Jews—or at least, make endless excuses for those who did? Did this not destabilize your entire worldview? Will you actually vote for a party half of which seems at peace with the prospect of your family members’ physical annihilation? Or will you finally see who your real friends now are: Arkansas MAGA hillbillies who pray for your people’s survival?

A: Ah, this is your first slash that’s actually drawn blood. I won’t pretend that the takeover of part of the US progressive coalition by literal Hamasniks hasn’t been one of the most terrifying experiences of my life. Yes, if I had to be ruled by either (a) a corrupt authoritarian demagogue or (b) an idiot college student chanting for “Intifada Revolution,” I’d be paralyzed. So it’s lucky that I don’t face that choice! I get to vote, once more, for a rather boring mainstream Democrat—alongside at least 70% of American Jews. The idea of Harris as an antisemite would be ludicrous even if she didn’t have a Jewish husband or wasn’t strongly considering a pro-Israel Jew as her running mate.

Q11: Sure, Kamala Harris might mouth all the right platitudes about Israel having a right to defend itself, but she’ll constantly pressure Israel to make concessions to Hamas and Hezbollah. She’ll turn a blind eye to Iran’s imminent nuclearization. Why don’t you stay up at night worrying that, if you vote for a useful idiot like her, you’ll have Israel’s annihilation and a second Holocaust on your conscience forever?

A: Look, oftentimes—whenever, for example, I’m spending hours reading anti-Zionists on Twitter—I feel like there’s no limit to how intensely Zionist I am. On reflection, though, there is a limit. Namely, I’m not going to be more Zionist than the vast majority of my Israeli friends and colleagues—the ones who served in the IDF, who in some cases did reserve duty in Gaza, who prop up the Israeli economy with their taxes, and who will face the consequences of whatever happens more directly than I will. With few exceptions, these friends despise the Trump/Bibi alliance with white-hot rage, and they desperately want more moderate leadership in both countries.

Q12: Suppose I concede that Kamala is OK on Israel. We both know that she’s not the future of the Democratic Party, any more than Biden is. The future is what we all saw on campuses this spring. “Houthis Houthis make us proud, turn another ship around.” How can you vote for a party whose rising generation seems to want you and your family dead?

A: Let me ask you something. When Trump won in 2016, did that check the power of the campus radicals? Or as Scott Alexander prophesied at the time, did it energize and embolden them like nothing else, by dramatically confirming their theology of a planet held hostage by the bullying, misogynistic rich white males? I fundamentally reject your premise that, if I’m terrified of crazy left-wing extremists, then a good response is to vote for the craziest right-wing extremists I can find, in hopes that the two will somehow cancel each other out. Instead I should support a coherent Enlightenment alternative to radicalism, or the closest thing to that available.

Q13: Even leaving aside Israel, how can you not be terrified by what the Left has become? Which side denounced you on social media a decade ago, as a misogynist monster who wanted all women to be his sex slaves? Which side tried to ruin your life and career? Did we, the online rightists, do that? No. We did not. We did nothing worse to you than bemusedly tell you to man up, grow a pair, and stop pleading for sympathy from feminists who will hate you no matter what.

A: I’ll answer with a little digression. Back in 2017, when Kamala Harris was in the Senate, her office invited me to DC to meet with them to provide advice about the National Quantum Initiative Act, which Kamala was then spearheading. Kamala herself sent regrets that she couldn’t meet me, because she had to be at the Kavanaugh hearings. I have (nerdy, male) friends who did meet her about tech policy and came away with positive impressions.

And, I dunno, does that sound like someone who wants me dead for the crime of having been born a nerdy heterosexual male? Or having awkwardly and ineptly asked women on dates, including the one who became my wife? OK, maybe Amanda Marcotte wants me dead for those crimes. Maybe Arthur Chu does (is he still around?). Good that they’re not running for president then.

Q14: Let me try one more time to show you how much your own party hates you. Which side has been at constant war against the SAT and other standardized tests, and merit-based college admissions, and gifted programs, and academic tracking and acceleration, and STEM magnet schools, and every single other measure by which future young Scott Aaronsons (and Saket Agrawals) might achieve their dreams in life? Has that been our side, or theirs?

A: To be honest, I haven’t seen the Trump or Harris campaigns take any position on any of these issues. Even if they did, there’s very little that the federal government can do: these battles happen in individual states and cities and counties and universities. So I’ll vote for Harris while continuing to advocate for what I think is right in education policy.

Q15: Can you not see that Kamala Harris is a vapid, power-seeking bureaucratic machine—that she has no fixed principles at all? For godsakes, she all but condemned Biden as a racist in the 2020 primary, then agreed to serve as his running mate!

A: I mean, she surely has more principles than Vance does. As far as I can tell, for example, she’s genuinely for abortion rights (as I am). Even if she believed in nothing, though, better a cardboard cutout on which values I recognize are written, than a flesh-and-blood person shouting values that horrify me.

Q16: What, if anything, could Republicans do to get you to vote for them?

A: Reject all nutty conspiracy theories. Fully, 100% commit to the peaceful transfer of power. Acknowledge the empirical reality of human-caused climate change, and the need for both technological and legislative measures to slow it and mitigate its impacts. Support abortion rights, or at least a European-style compromise on abortion. Republicans can keep the anti-wokeness stuff, which actually seems to have become their defining issue. If they do all that, and also the Democrats are taken over by frothing radicals who want to annihilate the state of Israel and abolish the police … that’s, uh, probably the point when I start voting Republican.

Q17: Aha, so you now admit that there exist conceivable circumstances that would cause you to vote Republican! In that case, why did you style yourself “Never-Trump From Here to Eternity”?

A: Tell you what, the day the Republicans (and Trump himself?) repudiate authoritarianism and start respecting election outcomes, is the day I’ll admit my title was hyperbolic.

Q18: In the meantime, will you at least treat us Trump supporters with civility and respect?

A: Not only does civil disagreement not compromise any of my values, it is a value to which I think we should all aspire. And to whatever extent I’ve fallen short of that ideal—even when baited into it—I’m sorry and I’ll try to do better. Certainly, age and experience have taught me that there’s hardly anyone so far gone that I can’t find something on which I agree with them, while disagreeing with most of the rest of the world.

Update (July 24): Remember the quest that Adam Yedidia and I started in 2016, to find the smallest n such that the value of the n^th Busy Beaver number can be proven independent of the axioms of ZF set theory? We managed to show that BB(8000) was independent. This was later improved to BB(745) by Stefan O’Rear and Johannes Riebel. Well, today Rohan Ridenour writes to tell me that he’s achieved a further improvement to BB(643). Awesome!

---

With yesterday’s My Prayer, for the first time I can remember in two decades of blogging, I put up a new post with the comments section completely turned off. I did so because I knew my nerves couldn’t handle a triumphant interrogation from Trumpist commenters about whether, in the wake of their Messiah’s (near-)blood sacrifice on behalf of the Nation, I’d at last acquiesce to the dissolution of America’s constitutional republic and its replacement by the dawning order: one where all elections are fraudulent unless the MAGA candidate wins, and where anything the leader does (including, e.g., jailing his opponents) is automatically immune from prosecution. I couldn’t handle it, but at the same time, and in stark contrast to the many who attack from my left, I also didn’t care what they thought of me.

With hindsight, turning off comments yesterday might be the single best moderation decision I ever made. I still got feedback on what I’d written, on Facebook and by email and text message and in person. But this more filtered feedback was … thoughtful. Incredibly, it lowered the stress that I was feeling rather than raising it even higher.

For context, I should explain that over the past couple years, one or more trolls have developed a particularly vicious strategy against me. Below my every blog post, even the most anodyne, a “new” pseudonymous commenter shows up to question me about the post topic, in what initially looks like a curious, good-faith way. So I engage, because I’m Scott Aaronson and that’s what I do; that’s a large part of the value I can offer the world.

Then, only once a conversation is underway does the troll gradually ratchet up the level of crazy, invariably ending at some place tailor-made to distress me (for example: vaccines are poisonous, death to Jews and Israel, I don’t understand basic quantum mechanics or computer science, I’m a misogynist monster, my childhood bullies were justified and right). Of course, as soon as I’ve confirmed the pattern, I send further comments straight to the trash. But the troll then follows up with many emails taunting me for not engaging further, packed with farcical accusations and misreadings for me to rebut and other bait.

Basically, I’m now consistently subjected to denial-of-service attacks against my open approach to the world. Or perhaps I’ve simply been schooled in why most people with audiences of thousands or more don’t maintain comment sections where, by default, they answer everyone! And yet it’s become painfully clear that, as long as I maintain a quasi-open comment section, I’ll feel guilty if I don’t answer everyone.

---

So without further ado, I hereby announce my new comment policy. Henceforth all comments to Shtetl-Optimized will be treated, by default, as personal missives to me—with no expectation either that they’ll appear on the blog or that I’ll reply to them.

At my leisure and discretion, and in consultation with the Shtetl-Optimized Committee of Guardians, I’ll put on the blog a curated selection of comments that I judge to be particularly interesting or to move the topic forward, and I’ll do my best to answer those. But it will be more like Letters to the Editor. Anyone who feels unjustly censored is welcome to the rest of the Internet.

The new policy starts now, in the comment section of this post. To the many who’ve asked me for this over the years, you’re welcome!

It is the duty of good people, always and everywhere, to condemn, reject, and disavow the use of political violence.

Even or especially when evildoers would celebrate the use of political violence against us.

It is our duty always to tell the truth, always to play by the rules — even when evil triumphs by lying, by sneeringly flouting every rule.

It appears to be an iron law of Fate that whenever good tries to steal a victory by evil means, it fails. This law is so infallible that any good that tries to circumvent it thereby becomes evil.

When Sam Bankman-Fried tries to save the world using financial fraud — he fails. Only the selfish succeed through fraud.

When kind, nerdy men, in celibate desperation, try to get women to bed using “Game” and other underhanded tactics — they fail. Only the smirking bullies get women that way.

Quantum mechanics is false, because its Born Rule speaks of randomness.

But randomness can’t explain why a bullet aimed at a destroyer of American democracy must inevitably miss by inches, while a bullet aimed at JFK or RFK or MLK or Gandhi or Rabin must inevitably meet its target.

Yet for all that, over the millennia, good has made actual progress. Slavery has been banished to the shadows. Children survive to adulthood. Sometimes altruists become billionaires, or billionaires altruists. Sometimes the good guy gets the girl.

Good has progressed not by lucky breaks — for good never gets lucky breaks — but only because the principles of good are superior.

There’s a kind of cosmic solace that could be offered even to the Jewish mother in the gas chamber watching her children take their last breaths, though the mother could be forgiven for rejecting it.

The solace is that good will triumph — if not in the next four years, then in the four years after that.

Or if not in four, then in a hundred.

Or if not in a hundred, then in a thousand.

Or if not in the entire history of life in on this planet, then on a different planet.

Or if not in this universe, then in a different universe.

Let us commit to fighting for good using good methods only. Fate has decreed in any case that, for us, those are the only methods that work.

Let us commit to use good methods only even if it means failure, heartbreak, despair, the destruction of democratic institutions and ecosystems multiplied by a thousand or a billion or any other constant — with the triumph of good only in the asymptotic limit.

Good will triumph, when it does, only because its principles are superior.

Endnote: I’ve gotten some pushback for this prayer from one of my scientific colleagues … specifically, for the part of the prayer where I deny the universal validity of the Born rule. And yet a less inflammatory way of putting the same point would simply be: I am not a universal Bayesian. There are places where my personal utility calculations do a worst-case analysis rather than averaging over possible futures for the world.

Endnote 2: It is one thing to say, never engage in political violence because the expected utility will come out negative. I’m saying something even stronger than that. Namely, even if the expected utility comes out positive, throw away the whole framework of being an expected-utility maximizer before you throw away that you’re never going to endorse political violence. There’s a class of moral decisions for which you’re allowed to use, even commendable for using, expected-utility calculations, and this is outside that class.

Endnote 3: If you thought that Trump’s base was devoted before, now that the MAGA Christ-figure has sacrificed his flesh — or come within a few inches of doing so — on behalf of the Nation, they will go to the ends of the earth for him, as much as any followers did for any ruler in human history. Now the only questions, assuming Trump wins (as he presumably will), are where he chooses to take his flock, and what emerges in the aftermath for what we currently call the United States. I urge my left-leaning American friends to look into second passports. Buckle up, and may we all be here to talk about it on the other end.

Perhaps like the poor current President of the United States, I can feel myself fading, my memory and verbal facility and attention to detail failing me, even while there’s so much left to do to battle the nonsense in the world. I started my career on an accelerated schedule—going to college at 15, finishing my PhD at 22, etc. etc.—and the decline is (alas) also hitting me early, at the ripe age of 43.

Nevertheless, I do seem to remember that this was once primarily a quantum computing blog, and that I was known to the world as a quantum computing theorist. And exciting things continue to happen in quantum computing…

---

First, a company in the UK called Oxford Ionics has announced that it now has a system of trapped-ion qubits in which it’s prepared two-qubit maximally entangled states with 99.97% fidelity. If true, this seems extremely good. Indeed, it seems better than the numbers from bigger trapped-ion efforts, and quite close to the ~99.99% that you’d want for quantum fault-tolerance. But maybe there’s a catch? Will they not be able to maintain this kind of fidelity when doing a long sequence of programmable two-qubit gates on dozens of qubits? Can the other trapped-ion efforts actually achieve similar fidelities in head-to-head comparisons? Anyway, I was surprised to see how little attention the paper got on SciRate. I look forward to hearing from experts in the comment section.

---

Second, I almost forgot … but last week Quantinuum announced that it’s done a better quantum supremacy experiment based on Random Circuit Sampling with 56 qubits—similar to what Google and USTC did in 2019-2020, but this time using 2-qubit gates with 99.84% fidelities (rather than merely ~99.5%). This should set a new standard for those looking to simulate these things using tensor network methods.

---

Third, a new paper by Schuster, Haferkamp, and Huang gives a major advance on k-designs and pseudorandom unitaries. Roughly speaking, the paper shows that even in one dimension, a random n-qubit quantum circuit, with alternating brickwork layers of 2-qubit gates, forms a “k-design” after only O(k polylog k log n) layers of gates. Well, modulo one caveat: the “random circuit” isn’t from the most natural ensemble, but has to have some of its 2-qubit gates set to the identity, namely those that straddle certain contiguous blocks of log n qubits. This seems like a purely technical issue—how could randomizing those straddling gates make the mixing behavior worse?—but future work will be needed to address it. Notably, the new upper bound is off from the best-possible k layers by only logarithmic factors. (For those tuning in from home: a k-design informally means a collection of n-qubit unitaries such that, from the perspective of degree-k polynomials, choosing a unitary randomly from the collection looks the same as choosing randomly among all n-qubit unitary transformations—i.e., from the Haar measure.)

Anyway, even in my current decrepit state, I can see that such a result would have implications for … well, all sorts of things that quantum computing and information theorists care about. Again I welcome any comments from experts!

---

Incidentally, congratulations to Peter Shor for winning the Shannon Award!

In Michael Sipser’s Introduction to the Theory of Computation textbook, he has one Platonically perfect homework exercise, so perfect that I can reconstruct it from memory despite not having opened the book for over a decade. It goes like this:

• Let f:{0,1}*→{0,1} be the constant 1 function if God exists, or the constant 0 function if God does not exist. Is f computable? (Hint: The answer does not depend on your religious beliefs.)

The correct answer is that yes, f is computable. Why? Because the constant 1 function is computable, and so is the constant 0 function, so if f is one or the other, then it’s computable.

If you’re still tempted to quibble, then consider the following parallel question:

• Let n equal 3 if God exists, or 5 if God does not exist. Is n prime?

The answer is again yes: even though n hasn’t been completely mathematically specified, it’s been specified enough for us to say that it’s prime (just like if we’d said, “n is an element of the set {3,5}; is n prime?”). Similarly, f has been specified enough for us to say that it’s computable.

The deeper lesson Sipser was trying to impart is that the concept of computability applies to functions or infinite sequences, not to individual yes-or-no questions or individual integers. Relatedly, and even more to the point: computability is about whether a computer program exists to map inputs to outputs in a specified way; it says nothing about how hard it might be to choose or find or write that program. Writing the program could even require settling God’s existence, for all the definition of computability cares.

---

Dozens of times in the past 25 years, I’ve gotten some variant on the following question, always with the air that I’m about to bowled over by its brilliance:

• Could the P versus NP question itself be NP-hard, and therefore impossible to solve?

Every time I get this one, I struggle to unpack the layers of misconceptions. But for starters: the concept of “NP-hard” applies to functions or languages, like 3SAT or Independent Set or Clique or whatnot, all of which take an input (a Boolean formula, a graph, etc) and produce a corresponding output. NP-hardness means that, if you had a polynomial-time algorithm to map the inputs to the outputs, then you could convert it via reductions into a polynomial-time algorithm for any language or function in the class NP.

P versus NP, by contrast, is an individual yes-or-no question. Its answer (for all we know) could be independent of the Zermelo-Fraenkel axioms of set theory, but there’s no sense in which the question could be uncomputable or NP-hard. Indeed, a fast program that correctly answers the P vs. NP question trivially exists:

• If P=NP, then the program prints “P=NP.”
• If P≠NP, then the program prints “P≠NP.”

---

In the comments of last week’s post on the breakthrough determination of Busy Beaver 5, I got several variants on the following question:

• What’s the smallest n for which the value of BB(n) is uncomputable? Could BB(6) already be uncomputable?

Once again, I explained that the Busy Beaver function is uncomputable, but the concept of computability doesn’t apply to individual integers like BB(6). Indeed, whichever integer k turns out to equal BB(6), the program “print k” clearly exists, and it clearly outputs that integer!

Again, we can ask for the smallest n such that the value of BB(n) is unprovable in ZF set theory (or some other system of axioms)—precisely the question that Adam Yedidia and I did ask in 2016 (the current record stands at n=745, improving my and Adam’s n=8000). But every specific integer is “computable”; it’s only the BB function as a whole that’s uncomputable.

Alas, in return for explaining this, I got more pushback, and even ridicule and abuse that I chose to leave in the moderation queue.

---

So, I’ve come to think of this as the Zombie Misconception of Theoretical Computer Science: this constant misapplication of concepts that were designed for infinite sequences and functions, to individual integers and open problems. (Or, relatedly: the constant conflation of the uncomputability of the halting problem with Gödel incompleteness. While they’re closely related, only Gödel lets you talk about individual statements rather than infinite families of statements, and only Turing-computability is absolute, rather than relative to a system of axioms.)

Anyway, I’m writing this post mostly just so that I have a place to link the next time this pedagogical zombie rises from its grave, muttering “UNCOMPUTABLE INTEGERRRRRRS….” But also so I can query my readers: what are your ideas for how to keep this zombie down?

The news these days feels apocalyptic to me—as if we’re living through, if not the last days of humanity, then surely the last days of liberal democracy on earth.

All the more reason to ignore all of that, then, and blog instead about the notorious Busy Beaver function! Because holy moly, what news have I got today. For lovers of this super-rapidly-growing sequence of integers, I’ve honored to announce the biggest Busy Beaver development that there’s been since 1983, when I slept in a crib and you booted up your computer using a 5.25-inch floppy. That was the year when Allen Brady determined that BusyBeaver(4) was equal to 107. (Tibor Radó, who invented the Busy Beaver function in the 1960s, quickly proved with his student Shen Lin that the first three values were 1, 6, and 21 respectively. The fourth value was harder.)

Only now, after an additional 41 years, do we know the fifth Busy Beaver value. Today, an international collaboration called bbchallenge is announcing that it’s determined, and even formally verified using the Coq proof system, that BB(5) is equal to 47,176,870—the value that’s been conjectured since 1990, when Heiner Marxen and Jürgen Buntrock discovered a 5-state Turing machine that runs for exactly 47,176,870 steps before halting, when started on a blank tape. The new bbchallenge achievement is to prove that all 5-state Turing machines that run for more steps than 47,176,870, actually run forever—or in other words, that 47,176,870 is the maximum finite number of steps for which any 5-state Turing machine can run. That’s what it means for BB(5) to equal 47,176,870.

For more on this story, see Ben Brubaker’s superb article in Quanta magazine, or bbchallenge’s own announcement. For more background on the Busy Beaver function, see my 2020 survey, or my 2017 big numbers lecture, or my 1999 big numbers essay, or the Googology Wiki page, or Pascal Michel’s survey.

---

The difficulty in pinning down BB(5) was not just that there are a lot of 5-state Turing machines (16,679,880,978,201 of them to be precise, although symmetries reduce the effective number). The real difficulty is, how do you prove that some given machine runs forever? If a Turing machine halts, you can prove that by simply running it on your laptop until halting (at least if it halts after a “mere” ~47 million steps, which is child’s-play). If, on the other hand, the machine runs forever, via some never-repeating infinite pattern rather than a simple infinite loop, then how do you prove that? You need to find a mathematical reason why it can’t halt, and there’s no systematic method for finding such reasons—that was the great discovery of Gödel and Turing nearly a century ago.

More precisely, the Busy Beaver function grows faster than any function that can be computed, and we know that because if a systematic method existed to compute arbitrary BB(n) values, then we could use that method to determine whether a given Turing machine halts (if the machine has n states, just check whether it runs for more than BB(n) steps; if it does, it must run forever). This is the famous halting problem, which Turing proved to be unsolvable by finite means. The Busy Beaver function is Turing-uncomputability made flesh, a finite function that scrapes the edge of infinity.

There’s also a more prosaic issue. Proofs that particular Turing machines run forever tend to be mind-numbingly tedious. Even supposing you’ve found such a “proof,” why should other people trust it, if they don’t want to spend days staring at the outputs of your custom-written software?

And so for decades, a few hobbyists picked away at the BB(5) problem. One, who goes by the handle “Skelet”, managed to reduce the problem to 43 holdout machines whose halting status was still undetermined. Or maybe only 25, depending who you asked? (And were we really sure about the machines outside those 43?)

The bbchallenge collaboration improved on the situation in two ways. First, it demanded that every proof of non-halting be vetted carefully. While this went beyond the original mandate, a participant named “mxdys” later upped the standard to fully machine-verifiable certificates for every non-halting machine in Coq, so that there could no longer be any serious question of correctness. (This, in turn, was done via “deciders,” programs that were crafted to recognize a specific type of parameterized behavior.) Second, the collaboration used an online forum and a Discord server to organize the effort, so that everyone knew what had been done and what remained to be done.

Despite this, it was far from obvious a priori that the collaboration would succeed. What if, for example, one of the 43 (or however many) Turing machines in the holdout set turned out to encode the Goldbach Conjecture, or one of the other great unsolved problems of number theory? Then the final determination of BB(5) would need to await the resolution of that problem. (We do know, incidentally, that there’s a 27-state Turing machine that encodes Goldbach.)

But apparently the collaboration got lucky. Coq proofs of non-halting were eventually found for all the 5-state holdout machines.

As a sad sidenote, Allen Brady, who determined the value of BB(4), apparently died just a few days before the BB(5) proof was complete. He was doubtful that BB(5) would ever be known. The reason, he wrote in 1988, was that “Nature has probably embedded among the five-state holdout machines one or more problems as illusive as the Goldbach Conjecture. Or, in other terms, there will likely be nonstopping recursive patterns which are beyond our powers of recognition.”

---

Maybe I should say a little at this point about what the 5-state Busy Beaver—i.e., the Marxen-Buntrock Turing machine that we now know to be the champion—actually does. Interpreted in English, the machine iterates a certain integer function g, which is defined by

• g(x) = (5x+18)/3 if x = 0 (mod 3),
• g(x) = (5x+22)/3 if x = 1 (mod 3),
• g(x) = HALT if x = 2 (mod 3).

Starting from x=0, the machine computes g(0), g(g(0)), g(g(g(0))), and so forth, halting if and if it ever reaches … well, HALT. The machine runs for millions of steps because it so happens that this iteration eventually reaches HALT, but only after a while:

0 → 6 → 16 → 34 → 64 → 114 → 196 → 334 → 564 → 946 → 1584 → 2646 → 4416 → 7366 → 12284 → HALT.

(And also, at each iteration, the machine runs for a number of steps that grows like the square of the number x.)

Some readers might be reminded of the Collatz Conjecture, the famous unsolved problem about whether, if you repeatedly replace a positive integer x by x/2 if x is even or 3x+1 if x is odd, you’ll always eventually reach x=1. As Scott Alexander would say, this is not a coincidence because nothing is ever a coincidence. (Especially not in math!)

---

It’s a fair question whether humans will ever know the value of BB(6). Pavel Kropitz discovered, a couple years ago, that BB(6) is at least 10^10^10^10^10^10^10^10^10^10^10^10^10^10^10 (i.e., 10 raised to itself 15 times). Obviously Kropitz didn’t actually run a 6-state Turing machine for that number of steps until halting! Instead he understood what the machine did—and it turned out to apply an iterative process similar to the g function above, but this time involving an exponential function. And the process could be proven to halt after ~15 rounds of exponentiation.

Meanwhile Tristan Stérin, who coordinated the bbchallenge effort, tells me that a 6-state machine was recently discovered that “iterates the Collatz-like map {3x/2, (3x-1)/2} from the number 8 and halts if and only if the number of odd terms ever gets bigger than twice the number of even terms.” This shows that, in order to determine the value of BB(6), one would first need to prove or disprove the Collatz-like conjecture that that never happens.

Basically, if and when artificial superintelligences take over the world, they can worry about the value of BB(6). And then God can worry about the value of BB(7).

---

I first learned about the BB function in 1996, when I was 15 years old, from a book called The New Turing Omnibus by A. K. Dewdney.  From what I gather, Dewdney would go on to become a nutty 9/11 truther.  But that’s irrelevant to the story.  What matters was that his book provided my first exposure to many of the key concepts of computer science, and probably played a role in my becoming a theoretical computer scientist at all.

And of all the concepts in Dewdney’s book, the one I liked the most was the Busy Beaver function. What a simple function! You could easily explain its definition to Archimedes, or Gauss, or any of the other great mathematicians of the past. And yet, by using it, you could name definite positive integers (BB(10), for example) incomprehensibly larger than any that they could name.

It was from Dewdney that I learned that the first four Busy Beaver numbers were the unthreatening-looking 1, 6, 21, and 107 … but then that the fifth value was already unknown (!!), and at any rate at least 47,176,870. I clearly remember wondering whether BB(5) would ever be known for certain, and even whether I might be the one to determine it. That was almost two-thirds of my life ago.

As things developed, I played no role whatsoever in the determination of BB(5) … except for this. Tristan Stérin tells me that reading my survey article, The Busy Beaver Frontier, was what inspired him to start and lead the bbchallenge collaboration that finally cracked the problem. It’s hard to express how gratified that makes me.

---

Why care about determining particular values of the Busy Beaver function? Isn’t this just a recreational programming exercise, analogous to code golf, rather than serious mathematical research?

I like to answer that question with another question: why care about humans landing on the moon, or Mars? Those otherwise somewhat arbitrary goals, you might say, serve as a hard-to-fake gauge of human progress against the vastness of the cosmos. In the same way, the quest to determine the Busy Beaver numbers is one concrete measure of human progress against the vastness of the arithmetical cosmos, a vastness that we learned from Gödel and Turing won’t succumb to any fixed procedure. The Busy Beaver numbers are just … there, Platonically, as surely as 13 was prime long before the first caveman tried to arrange 13 rocks into a nontrivial rectangle and failed. And yet we might never know the sixth of these numbers and only today learned the fifth.

Anyway, huge congratulations to the bbchallenge team on their accomplishment. At a terrifying time for the world, I’m happy that, whatever happens, at least I lived to see this.