Shtetl-Optimized

WHOA … I’ve won the inaugural Luca Trevisan Award for Expository Work in Theoretical Computer Science! This has a particular meaning for me as someone who knew Luca Trevisan as well as I did for 25 years — who had him as a professor and thesis committee member, whose blog bounced off his blog, who benefitted tremendously from his expository work in TCS — before Luca tragically succumbed to cancer two years ago.

As I told the committee, receiving this award makes me want to use my blog for more actual CS theory exposition, and less venting, in order to retrospectively become worthier of such an honor.

I’m ridiculously grateful to the entire TCS community — my people, my homies — for tolerating me to do what I do.

If you’re curious, here’s the official citation:

The inaugural Luca Trevisan Award for Expository Work in Theoretical Computer Science is awarded to Scott Aaronson for his sustained and high-impact inspirational efforts to explain and promote our field to broad audiences. His blog Shtetl-Optimized has hosted remarkably frequent and elaborate posts over more than two decades, and has become a central meeting place for wide-ranging conversations across the TCS and Physics communities. Scott Aaronson’s blog posts contain crystal-clear, informative expositions of exciting new results, calibrated evaluations of technological claims, and profound analyses of topics in these fields and (way) beyond. The uniquely enthusiastic and witty style of his writings (including his book Quantum Computing Since Democritus and his other lecture notes and surveys), lectures, and interviews have made him a top invitee for both popular and professional appearances, attracting large audiences. These qualities have inspired many students to enter the field, and made Scott Aaronson a go-to person for journalists and scientists alike looking for a definitive word on the latest scientific activity in TCS and quantum computing.

---

In the rest of this post, I’m going to start practicing what I preached—y’know, about turning over more of this blog to actual exposition, of a kind that the Trevisan Award could plausibly be meant to encourage. I’ll start with something that’s been on my back burner for the past couple months: namely, the (lightly edited) transcript of a talk that I gave this spring at UT Austin’s undergraduate math club. So, without further ado, and in memory of Luca…

---

On the Decimal Digits of Powers of 2
by Scott Aaronson

Hi! I’ve given six previous talks here at UT’s math club, some on relatively “important” topics—Gödel’s Theorem, time travel, Huang’s proof of the Sensitivity Conjecture, and so on.

Today, I want to talk about an unimportant question, one that my son Daniel, who was then 8, and who’s sitting here in the front row (along with his sister Lily), asked me a few months ago.

Daniel asked: which powers of 2 can you double without needing to carry digits? Clearly 1, 2, 4, 32, and 1024 all have this property, their doubles being 2, 4, 8, 64, and 2048 respectively. Are there any others?

Since I happen to have the powers of 2 up to 2²⁰ = 1,048,576 committed to memory since childhood, I confirmed that there were no other examples up to there: 128, 256, 512, 2048, etc. all require carries. So I told Daniel: I can’t find any other example, and on that basis, I conjecture that there aren’t any more. But if that conjecture is true, I don’t know if it will ever be proven, by humans or even AI!

Then I googled it, and saw that this is a known question (not very well known, but there’s a StackExchange post about it). And indeed it had been checked up to 2^millions, and no other counterexample had been found.

---

Why did I become confident so quickly that yes, 1024 is probably the last example of a power of 2 that can be doubled without carrying?

Because of the heuristic that the decimal digits of 2ⁿ are more or less “random,” apart from various constraints that are irrelevant here (like that the last digit always cycles among 2, 4, 6, and 8). And 2ⁿ has about n/log₂10 decimal digits. Since only 0, 1, 2, 3, 4 can be doubled without carrying, the probability of 2ⁿ being a counterexample should therefore be about $$ (\frac{1}{2} )^{n / \log_2 10}. $$

So, if we’ve already checked up to (say) n=1000, then the probability of a larger counterexample should be at most

$$ \sum_{n=1001}^{\infty} (\frac{1}{2} )^{n / \log_2 10} $$

which, when we sum the geometric series, is exceedingly close to 0.

---

Ah, but why did I say that I don’t know if the conjecture will ever be proven? Because it seems to belong a large class of similar statements, none of which mathematicians have had any idea how to prove.

Variant of a conjecture by Jeffrey Shallit: 65,536 is the only power of 2 that has no power of 2 among its decimal digits.

Freeman Dyson’s conjecture (2005): There’s no power of 2 for which, when you reverse the decimal digits, you get a power of 5.

Paul Erdös’s conjecture (1979): For every n≥9, there’s at least one ‘2’ in the base-3 representation of 2ⁿ.

Or looking even more broadly:

Conjecture: The decimal expansion of π is not all 6’s and 7’s after some finite point.

(This would follow from the stronger conjecture that π is base-10 normal—that is, that every finite pattern of decimal digits occurs in it with the limiting frequency you’d expect.)

Or:

Conjecture: π+e is an irrational number.

What all the above conjectures have in common, and what I find so fascinating about them, is that they seem hopeless to prove for exactly the same reason why they seem almost certainly true. Namely, they all seem to be true “merely” because it would be too insane of a coincidence were they false!

The trouble is, that’s not the sort of reason that seems amenable to turning into a proof. Fermat’s Last Theorem is an interesting exception that proves the rule here. That xⁿ+yⁿ=zⁿ has no nontrivial integer solution for n≥3, did seem almost certainly true on statistical grounds for n≥4 (and for the n=3 case, a proof goes back to Euler). And of course, FLT was ultimately provable. But Wiles’s eventual proof exploited a lucky connection between the Fermat equation and deep, fancy things like modular forms and elliptic curves. At no point did the proof formalize the statistical argument that a 12-year-old could understand, for why the theorem is “almost certainly true.” It simply had nothing to do with the statistical argument.

So then, if you wanted to prove conjectures like my son Daniel’s, or like Shallit’s or Dyson’s or Erdös’s above, the question would be: could these “recreational” problems about base-10 representations ever be connected to anything similarly deep? Right now, it’s very hard to see how they could.

Still, all hope is not lost! Here’s a striking theorem that I learned about when I researched this:

Theorem (James Maynard, 2016): For every digit a from 0 to 9, there are infinitely many primes with no a’s in their base-10 representation.

