Weinersmith's God is a Liar

You know, probably

I am a big fan of Zach Weinersmith’s Saturday Morning Breakfast Comics. Aside from being funny and insightful, it often manages to blend in topics in mathematics, science, and philosophy. It has provided such gems as a delightfully accurate description of quantum computing, framed as The Talk one gives to a child entering puberty.

Unfortunately, I am also a geek, and so I am honor-bound to participate in our oldest tradition: correcting people over technicalities. Specifically, I am talking about the SMBC from February 20, 2026:

Original comic here.

As a number theorist, I am delighted that a popular cartoonist is talking about some of the classic problems in our field, and how ridiculous it is that we have absolutely no clue how to solve these seemingly simple problems. But I have a slight problem with the first panel.

There is no general way to determine whether a set of numbers contains infinitely many primes, and I can prove it.

Of course, we need to clarify some points before I can provide such a proof:

1. What do we mean when we say a “way to tell”?

2. What sort of sets of numbers are we considering?

In a certain highly trivial sense, of course there is a way to tell whether a set of numbers contains infinitely many primes: look through all of them and count how many primes there are. But this is useless to us humans, because we don’t have a way to go through the entirety of an infinite set—it would take us, literally, forever. So, instead, I am going to interpret this as asking whether there is some algorithm using which we could take a set of numbers and determine whether it contains infinitely many primes (in finite time).

But this leads us to the second problem: what sorts of sets of numbers are we considering? Whatever we come up with, it has to be something that we could actually provide as an input to our algorithm. (Those who are familiar with cardinality might recognize that there are uncountably many subsets of the natural numbers, but the set of inputs to an algorithm has to be countable, since it has to be represented by some finite number of bits. Uh oh!)

I’m going to interpret this as follows: we’ll consider just computably enumerable sets. That is, we’ll consider just those sets of natural numbers for which there exists some algorithm that enumerates the elements in this set. For example, I can write some basic code that will print all numbers of the form n²+1.

def EnumLandau():
  n = 0
  while(True):
    print(n**2+1)
    n=n+1

(I am choosing to write this in Python simply because it is very readable, but the language and hardware don’t really matter.) Similarly, I can write something that will print the sequence 1, 11, 111, 1111, and so on.

def EnumRn():
  n=1
  while(True):
    print(n)
    n = 10*n+1

I’ll leave it as an exercise to the reader on how to generate Zach’s final sequence this way. (It’s only a little harder.)

In any case, this is something that we can apply an algorithm to—it is just some finite string of symbols, which can be easily represented in binary, for example. And so now we have a perfectly well-defined question:

Does there exist an algorithm such that on an input of an algorithm that prints natural numbers, it always outputs whether infinitely many primes will be printed or not?

The answer to this is “no!” We’ll prove it by contradiction: suppose that such an algorithm does exist, and then show that something absurd follows as a result. Specifically, we will prove that such an algorithm would allow us to solve the halting problem.

---

A small aside, in case you haven’t heard of the halting problem before. (If you have, feel free to skip forward.)

The halting problem is the question of how to determine whether a given algorithm runs forever or if it eventually halts and finishes its computation. For instance, EnumLandau and EnumRn pretty clearly run forever. But here is a different example.

def Countdown():
  n = 3
  while(n > 0):
    print(n)
    n=n-1
  print("Blast off!")
  return 0

In contrast, Countdown will run for 1+3×3+2=12 steps (one defining n, three for each time we run through the loop, and then two more at the end), and then it halts (when it hits the return statement).

Here’s another example.

def FLT_search():
  n=3
  while(True):
    for a in range(1,n):
      for b in range(1,n):
        for c in range(1,n):
          for k in range(3,n):
            if(a**k+b**k==c**k):
              return (a,b,c,k)
    n = n+1

This program searches (very inefficiently) for positive integers a, b, c, k such that a^k+b^k=c^k with k≥3; if it finds such an example, it halts and returns the relevant integers. It isn’t entirely obvious whether this program runs forever or eventually halts—in fact, it is the former, but this is the content of Fermat’s Last Theorem, which was only proved in 1995.

It would be incredibly useful if we could feed such an algorithm to a computer, and it would automatically determine for us whether it eventually halts or not. Unfortunately, the halting problem is not solvable—there cannot be an algorithm that would always be able to make such a check.

Here’s a quick way to see this: suppose that there was such an algorithm—call it Halt. Now, define a program as follows:

def Turing():
  while(Halt(Turing)):
    pass
  return 0

What does Turing do? It passes itself to Halt. If Halt says that Turing halts, then Turing runs forever. If Halt says that Turing runs forever, then Turing halts. This is clearly a contradiction! Therefore, no algorithm like Halt can possibly exist.

(This is not a property of Python—you can make this proof work even for Turing machines, which are far more basic. It just requires a little bit more thought.)

---

Back to our original problem: how can we prove that no algorithm can determine whether computably enumerable sets contain infinitely many primes?

Assume that such an algorithm exists. We’re going to start with an arbitrary program P and then show that we can use our algorithm to determine whether P halts or not. As discussed above, this is a contradiction.

How to do it? We’ll need two helper functions:

1. PrimeQ: an algorithm that tests whether an integer n is prime or not, and

2. PHaltsAfter: an algorithm that runs P for n steps and returns whether it has halted.

I’ll skip writing out the implementations here, but neither is difficult. Using these, we now write the following algorithm.

def EnumPShifted():
  n = 2
  while(True):
    if PrimeQ(n) ^ PHaltsAfter(n):
      print(n)

(This includes one of the few bits of Python that really don’t look like pseudo-code: ^ stands for “exclusive-or” or “XOR”. The expression a^b is “True” if exactly one of a and b is true, and false otherwise.)

What does this do? It goes through all the natural numbers n, and then it does one of two things, depending on whether P has halted or not: if P has not halted, it prints n if it is prime; if P has halted, it prints n if it is not prime.

Therefore, if P never halts, EnumPShifted prints all prime numbers, of which there are infinitely many. (There are many proofs of this.) On the other hand, if P eventually halts, then past some point EnumPShifted never prints primes again, and so it only ever prints finitely many.

To sum up: EnumPShifted prints infinitely many primes if and only if P eventually halts. Therefore, if we have an algorithm that can always determine whether EnumPShifted prints infinitely many primes, then we can use it to determine whether P halts. But we already know that this is impossible. Q.E.D.!

---

What are we to make of all this? One explanation is that Zach Weinersmith is only human and either made a small technical mistake or chose to gloss over it for the sake of readability.

But a more entertaining possibility is that Zach’s God is lying to mess with the human. It wouldn’t be the first time.

Original comic here.