The proof uses heavy Fourier-analytic techniques. Likewise, presumably there are infinitely many primes that you can double without carrying—2, 3, 11, 13, 23, 31, …—because the primes are much denser than the powers of 2! And presumably there are infinitely many primes that are missing any two decimal digits, or even whose decimal digits consist entirely of 0’s and 1’s. But Maynard’s techniques are not yet powerful enough to prove such things.

---

Even though I promised a topic of no importance today, I can’t resist pointing out a potential connection here to one of the biggest questions on earth right now, and something that’s professionally interested me for the past four years: namely, the question of how to align powerful AIs with human values and prevent them from destroying the world.

Paul Christiano, and the Alignment Research Center in Berkeley that he founded, have developed a whole program for how to make AI safe that depends on the possibility of formalizing “heuristic arguments”—that is, the kinds of arguments that convince us that the above conjectures are all almost certainly true, even without proofs of them.

The intuition here is that we’ll never have a rigorous proof that, for example, a real-world neural network will behave safely under all circumstances—it’s just too complicated. The best we can hope for is an argument that, e.g., “for this model to scheme against humans would require a crazy unexplained coincidence in its weights.” But how can we hope to formalize such arguments? As baby test cases, can we at least formalize our intuitions for why π is normal, or why Daniel’s conjecture is true, in some principled way?

ARC has tried: there’s a 2022 paper by Christiano, Neyman, and Xu on “Formalizing the presumption of independence.” But it’s tricky, and ARC itself would be the first to agree that the existing results are unsatisfying. How do we even formalize the intuition that, for example, you should be willing to bet at even odds against the 10¹⁰⁰th digit of π being a 5?

---

In the rest of this talk, I’d like to circle back to Daniel’s original question about powers of 2, and show you some things that can be proved about it—with thanks to Greg Kuperberg and my other friends on Facebook, and in some cases to GPT5Pro.

Let’s start with the following easier question. Is there a power of 2 whose decimal digits start with 31415? Or with the complete works of Shakespeare, encoded by letter values in some suitable way? Or with a googolplex digits all of which can be doubled without carrying (as Daniel wanted)?

I claim that the answers are yes, yes, and yes! How do we prove this?

The key fact we’ll use is simply that log₁₀2 is an irrational number. (If you don’t remember the proof: suppose log₁₀2 = a/b. Then 10^a/b = 2, so 10^a=2^b. But this has no integer solutions other than a=b=0.)

Suppose we want k as a prefix, where 10^d-1 ≤ k ≤ 10^d. Then we want integers n,r such that

$$ k 10^r \le 2^n \le (k+1) 10^r, $$

i.e. taking the base-10 log,

$$ \log_{10}k + r \le n \log_{10}2 \le \log_{10}(k+1) + r. $$

In other words, the fractional part of n log₁₀2 needs to lie between the fractional part of log₁₀(k), and the fractional part of log₁₀(k+1) (where again, k is given).

But now we can appeal to the following Key Fact: if α is any irrational number, then the set

{the fractional part of nα : n∈N}

is dense in the interval [0,1]. Or equivalently, if I rotate around and around the unit circle by 2απ radians each time, then if α is irrational, I’ll eventually get arbitrarily close to any given point on the unit circle.

Why is the key fact true? Just the pigeonhole principle! Clearly, for any ε>0, the fact that α is irrational means that there must be two points, xα and yα, whose fractional parts are distinct yet closer together than ε. But then, by adding multiples of (x-y)α, we can get our fractional part to be ε-close to anything in [0,1].

And to sum up, this is why there must be a power of 2 whose decimal representation starts with the complete works of Shakespeare, or with a googolplex carry-free digits! (Indeed, from the above discussion, we could even extract an efficient algorithm for constructing that power of 2.)

---

So much for the first decimal digits of 2ⁿ. Now let’s look at 2ⁿ‘s last decimal digits!

Here there are some complications, arising from the twin facts that

(a) 10 is composite, and
(b) 2 is one of its factors.

But we can deal with those complications!

For starters: what are the possible last decimal digits of 2ⁿ?

1, 2, 4, 8, 6, 2, 4, 8, 6, …

So, there’s an initial 1, but then we cycle forever through the even nonzero digits.

What about the last two digits of 2ⁿ? If you’ve never tried this before, it’s instructive to work it out:

01, 02, 04, 08, 16, 32, 64, 28, 56, 12, 24, 48, 96, 92, 84, 68, 36, 72, 44, 88, 76, 52, 04, …

So, there’s an initial 01 and 02, but after that, we cycle forever through 20=4×5 possibilities, namely all the possible multiples of 4 whose last digits are nonzero.

You can check that the general pattern is: the last k decimal digits of 2ⁿ have an initial segment that looks like 001, 002, 004, 008, …, 2^k-1. And then there’s an eternal cycle of length 4×5^k-1, where the last digit can be any of 2,4,6,8, while every other digit can either be any possible even digit or any possible odd digit, depending on the digits to its right—in (if you want to say this a fancier way) a recursively defined embedding of the powers of 2 mod 5^k into the cyclic group Z/10^k. So, there’s an initial “runup” as you fill out all the needed powers of 2, but then once that’s done, you just cycle around forever in an embedding of Z/5^k into Z/10^k, because

(a) 2 happens to be a primitive element of Z/5^k for any k, and
(b) 5 divides 10.

So in particular, and relevant to Daniel’s conjecture: there exists a power of 2 whose last googolplex digits can all be doubled without carrying. Why? For the last digit, you can pick 2 or 4. Then, for the last googolplex digits but one, you can pick 1 or 3 for those constrained to be odd, and 0, 2, or 4 for those constrained to be even. Lots of choices that work!

---

So, we can avoid carries in the leftmost digits of 2ⁿ, we can avoid carries in the rightmost digits … so that “merely” leaves all the digits in the middle, where who the hell knows! Empirically, the digits seem to pass every standard randomness test that you can throw at them. So in particular, e.g., the fraction of the digits that are in {0,1,2,3,4} seems to converge inexorably towards 50%, so that it’s extremely plausible to conjecture that the fraction is less than 49% or more than 51% for only finitely many values of n. But of course, that’s presumably even harder to prove than Daniel’s original conjecture.

---

OK, last topic. Suppose we want to program a computer to check Daniel’s conjecture up to 2ⁿ, for some huge n. What algorithm will do that most efficiently? A naive algorithm would just calculate 1, 2, 4, …, 2ⁿ and check all the digits of all of them. That takes O(n²) time, since each 2^k, for k=0,1,…,n, has ~klog₁₀2 = O(k) decimal digits.

We can improve this to roughly O(n) time, by simply noticing that we only need to check O(1) digits per power of 2 in expectation, presumably, until we find the first digit that requires carrying. Then we don’t even need to compute the remaining digits: we can simply move on to the next power of 2. (This sort of trick is used all over the place in the design of fast algorithms.)

But when I posted about Daniel’s problem on Facebook, my friend Greg Kuperberg (who’s a mathematician at UC Davis) noticed that further improvements are possible. To wit: 8×6 = 48, which again ends in 8. So, 8×16 ends in 8, as does 8×16^k for every k≥0. Meaning: no 2ⁿ where n=3+4k can possibly be a counterexample to Daniel’s conjecture. They’re all ruled out!

Likewise, 64×1,048,576 ends in 64, so no 2ⁿ of the form n=6+20k can be a counterexample. They’re all ruled out as well.

We can keep going this way, filling out the “search tree” of potential counterexamples to Daniel’s conjecture via breadth-first search. At the root of the search tree, we try all possibilities for the last digit. One level deeper, we try all possibilities for the second-to-last digit, and so on. As we go, we prune subtrees according to constraints like the ones above that we keep discovering and adding.

When I worked this out, I got an algorithm for checking Daniel’s conjecture up to 2ⁿ, which under reasonable assumptions takes time only O(n^α), where α = 1-log₅2 ≈ 0.569, and space only polylog(n).

Paul Crowley (who’s my Facebook friend) then actually implemented this algorithm, and he tells me that he used it to check that Daniel’s conjecture holds all the way up to $$2^{10^{21}}$$ (!!), using 40 minutes on a 128-core machine.

So, to return at last to the first thing I told Daniel: yes, I think his conjecture is almost certainly true, even though I have no idea when, if ever, the human race or its successors will have a proof.

Alas, the dream that I had last night was not the inspiring, MLK kind of dream, even though tomorrow happens to be the great man’s day.  No, I had the literal kind of dream, where everything seems real but then you wake up and remember only the last fragments.

In my case, those last fragments involved a gray-haired bespectacled woman, a fellow CS professor.  She and I were standing in a dimly lit university building.  And she was grabbing me by the shoulders, shaking me.

“Look, Scott,” she was saying, “we’re both computer scientists.  We were both around in the 90s.  You know as well as I do that, if someone claims to have built an AI, but it turns out they just loaded a bunch of known answers, written by humans, into a lookup table, and then they search the table when a question comes … that’s not AI.  It’s slop.  It’s garbage.”

“But…” I interjected.

“Oh of course,” she continued, “so you make the table bigger.  What do you have now?  More slop!  More garbage!  You load the entire Internet into the table.  Now you have an astronomical-sized piece of garbage!”

“I mean,” I said, “there’s an exponential blowup in the number of possible questions, which can only be handled by…”

“Of course,” she said impatiently, “I understand as well as anyone.  You train a neural net to predict a probability distribution over the next token.  In other words, you slice up and statistically recombine your giant lookup table to disguise what’s really going on.  Now what do you get?  You get the biggest piece of garbage the world has ever seen.  You get a hideous monster that’s destroying and zombifying our entire civilization … and that still understands nothing more than the original lookup table did.”

“I mean, you get a tool that hundreds of millions of people now use every day—to write code, to do literature searches…”

By this point, the professor was screaming at me, albeit with a pleading tone in her voice.  “But no one who you respect uses that garbage! Not a single one!  Go ahead and ask them: scientists, mathematicians, artists, creators…”

“I use it,” I replied quietly.  “Most of my friends use it too.”

The professor stared at me with a new, wordless horror.  And that’s when I woke up.

I think I was next going to say something about how I agreed that generative AI might be taking the world down a terrible, dangerous path, but how dismissing the scientific and philosophical immensity of what’s happened, by calling it “slop,” “garbage,” etc., is a bad way to talk about the danger. If so, I suppose I’ll never know how the professor would’ve replied to that. Though, if she was just an unintegrated part of my own consciousness—or a giant lookup table that I can query on demand!—perhaps I could summon her back.

Mostly, I remember being surprised to have had a dream that was this coherent and topical. Normally my dreams just involve wandering around lost in an airport that then transforms itself into my old high school, or something.

Scott Alexander has put up one of his greatest posts ever, a 10,000-word eulogy to Dilbert creator Scott Adams, of which I would’ve been happy to read 40,000 words more. In it, Alexander trains a microscope on Adams’ tragic flaws as a thinker and human being, but he adds:

In case it’s not obvious, I loved Scott Adams.

Partly this is because we’re too similar for me to hate him without hating myself.

And:

Adams was my teacher in a more literal way too. He published several annotated collections, books where he would present comics along with an explanation of exactly what he was doing in each place, why some things were funny and others weren’t, and how you could one day be as funny as him. Ten year old Scott devoured these … objectively my joke posts get the most likes and retweets of anything I write, and I owe much of my skill in the genre to cramming Adams’ advice into a malleable immature brain.

When I first heard the news that Scott Adams had succumbed to cancer, I posted something infinitely more trivial on my Facebook. I simply said:

Scott Adams (who reigned for decades as the #1 Scott A. of the Internet, with Alexander as #2 and me as at most #3) was a hateful asshole, a nihilist, and a crank. And yet, even when reading the obituaries that explain what an asshole, nihilist, and crank he was, I laugh whenever they quote him.

Inspired by Scott Alexander, I’d like now to try again, to say something more substantial. As Scott Alexander points out, Scott Adams’ most fundamental belief—the through-line that runs not only through Dilbert but through all his books and blog posts and podcasts—was that the world is ruled by idiots. The pointy-haired boss always wins, spouting about synergy and the true essence of leadership, and the nerdy Dilberts always lose. Trying to change minds by rational argument is a fools’ errand, as “master persuaders” and skilled hypnotists will forever run rings around you. He, Scott Adams, is cleverer than everyone else, among other things because he realizes all this—but even he is powerless to change it.

Or as Adams put it in The Dilbert Principle:

It’s useless to expect rational behavior from the people you work with, or anybody else for that matter. If you can come to peace with the fact that you’re surrounded by idiots, you’ll realize that resistance is futile, your tension will dissipate, and you can sit back and have a good laugh at the expense of others.

The thing is, if your life philosophy is that the world is ruled by idiots, and that confident charlatans will always beat earnest nerds, you’re … often going to be vindicated by events. Adams was famously vindicated back in 2015, when he predicted Trump’s victory in the 2016 election (since Trump, you see, was a “master persuader”), before any other mainstream commentator thought that Trump even had a serious chance of winning the Republican nomination.

But if you adopt this worldview, you’re also often going to be wrong—as countless of Adams’ other confident predictions were (see Scott Alexander’s post for examples), to say nothing of his scientific or moral views.

My first hint that the creator of Dilbert was not a reliable thinker, was when I learned of his smugly dismissive view of science. One of the earliest Shtetl-Optimized posts, way back in 2006, was entitled Scott A., disbeliever in Darwinism. At that time, Adams’ crypto-creationism struck me as just some bizarre, inexplicable deviation. I’m no longer confused about it: on the one hand, Scott Alexander’s eulogy shows just how much deeper the crankishness went, how Adams also gobbled medical misinformation, placed his own cockamamie ideas about gravity on par with general relativity, etc. etc. But Alexander succeeds in reconciling all this with Adams’ achievements: it’s all just consequences from the starting axiom that the world is ruled by morons, and that he, Scott Adams, is the only one clever enough to see through it all.

---

Is my epistemology any different? Do I not also look out on the world, and see idiots and con-men and pointy-haired bosses in every direction? Well, not everywhere. At any rate, I see far fewer of them in the hard sciences.

This seems like a good time to say something that’s been a subtext of Shtetl-Optimized for 20 years, but that Scott Alexander has inspired me to make text.

My whole worldview starts from the observation that science works. Not perfectly, of course—working in academic science for nearly 30 years, I’ve had a close-up view of the flaws—but the motor runs. On a planet full of pointy-haired bosses and imposters and frauds, science nevertheless took us in a few centuries from wretchedness and superstition to walking on the moon and knowing the age of the universe and the code of life.

This is the point where people always say: that’s all well and good, but you can’t derive ought from is, and science, for all its undoubted successes, tells us nothing about what to value or how to live our lives.

To which I reply: that’s true in a narrow sense, but it dramatically understates how far you can get from the “science works” observation.

As one example, you can infer that the people worth listening to are the people who speak and write clearly, who carefully distinguish what they know from what they don’t, who sometimes change their minds when presented with opposing views and at any rate give counterarguments—i.e., who exemplify the values that make science work. The political systems worth following are the ones that test their ideas against experience, that have built-in error-correction mechanisms, that promote people based on ability rather than loyalty—the same things that make scientific institutions work, insofar as they do work. And of course, if the scientists who study X are nearly unanimous in saying that a certain policy toward X would be terrible, then we’d better have a damned good reason to pursue the policy anyway. This still leaves a wide range of moral and political views on the table, but it rules out virtually every kind of populism, authoritarianism, and fundamentalism.

Incidentally, this principle—that one’s whole moral and philosophical worldview should grow out of the seed of science working—is why, from an early age, I’ve reacted to every kind of postmodernism as I would to venomous snakes. Whenever someone tells me that science is just another narrative, a cultural construct, a facade for elite power-seeking, etc., to me they might as well be O’Brien from 1984, in the climactic scene where he tortures Winston Smith into agreeing that 2+2=5, and that the stars are just tiny dots a few miles away if the Party says they are. Once you can believe absurdities, you can justify atrocities.

Scott Adams’ life is interesting to me in that shows exactly how far it’s possible to get without internalizing this. Yes, you can notice that the pointy-haired boss is full of crap. You can make fun of the boss. If you’re unusually good at making fun of him, you might even become a rich, famous, celebrated cartoonist. But you’re never going to figure out any ways of doing things that are systematically better than the pointy-haired boss’s ways, or even recognize the ways that others have found. You’ll be in error far more often than in doubt. You might even die of prostate cancer earlier than necessary, because you listen to medical crackpots and rely on ivermectin, turning to radiation and other established treatments only after having lost crucial time.

---

Scott Adams was hardly the first great artist to have tragic moral flaws, or to cause millions of his fans to ask whether they could separate the artist from the art. But I think he provides one of the cleanest examples where the greatness and the flaws sprang from the same source: namely, overgeneralization from the correct observation that “the world is full of idiots,” in a way that leaves basically no room even for Darwin or Einstein, and so inevitably curdles over time into crankishness, bitterness, and arrogance. May we laugh at Scott Adams’ cartoons and may we learn from his errors, both of which are now permanent parts of the world’s heritage.

Not long ago William MacAskill, the founder of the Effective Altruist movement, visited Austin, where I got to talk with him in person for the first time. I was a fan of his book What We Owe the Future, and found him as thoughtful and eloquent face-to-face as I did on the page. Talking to Will inspired me to write the following short reflection on how I should spend my time, which I’m now sharing in case it’s of interest to anyone else.

---

By inclination and temperament, I simply seek the clearest possible understanding of reality.  This has led me to spend time on (for example) the Busy Beaver function and the P versus NP problem and quantum computation and the foundations of quantum mechanics and the black hole information puzzle, and on explaining whatever I’ve understood to others.  It’s why I became a professor.

But the understanding I’ve gained also tells me that I should try to do things that will have huge positive impact, in what looks like a pivotal and even terrifying time for civilization.  It tells me that seeking understanding of the universe, like I’ve been doing, is probably nowhere close to optimizing any values that I could defend.  It’s self-indulgent, a few steps above spending my life learning to solve Rubik’s Cube as quickly as possible, but only a few.  Basically, it’s the most fun way I could make a good living and have a prestigious career, so it’s what I ended up doing.  I should be skeptical that such a course would coincidentally also maximize the good I can do for humanity.

Instead I should plausibly be figuring out how to make billions of dollars, in cryptocurrency or startups or whatever, and then spending it in a way that saves human civilization, for example by making AGI go well.  Or I should be convincing whatever billionaires I know to do the same.  Or executing some other galaxy-brained plan.  Even if I were purely selfish, as I hope I’m not, still there are things other than theoretical computer science research that would bring more hedonistic pleasure.  I’ve basically just followed a path of least resistance.

On the other hand, I don’t know how to make billions of dollars.  I don’t know how to make AGI go well.  I don’t know how to influence Elon Musk or Sam Altman or Peter Thiel or Sergey Brin or Mark Zuckerberg or Marc Andreessen to do good things rather than bad things, even when I have gotten to talk to some of them.  Past attempts in this direction by extremely smart and motivated people—for example, those of Eliezer Yudkowsky and Sam Bankman-Fried—have had, err, uneven results, to put it mildly.  I don’t know why I would succeed where they failed.

Of course, if I had a better understanding of reality, I might know how better to achieve prosocial goals for humanity.  Or I might learn why they were actually the wrong goals, and replace them with better goals.  But then I’m back to the original goal of understanding reality as clearly as possible, with the corresponding danger that I spend my time learning to solve Rubik’s Cube faster.

I’ve now been blogging for nearly twenty years—through five presidential administrations, my own moves from Waterloo to MIT to UT Austin, my work on algebrization and BosonSampling and BQP vs. PH and quantum money and shadow tomography, the publication of Quantum Computing Since Democritus, my courtship and marriage and the birth of my two kids, a global pandemic, the rise of super-powerful AI and the terrifying downfall of the liberal world order.

Yet all that time, through more than a thousand blog posts on quantum computing, complexity theory, philosophy, the state of the world, and everything else, I chased a form of recognition for my blogging that remained elusive.

Until now.

This week I received the following email:

I emailed regarding your blog Shtetl-Optimized Blog which was selected by FeedSpot as one of the Top 50 Quantum Computing Blogs on the web.

https://bloggers.feedspot.com/quantum_computing_blogs

We recommend adding your website link and other social media handles to get more visibility in our list, get better ranking and get discovered by brands for collaboration.

We’ve also created a badge for you to highlight this recognition. You can proudly display it on your website or share it with your followers on social media.

We’d be thankful if you can help us spread the word by briefly mentioning Top 50 Quantum Computing Blogs in any of your upcoming posts.

Please let me know if you can do the needful.

You read that correctly: Shtetl-Optimized is now officially one of the top 50 quantum computing blogs on the web. You can click the link to find the other 49.

---

Maybe it’s not unrelated to this new notoriety that, over the past few months, I’ve gotten a massively higher-than-usual volume of emailed solutions to the P vs. NP problem, as well as the other Clay Millennium Problems (sometimes all seven problems at once), as well as quantum gravity and life, the universe, and everything. I now get at least six or seven confident such emails per day.

While I don’t spend much time on this flood of scientific breakthroughs (how could I?), I’d like to note one detail that’s new. Many of the emails now include transcripts where ChatGPT fills in the details of the emailer’s theories for them—unironically, as though that ought to clinch the case. Who said generative AI wasn’t poised to change the world? Indeed, I’ll probably need to start relying on LLMs myself to keep up with the flood of fan mail, hate mail, crank mail, and advice-seeking mail.

Anyway, thanks for reading everyone! I look forward to another twenty years of Shtetl-Optimized, if my own health and the health of the world cooperate.

A friend and I were discussing whether there’s anything I could possibly say, on this blog, in 2025, that wouldn’t provoke an outraged reaction from my commenters. So I started jotting down ideas. Let’s see how I did.

1. Pancakes are a delicious breakfast, especially with blueberries and maple syrup.
   
2. Since it’s now Passover, and no pancakes for me this week, let me add: I think matzoh has been somewhat unfairly maligned. Of course it tastes like cardboard if you eat it plain, but it’s pretty tasty with butter, fruit preserves, tuna salad, egg salad, or chopped liver.
   
3. Central Texas is actually really nice in the springtime, with lush foliage and good weather for being outside.
   
4. Kittens are cute. So are puppies, although I’d go for kittens given the choice.
   
5. Hamilton is a great musical—so much so that it’s become hard to think about the American Founding except as Lin-Manuel Miranda reimagined it, with rap battles in Washington’s cabinet and so forth. I’m glad I got to take my kids to see it last week, when it was in Austin (I hadn’t seen it since it its pre-Broadway previews a decade ago). Two-hundred fifty years on, I hope America remembers its founding promise, and that Hamilton doesn’t turn out to be America’s eulogy.
   
6. The Simpsons and Futurama are hilarious.
   
7. Young Sheldon and The Big Bang Theory are unjustly maligned. They were about as good as any sitcoms can possibly be.
   
8. For the most part, people should be free to live lives of their choosing, as long as they’re not harming others.
   
9. The rapid progress of AI might be the most important thing that’s happened in my lifetime. There’s a huge range of plausible outcomes, from “merely another technological transformation like computing or the Internet” to “biggest thing since the appearance of multicellular life,” but in any case, we ought to proceed with caution and with the wider interests of humanity foremost in our minds.
   
10. Research into curing cancer is great and should continue to be supported.
    
11. The discoveries of NP-completeness, public-key encryption, zero-knowledge and probabilistically checkable proofs, and quantum computational speedups were milestones in the history of theoretical computer science, worthy of celebration.
    
12. Katalin Karikó, who pioneered mRNA vaccines, is a heroine of humanity. We should figure out how to create more Katalin Karikós.
    
13. Scientists spend too much of their time writing grant proposals, and not enough doing actual science. We should experiment with new institutions to fix this.
    
14. I wish California could build high-speed rail from LA to San Francisco. If California’s Democrats could show they could do this, it would be an electoral boon to Democrats nationally.
    
15. I wish the US could build clean energy, including wind, solar, and nuclear. Actually, more generally, we should do everything recommended in Derek Thompson and Ezra Klein’s phenomenal new book Abundance, which I just finished.
    
16. The great questions of philosophy—why does the universe exist? how does consciousness relate to the physical world? what grounds morality?—are worthy of respect, as primary drivers of human curiosity for millennia. Scientists and engineers should never sneer at these questions. All the same, I personally couldn’t spend my life on such questions: I also need small problems, ones where I can make definite progress.
    
17. Quantum physics, which turns 100 this year, is arguably the most metaphysical of all empirical discoveries. It’s worthy of returning to again and again in life, asking: but how could the world be that way? Is there a different angle that we missed?
    
18. If I knew for sure that I could achieve Enlightenment, but only by meditating on a mountaintop for a decade, a further question would arise: is it worth it? Or would I rather spend that decade engaged with the world, with scientific problems and with other people?
    
19. I, too, vote for political parties, and have sectarian allegiances. But I’m most moved by human creative effort, in science or literature or anything else, that transcends time and place and circumstance and speaks to the eternal.
    
20. As I was writing this post, a bird died by flying straight into the window of my home office. As little sense as it might make from a utilitarian standpoint, I am sad for that bird.

Err, happy MLK Day!

This week represents the convergence of so many plotlines that, if it were the season finale of some streaming show, I’d feel like the writers had too many balls in the air. For the benefit of the tiny part of the world that cares what I think, I offer the following comments.

---

My view of Trump is the same as it’s been for a decade—that he’s a con man, a criminal, and the most dangerous internal threat the US has ever faced in its history. I think Congress and Merrick Garland deserve eternal shame for not moving aggressively to bar Trump from office and then prosecute him for insurrection—that this was a catastrophic failure of our system, one for which we’ll now suffer the consequences. If this time Trump got 52% of some swing state rather than 48%, if the “zeitgeist” or the “vibes” have shifted, if the “Resistance” is so weary that it’s barely bothering to show up, if Bezos and Zuckerberg and Musk and even Sam Altman now find it expedient to placate the tyrant rather than standing up for what previously appeared to be their principles—well, I don’t see how any of that affects how I ought to feel.

All the same, I have no plans to flee the United States or anything, just like I didn’t the last time. I’ll even permit myself pleasure when the crazed strongman takes actions that I happen to agree with (like pushing the tottering Ayatollah regime toward its well-deserved end). And then I’ll vote for Enlightenment values (or the nearest available approximation) in 2026 and 2028, assuming the country survives until then.

---

The second plotline is the ceasefire in Gaza, and the beginning of the release of the Israeli hostages, in exchange for thousands of Palestinian prisoners. I have all the mixed emotions you might expect. I’m terrified about the precedent this reinforces and about the many mass-murderers it will free—as I was terrified in 2011 by the Gilad Shalit deal, the one that released Sinwar and thereby set the stage for October 7. Certainly World War II didn’t end with the Nazis marching triumphantly around Berlin, guns in the air, and vowing to repeat their conquest of Europe at the earliest opportunity. All the same, it’s not my place to be more Zionist than Netanyahu, or than the vast majority of the Israeli public that supported the deal. I’m obviously thrilled to see the hostages return, and even slightly touched by the ethic that would move heaven and earth to save these specific people, almost every consideration of game theory and utilitarianism be damned. I take solace that we’re not quite returning to the situation of October 6, since Hamas, Hezbollah, and Iran itself have all been severely degraded (and the Assad regime no longer exists). This is no longer 1944, when you can slaughter 1200 Jews without paying any price for it: that was the original promise of the State of Israel. All the same, I fear that bloodshed will continue from here until the Singularity, unless majorities on both sides choose coexistence—partition, the two-state solution, call it whatever you will. And that’s primarily a question of culture, and the education of children.

---

The third plotline was the end of TikTok, quickly followed by its (temporary?) return on Trump’s order. As far as I can tell, Instagram, Twitter/X, and TikTok have all been net negatives for the world; it would’ve been far better if none of them had been invented. But, OK, our society allows many things that are plausibly net-negative, like sports betting and Cheetos. In this case, however, the US Supreme Court ruled 9-0 (!!) that Congress has a legitimate interest in keeping Chinese Communist Party spyware off 170 million Americans’ phones—and that there’s no First Amendment concern that overrides this security interest, since the TikTok ban isn’t targeting speech on the basis of its content. I found the court’s argument convincing. I hope TikTok goes dark 90 days from now—or, second-best, that it gets sold to some entity that’s merely bad in the normal ways and not a hostile foreign power.

---

The fourth plotline is the still-ongoing devastation of much of Los Angeles. I heard from friends at Caltech and elsewhere who had to evacuate their homes—but at least they had homes to return to, as those in Altadena and the Palisades didn’t. It’s a sign of the times that even a disaster of this magnitude now brings only partisan bickering: was the cause climate change, reshaping the entire planet in terrifying ways, just like all those experts have been warning for decades? Or was it staggering lack of preparation from the California and LA governments? My own answers to these questions are “yes” and “yes.”

Maybe I’ll briefly highlight the role of the utilitarianism versus deontology debate. According to this article from back in October, widely shared once the fires started, the US Forest Service halted controlled burns in California because it lacked the manpower, but also this:

“I think the Forest Service is worried about the risk of something bad happening [with a prescribed burn]. And they’re willing to trade that risk — which they will be blamed for — for increased risks on wildfires,” Wara said. In the event of a wildfire, “if something bad happens, they’re much less likely to be blamed because they can point the finger at Mother Nature.”

We saw something similar with the refusal to allow challenge trials for the COVID vaccines, which could’ve moved the approval date up by months and saved millions of lives. Humans are really bad at trolley problems, at weighing a concrete, immediate risk against a diffuse future risk that might be orders of magnitude worse. (Come to think of it, Israel’s repeated hostage deals are another example—though that one has the defense that it demonstrates the lengths to which the state will go to protect its people.)

---

Oh, and on top of all the other plotlines, today—January 20th—is my daughter’s 12th birthday. Happy birthday Lily!!

Pedro Domingos is a computer scientist at the University of Washington.  I’ve known him for years as a guy who’d confidently explain to me why I was wrong about everything from physics to CS to politics … but then, for some reason, ask to meet with me again.  Over the past 6 or 7 years, Pedro has become notorious in the CS world as a right-wing bomb-thrower on what I still call Twitter—one who, fortunately for Pedro, is protected by his tenure at UW. He’s also known for a popular book on machine learning called The Master Algorithm, which I probably should’ve read but didn’t.

Now Pedro has released a short satirical novel, entitled 2040.  The novel centers around a presidential election between:

• The Democratic candidate, “Chief Raging Bull,” an angry activist with 1/1024 Native American ancestry (as proven by a DNA test, the Chief proudly boasts) who wants to dissolve the United States and return it to its Native inhabitants, and

• The Republican candidate, “PresiBot,” a chatbot with a frequently-malfunctioning robotic “body.” While this premise would’ve come off as comic science fiction five years ago, PresiBot now seems like it could plausibly be built using existing LLMs.

This is all in a near-future whose economy has been transformed (and to some extent hollowed out) by AI, and whose populace is controlled and manipulated by “Happinet,” a giant San Francisco tech company that parodies Google and/or Meta.

I should clarify that the protagonists, the ones we’re supposed to root for, are the founders of the startup company that built PresiBot—that is, people who are trying to put the US under the control of a frequently-glitching piece of software that’s also a Republican. For some readers, this alone might be a dealbreaker. But as I already knew Pedro’s ideological convictions, I felt like I had fair warning.

As I read the first couple chapters, my main worry was that I was about to endure an entire novel constructed out of tweet-like witticisms. But my appreciation for what Pedro was doing grew the more I read.

[Warning: Spoilers follow]

To my mind, the emotional core of the novel comes near the end, after PresiBot creator Ethan Burnswagger gets cancelled for a remark that’s judged racially insensitive. Exiled and fired from his own company, Ethan wanders around 2040 San Francisco, and meets working-class and homeless people who are doing their best to cope with the changes AI has wrought on civilization. This gives him the crucial idea to upgrade PresiBot into a crowdsourced entity that continuously channels the American popular will. Citizens watching PresiBot will register their second-by-second opinions on what it should say or do, and PresiBot will use its vast AI powers to make decisions incorporating their feedback. (How will the bot, once elected, handle classified intelligence briefings? One of many questions left unanswered here.) Pedro is at his best when, rather than taking potshots at the libs, he’s honestly trying to contemplate how AI is going to change regular people’s lives in the coming decades.

As for the novel’s politics? I mean, you might complain that Pedro stacks the deck too far in the AI candidate’s favor, thereby spoiling the novel’s central thought experiment, by making the AI’s opponent a human who literally wants to end the United States, killing or expelling most of its inhabitants. Worse, the Republican party that actually exists in our reality—i.e., the one dominated by Trump and his conspiratorial revenge fantasies—is simply dissolved by authorial fiat and replaced by a moderate, centrist party of Pedro’s dreams, a party so open-minded it would even nominate an AI.

Having said all that: I confess I enjoyed “2040.” The plot is tightly constructed, the dialogue crackles (certainly for a CS professor writing a first novel), the satire at least provokes chuckles, and at just 215 pages, the action moves.

Want some honesty about how I (mis)spend my time? These days, my daily routine includes reading all of the following:

• The comments on this blog (many of which I then answer)
• The Washington Post (“The Post Most” takes me about an hour a day, every day)
• The New York Times
• Scott Alexander’s Astral Codex Ten
• Zvi Mowshowitz’s Don’t Worry About the Vase (Zvi is so superhumanly prolific that reading him easily takes 12 hours per week … but it’s all good stuff!)
• Peter Woit’s Not Even Wrong (rarely updated anymore, thankfully for my reading time!)
• Quanta (how could I forget?)
• Quillette
• The Free Press
• Mosaic
• Tablet
• Commentary
• Paul Graham’s Twitter
• David Deutsch’s Twitter
• Eliezer Yudkowsky’s Twitter
• Updates and comments from my Facebook friends (this can easily take a couple hours per day)
• The quant-ph arXiv (I scan maybe 50 titles and abstracts per day, and if any papers are relevant to me, read at least their introductions)
• The science fiction and fantasy novels I read with my kids
• Whichever other books I’m currently reading

Many of these materials contain lists of links to other articles, or tweet threads, some of which then take me hours to read in themselves. This is not counting podcasts or movies or TV shows.

While I read unusually quickly, I’d estimate that my reading burden is now at eight hours per day, seven days per week. I haven’t finished reading by the time my kids are back from school or day camp. Now let’s add in my actual job (or two jobs, although the OpenAI one is ending this month, and I start teaching again in two weeks). Add in answering emails (including from fans and advice-seekers), giving lectures, meeting grad students and undergrads, doing Zoom calls, filling out forms, consulting, going on podcasts, reviewing papers, taking care of my kids, eating, shopping, personal hygiene.

As often as not, when the day is done, it’s not just that I’ve achieved nothing of lasting value—it’s that I’ve never even started with research, writing, or any long-term projects. This contrasts with my twenties, when obsessively working on research problems and writing up the results could easily fill my day.

The solution seems obvious: stop reading so much. Cut back to a few hours per day, tops. But it’s hard. The rapid scale-up of AI is a once-in-the-history-of-civilization story that I feel astounded to be living through and compelled to follow, and just keeping up with the highlights is almost a full-time job in itself. The threat to democracy from Trump, Putin, Xi, Maduro, and the world’s other authoritarians is another story that I feel unable to look away from.

Since October 7, though, the once-again-precarious situation of Jews everywhere on earth has become, on top of everything else it is, the #1 drain on my time. It would be one thing if I limited myself to thoughtful analyses, but I can easily lose hours per day doomscrolling through the infinite firehose of strident anti-Zionism (and often, simple unconcealed Jew-hatred) that one finds for example on Twitter, Facebook, and the comment sections of Washington Post articles. Every time someone calls the “Zios” land-stealing baby-killers who deserve to die, my brain insists that they’re addressing me personally. So I stop to ponder the psychology of each individual commenter before moving on to the next, struggle to see the world from their eyes. Would explaining the complex realities of the conflict change this person’s mind? What about introducing them to my friends and relatives in Israel who never knew any other home and want nothing but peace, coexistence, and a two-state solution?

I naturally can’t say that all this compulsive reading makes me happy or fulfilled. Worse yet, I can’t even say it makes me feel more informed. What I suppose it does make me feel is … excused. If so much is being written daily about the biggest controversies in the world, then how can I be blamed for reading it rather than doing anything new?

At the risk of adding even more to the terrifying torrent of words, I’d like to hear from anyone who ever struggled with a similar reading addiction, and successfully overcame it. What worked for you?

---

Update (Aug. 15): Thanks so much for the advice, everyone! I figured this would be the perfect day to put some of your wisdom into practice, and finally go on a reading fast and embark on some serious work. So of course, this is the day that Tablet and The Free Press had to drop possibly the best pieces in their respective histories: namely, a gargantuan profile of the Oculus and Anduril founder Palmer Luckey, and an interview with an anonymous Palestinian who, against huge odds, landed a successful tech career and a group of friends in Israel, but who’s now being called “traitor” by other Palestinians for condemning the October 7 massacre and who fears for his life. Both of these articles could be made into big-budget feature films—I’m friggin serious. But the more immediate task is to get this anonymous Palestinian hero out of harm’s way while there’s still time.

And as for my reading fast, there’s always tomorrow.

FOR IMMEDIATE RELEASE – From the university campuses of Assyria to the thoroughfares of Ur to the palaces of the Hittite Empire, students across the Fertile Crescent have formed human chains, camel caravans, and even makeshift tent cities to protest the oppression of innocent Egyptians by the rogue proto-nation of “Israel” and its vengeful, warlike deity Yahweh. According to leading human rights organizations, the Hebrews, under the leadership of a bearded extremist known as Moses or “Genocide Moe,” have unleashed frogs, wild beasts, hail, locusts, cattle disease, and other prohibited collective punishments on Egypt’s civilian population, regardless of the humanitarian cost.

Human-rights expert Asenath Albanese says that “under international law, it is the Hebrews’ sole responsibility to supply food, water, and energy to the Egyptian populace, just as it was their responsibility to build mud-brick store-cities for Pharoah. Turning the entire Nile into blood, and plunging Egypt into neverending darkness, are manifestly inconsistent with the Israelites’ humanitarian obligations.”

Israelite propaganda materials have held these supernatural assaults to be justified by Pharoah’s alleged enslavement of the Hebrews, as well as unverified reports of his casting all newborn Hebrew boys into the Nile. Chanting “Let My People Go,” some Hebrew counterprotesters claim that Pharoah could end the plagues at any time by simply releasing those held in bondage.

Yet Ptahmose O’Connor, Chair of Middle East Studies at the University of Avaris, retorts that this simplistic formulation ignores the broader context. “Ever since Joseph became Pharoah’s economic adviser, the Israelites have enjoyed a position of unearned power and privilege in Egypt. Through underhanded dealings, they even recruited the world’s sole superpower—namely Adonai, Creator of the Universe—as their ally, removing any possibility that Adonai could serve as a neutral mediator in the conflict. As such, Egypt’s oppressed have a right to resist their oppression by any means necessary. This includes commonsense measures like setting taskmasters over the Hebrews to afflict them with heavy burdens, and dealing shrewdly with them lest they multiply.”

Professor O’Connor, however, dismissed the claims of drowned Hebrew babies as unverified rumors. “Infanticide accusations,” he explained, “have an ugly history of racism, Orientalism, and Egyptophobia. Therefore, unless you’re a racist or an Orientalist, the only possible conclusion is that no Hebrew babies have been drowned in the Nile, except possibly by accident, or of course by Hebrews themselves looking for a pretext to start this conflict.”

Meanwhile, at elite academic institutions across the region, the calls for justice have been deafening. “From the Nile to the Sea of Reeds, free Egypt from Jacob’s seeds!” students chanted. Some protesters even taunted passing Hebrew slaves with “go back to Canaan!”, though others were quick to disavow that message. According to Professor O’Connor, it’s important to clarify that the Hebrews don’t belong in Canaan either, and that finding a place where they do belong is not the protesters’ job.

In the face of such stridency, a few professors and temple priests have called the protests anti-Semitic. The protesters, however, dismiss that charge, pointing as proof to the many Hebrews and other Semitic peoples in their own ranks. For example, Sa-Hathor Goldstein, who currently serves as Pithom College’s Chapter President of Jews for Pharoah, told us that “we stand in solidarity with our Egyptian brethren, with the shepherds, goat-workers, and queer and mummified voices around the world. And every time Genocide Moe strikes down his staff to summon another of Yahweh’s barbaric plagues, we’ll be right there to tell him: Not In Our Name!”

“Look,” Goldstein added softly, “my own grandparents were murdered by Egyptian taskmasters. But the lesson I draw from my family’s tragic history is to speak up for oppressed people everywhere—even the ones who are standing over me with whips.”

“If Yahweh is so all-powerful,” Goldstein went on to ask, “why could He not devise a way to free the Israelites without a single Egyptian needing to suffer? Why did He allow us to become slaves in the first place? And why, after each plague, does He harden Pharoah’s heart against our release? Not only does that tactic needlessly prolong the suffering of Israelites and Egyptians alike, it also infringes on Pharoah’s bodily autonomy.”

But the strongest argument, Goldstein concluded, arching his eyebrow, is that “ever since I started speaking out on this issue, it’s been so easy to get with all the Midianite chicks at my school. That’s because they, like me, see past the endless intellectual arguments over ‘who started’ or ‘how’ or ‘why’ to the emotional truth that the suffering just has to stop, man.”

Last night, college towns across the Tigris, Euphrates, and Nile were aglow with candelight vigils for Baka Ahhotep, an Egyptian taskmaster and beloved father of three cruelly slain by “Genocide Moe,” in an altercation over alleged mistreatment of a Hebrew slave whose details remain disputed.

According to Caitlyn Mentuhotep, a sophomore majoring in hieroglyphic theory at the University of Pi-Ramesses who attended her school’s vigil for Ahhotep, staying true to her convictions hasn’t been easy in the face of Yahweh’s unending plagues—particularly the head lice. “But what keeps me going,” she said, “is the absolute certainty that, when people centuries from now write the story of our time, they’ll say that those of us who stood with Pharoah were on the right side of history.”

Have a wonderful holiday!