Supertasks: Doing Infinitely Many Things — Lectures on Infinity (Lecture 2)
Let us explore several paradoxical supertasks—the deal with the Devil, balls in a sack, the Chocolatier's game, and more.
Welcome to the Lectures on Infinity, a series of lectures exploring all my favorite paradoxes and conundrums.
In this second lecture, we explore the concept of supertask—a task involving infinitely many separate actions or steps. We shall play with Thomson’s lamp, turning it on and off infinitely in a finite duration of time, before encountering the dangerous Deal with the Devil. And then infinitely many billiard balls in a sack! Will the Glutton win in the Chocolatier’s game? Let’s find out.
I shall be gradually sharing the individual lectures here on Infinitely More in the coming weeks and months.
Please enjoy!
Find the lectures here on Infinitely More in the lectures-on-infinity tag.
The lectures will appear on YouTube.
The whole lecture course is hosted at Ergo: Lectures on Infinity.
Find other philosophy lecture courses at Ergo.org.
This lecture is based on my essay Supertasks.
The essay also appears in my new book, The Book of Infinity.
Supertasks: Doing Infinitely Many Things
A lightly edited transcript. Timestamps link to the video on the Ergo website.
What Are Supertasks?
Let’s talk about supertasks, which are tasks involving infinitely many steps.
Thompson’s Lamp: On or Off After Infinity?
There is a famous supertask puzzle known as Thomson’s lamp, where you turn a lamp on and off infinitely many times in a finite period. It is hard to believe, but there are hundreds of papers in the academic literature devoted to it. The setup is domestic and familiar: you are at home reading in your study as the twilight fades, so you turn on the light. But it is a little too bright, so you switch it off again. Then it is a little too dark, so you switch it back on again, and so on.
Thompson’s Lamp is a supertask. You turn the lamp on for half a minute, then off for a quarter of a minute, then on for an eighth of a minute, then off for a sixteenth of a minute, and so on, following the geometric series discussed in another lecture. After exactly one minute, you have turned the light on and off infinitely many times, cycling on, off, on, off, on, off, faster and faster. The question Thompson asked about this scenario concerns the intelligibility of the supertask itself: what is the state of the lamp after one minute? Is it on, or is it off?
To be precise about the timing: we run from time zero to time one, representing one minute. The lamp is on for the first half-minute, then off for the quarter-minute that follows, then on, then off, alternating infinitely many times within that single minute. The question is whether, at T equal one, the lamp is on or off, and indeed whether that question is even well-posed or determined.
There are, of course, all kinds of physics-based objections one can raise against the thought experiment. It is not physically possible to flick a light switch so rapidly toward the end of the sequence. Electric current flows at a finite rate and could not switch the lamp on and off in those vanishingly narrow intervals. And every interval in which the lamp is on requires the emission of photons, yet there may be only finitely many photons available, so the lamp could not genuinely be on during infinitely many distinct intervals. These objections are quite strong.
But they are really beside the point, because what is at stake is not whether we can actually perform a supertask in physical reality. The real question is whether it is even logically coherent, whether it is intelligible to speak of a task involving infinitely many steps. Mathematically, for instance, we can easily construct a step function that behaves exactly as described: on between zero and one-half, then off, then on, then off, alternating in the familiar pattern. The question then becomes what the function is doing at the limit point T equal one. And mathematically, of course, a function can behave in precisely this way and take any value you like at T equal one. There is no mathematical objection to stipulating that it is on at that point, or off, or anything else.
Zeno’s Paradox Makes Supertasks Real
Let us return to the Zeno situation. Zeno argued that it is not possible to walk from here to there, and I want to consider not the first version of that paradox but the second, in which to go from here to there you first go halfway, then halfway of what remains, then halfway of what remains again, and so on. When you walk from here to there, you have done infinitely many things along the way: you first reached the halfway point, then the halfway point of what remained, then the halfway point of what remained after that, and so on.
The picture looks just like this. In order to walk from here to there, you first had to reach this point, then this point, then this point, then this point, and so on. It seems, then, that we can perform a supertask, and that the idea is perfectly intelligible. If you believe that you can walk from here to there, you should also believe that you can do infinitely many things, provided we view each of those intermediate accomplishments as a separate thing you have done in the course of that walk.
Trivial Supertasks Hide in Plain Sight
This suggests a different way of thinking about Thompson’s Lamp. Suppose we simply leave the lamp on for the first half-minute, then continue to leave it on for the next quarter-minute, then for half of what remains after that, and so on. You have left the lamp on for one minute altogether, but in doing so you have, in a sense, done infinitely many things: you left it on for the first half of that period, then again for half of what remained, then for half of what remained after that, and so on indefinitely.
That doesn’t seem problematic in any way. You simply left the lamp on for a minute, and we can view that as an ordinary task which can equally well be thought of as a supertask, if we divide the action into these infinitely many successive intervals. Equally, we could have left the lamp off the entire time, which would constitute another trivial supertask of the same kind. So it seems that in at least some cases, we can perform a supertask without any difficulty at all.
The Deal with the Devil
Let me tell you about a particular supertask that I find especially compelling. It is called the Deal with the Devil. Suppose you have made some shrewd investments and now carry with you infinitely many dollar bills, numbered with all the odd numbers: one, three, five, and so on. You walk into an underground bar where the Devil is sitting at a table piled high with money. He holds all the even-numbered bills: two, four, six, and so on.
The Devil takes a particular liking to your dollar bills and offers to pay a premium for them. Specifically, he will give you two dollar bills for each one of yours. That sounds like it might not matter much: two for one still leaves you with infinitely much money, so you seem no worse off. You think, “What’s the harm?” and agree to the deal.
The Devil draws up a contract specifying exactly how the exchange will be carried out, and of course it will be carried out as a supertask. In the first half hour, he gives you two dollar bills and takes one from you. In the next quarter hour, he gives you two more and takes one more. In the next eighth of an hour, the same again, and so on through the geometric series. After one hour, all infinitely many trades are complete.
But the contract is very fussy about the order of the exchanges. The Devil always buys from you your currently lowest-numbered bill, and he always pays you with higher-numbered bills. So at the start you hold bills one, three, five, seven, nine, and so on. In the first round, he gives you bills two and four and takes bill number one. In the next round, he gives you six and eight and takes bill number two, which he had just paid you. In the round after that, he gives you ten and twelve and takes bill number three, and so on.
You can see what is happening. Because the Devil always buys your currently lowest-numbered bill and always pays you with higher-numbered bills, your lowest-held bill keeps growing without bound as the process continues. Every single bill is eventually purchased from you at some stage of the supertask. When all the trades are complete, the Devil holds every bill, and you have nothing at all.
I like this example because it shows how supertask transactions do not always behave the way finite transactions do. Even though each individual trade looked favorable, or at worst neutral, the details of how the process unfolds in this infinitary manner produce a result that is genuinely surprising. We have to pay close attention to the order and structure of the process, not just its local character at each step.
Balls in a Sack: Empty After Infinity?
Here is another puzzle in the same spirit. Suppose you have lost a bet with your friends, and the agreed penalty is that you must stand in humiliation holding a large, empty wool sack. Nearby is a pile of infinitely many billiard balls. The procedure you must carry out is this: at each step, you take two billiard balls from the pile and put them into the sack, and then you take one billiard ball out of the sack and discard it permanently. Moreover, you must perform each step faster and faster. If the first step takes half a minute, the second a quarter of a minute, the third an eighth, and so on, then after exactly one minute you will have completed infinitely many steps, finishing the supertask in finite time.
You will be redeemed in the eyes of your friends if, at the end of this procedure, the sack is empty. At first this seems impossible. The sack is empty at the start, yet at every step you are putting two balls in and taking only one out, so after n steps there are n balls in the sack. The sack grows heavier and heavier as you go. How could it possibly be empty after infinitely many steps?
And yet redemption is achievable, provided you arrange the procedure in the right way. Think of the billiard balls as numbered by the natural numbers: ball zero, ball one, ball two, and so on. At every stage, you place the next two balls into the sack, but you always remove the lowest-numbered ball currently in the sack. So on the first step you put balls zero and one into the sack and remove ball zero, the lowest. On the second step you put balls two and three in and remove ball one. On the third step you put balls four and five in and remove ball two. And so on.
The key observation is that ball n is removed from the sack on the nth step and is never returned. So when you ask what balls remain in the sack after the supertask is complete, the answer must be: none. Any particular ball you name, say ball n, was removed at step n and discarded. There is no ball that could be sitting in the sack at the end, because every ball has been accounted for and removed at some finite stage.
This is another instance of the strange character of supertasks. If you performed only finitely many steps, the count of balls in the sack after n steps would simply be n, growing without bound. Yet when the infinitely many steps are arranged in precisely this way, the sack is empty at the conclusion. The details of how you carry out the infinite procedure turn out to matter enormously.
Controlling What Remains in the Sack
We can also arrange for the sack to be completely full, with infinitely many balls remaining at the end. Suppose we always remove the highest-numbered ball in each step. We put in balls zero and one and take out ball one, then we put in balls two and three and take out ball three, then we put in balls four and five and take out ball five. In this way, all the even-numbered balls end up in the sack, and all the odd-numbered balls are the ones we remove.
This naturally raises further questions. How could one arrange the process so that exactly the prime numbers remain in the sack at the end? Or could one design a process so that exactly the multiples of 17 remain? The answer turns out to be quite robust: one can actually design a process so that any given target set is exactly what remains at the end. One can even find necessary and sufficient criteria on the target set that make this possible.
Random Removal and Vanishing Probability
There is perhaps a stochastic way of thinking about the balls-in-a-sack puzzle, meaning a way of treating it as a random process. Suppose that whenever you put two balls into the sack, the ball you then remove is chosen randomly from all the balls currently in the sack. You start with an empty sack, put two balls in, and pick one of them at random. Then you put two more balls in, giving you three, and again remove one at random, leaving two. Two more go in, one comes out at random, and so on. The question is: what should we expect at the end? Will there be any balls left in the sack, and if so, how many?
Let us focus on one particular ball from the very first step and ask how likely it is to survive. On the first step, two balls are in the sack, so our chosen ball has a one-half chance of not being the one removed. Given that it survives that first step, two more balls are added, making three in total, and our ball survives if either of the other two is chosen, giving it a two-thirds chance of surviving the second step. On the third removal, there are four balls in the sack, so the probability of surviving that step, given survival through the first two, is three-quarters. The pattern is now clear: at step n, the probability of surviving that step, conditional on having survived all previous steps, is n over n plus one.
The probability that our ball survives all n steps is therefore the product of these conditional probabilities: one-half times two-thirds times three-quarters, and so on up to n over n plus one. Because of the telescoping cancellation, the twos cancel, the threes cancel, the fours cancel, and every intermediate factor cancels, leaving simply one over n plus one. So the probability that a given ball has not been discarded after n steps is one over n plus one, which approaches zero as n grows large.
Since the probability of surviving n steps is one over n plus one for every n, the probability of surviving infinitely many steps must be less than this quantity for every n. That forces the probability to be zero. In other words, the chance that any particular ball is never chosen for removal is exactly zero.
Probability Zero Does Not Mean Impossible
The probability that a given ball is never picked is zero. The same argument applies to the balls added at later stages. If I consider the balls remaining in the sack at stage k, there is a k over k+1 chance of surviving the next round, since that is the number of balls in the sack, then k+1 over k+2, and so on, multiplying k+n over k+n+1. We get the same cancellation phenomenon, leaving us with k over k+n+1. For any fixed k, as n grows large, this quantity goes to zero.
Therefore, for any particular ball at any particular stage, the probability that it survives infinitely many steps is zero. For every ball, almost surely it will be chosen at some stage. I should note that “almost surely” is a technical term as probabilists use it, with a very particular meaning: it means that the probability of that event is 100%. That is different from being logically certain, and this is the philosophical point I want to make.
In this kind of stochastic reasoning, the difference between a probability-zero event and an impossible event is not trivial. Just because something has probability zero does not mean it is logically impossible. It is logically possible, for example, that on the first round one of the balls is red and that red ball is simply never chosen. That is logically possible, and yet it is probability zero, as we calculated: the probability of the red ball never being chosen is less than 1 over n+1 for every n, and therefore the probability of that event is zero.
One has to keep in mind that probability zero and impossible are not the same thing.
Every Ball vs. All Balls: A Subtle Gap
We can still reason probabilistically here. For any particular ball, it is very likely to be chosen at some stage, and so what we expect at the end is that the sack should be empty. With probability one, we should expect the sack to be empty, because with probability one any particular ball is almost surely chosen at some stage.
But notice what happened in that reasoning. What we argued first is that for every ball, almost surely it is chosen at some stage. What I said afterwards, however, was that almost surely every ball is chosen. Those are not quite the same thing. For any particular ball, it is very likely to be chosen at some stage and removed, but that is different from the sack being empty. For the sack to be empty, I want to say it is very likely that every ball is chosen at some stage.
So the question is: how do we move from a probability calculation about every individual ball to the claim that almost surely something is true of every ball? Perhaps it is helpful here to think about the situation of a dartboard.
Dartboards and Countable Additivity
Suppose we are playing darts and I am throwing darts at a dartboard with a uniform probability distribution over where the dart lands. The probability that the dart lands in any particular region is simply the ratio of that region’s area to the total area of the dartboard. So, for example, the probability that the dart lands on the left side is one-half, since the left and right sides have equal area. Similarly, the probability of landing in any given quadrant is one-quarter, and so on.
Now, the probability of hitting any particular point is zero, because a point has zero area. If we think of the dartboard as a continuum of points, the probability of hitting any exact point is zero. But here is the tension: I want to say, for every point, almost surely the dart does not hit that point. Am I then willing to say that almost surely the dart does not hit any point at all? No, because the dart is going to hit some point. I will throw it, it will land, and it will land exactly somewhere. That means the dart will hit a point that was itself a probability-zero event.
There is a useful way of putting this: it is very likely that rare things happen. I throw the dart and it hits whichever point it hits. For any particular point, that outcome was a very rare event, yet it is virtually certain that some such rare event will occur. The space of possible outcomes is so enormous that, even though each individual outcome is vanishingly unlikely, one of them is guaranteed to happen.
We can see the same phenomenon with a coin. Suppose I flip a coin ten times and obtain some particular sequence of heads and tails. Almost surely I will get some sequence, but any particular sequence has probability 1 over 2 to the 10, which is a very small number. So it is very likely that a rare event occurs. It is a little paradoxical, but it should not be too paradoxical, because in a sense it is obvious: the space of things that could occur is enormous, and it is very likely that one of them will happen.
Returning to the stochastic process with balls in a sack, we seem to be reasoning in exactly the same way in both cases. For any particular ball, it is very likely that it gets removed, and I want to conclude from that that it is very likely all the balls are removed. But I do not want to make the same move with the dartboard: for any particular point, it is very likely the dart will not land there, yet I cannot conclude that it is very likely the dart will not land anywhere, because it certainly will land somewhere. So how can the inference be justified in the balls case but not in the dartboard case?
The answer lies in the philosophy of probability and in a fundamental asymmetry: the number of balls is only a countably infinite collection, whereas the number of points on the dartboard is an uncountably infinite collection. Probability theory is countably additive. When we have a countable list of probability-zero events, we can conclude that the probability of any one of them occurring is still zero. But we cannot make that move in an uncountable setting. To examine the subtle differences between these two situations is to enter deeply into the philosophy of probability, and in particular into the question of why we want our probability measures, and Lebesgue measure, to be countably additive but not required to be more than that.
The Chocolatier’s Game: Finite Servings
Let us consider another supertask, which I call the Chocolatier’s Game. It is a game played between two players: the chocolatier, who serves exquisite chocolate creations on a kind of serving platter, and the glutton, who eats them as the game proceeds. The game has infinitely many rounds, and on every round the chocolatier serves finitely many new chocolates, while the glutton is allowed to eat only one. The uneaten chocolates accumulate on the platter.
So perhaps the chocolatier serves 17 chocolates, and the glutton picks one and eats it. Then 37 more arrive on the next round, and the glutton again picks one. Then perhaps just two more are added, and the glutton picks one from among the accumulating chocolates on the platter. We can think of this entire infinite process as completing in a finite amount of time, using the geometric series reasoning we have already discussed, but in fact nothing is at stake in that decision. The logic of the game is simply that there are infinitely many steps, and then we ask who won afterwards. It is irrelevant whether the process took finite or infinite time.
The glutton wins if he eats every single chocolate that was ever served. At first glance this might seem impossible, because at every stage of the game the number of chocolates on the platter is increasing and growing without bound. It would appear absurd for the glutton to eat all of them. But if we apply the ideas from the deal-with-the-devil scenario or the balls-in-a-sack puzzle, we can see that the glutton can in fact win.
Here is one strategy. The glutton will be systematic, mentally organizing the chocolates on the platter into a queue. New chocolates, however many arrive, are always added to the back of the queue, and the glutton always eats from the front. This is precisely the stock-rotation method a restaurant uses: new supplies go to the back of the cupboard, and the oldest items at the front are always used first, ensuring that everything is turned over in time.
This queue strategy is a winning strategy for the glutton. For any particular chocolate that is ever served, it occupies a specific place in the queue at the moment it arrives, and there are only finitely many chocolates in front of it. Therefore we know exactly which turn that chocolate will be eaten on, and at that turn it will indeed be eaten. Since this reasoning applies to every chocolate ever served, every chocolate will be eaten at some stage. After infinitely many steps, the glutton will have eaten every single chocolate. The glutton has a winning strategy in the Chocolatier’s Game.
Infinite Servings and the Zigzag Strategy
There is another version of the chocolatier’s game, a slightly harder version. I like it a lot, because it begins with the easy case we just discussed, which is quite clear, and then we can make it progressively harder. In the end, the chocolatier’s game becomes quite sophisticated mathematically, and I will be hinting at those deeper developments. But we can go at least one step further.
Consider the version of the chocolatier’s game in which the chocolatier is allowed to serve infinitely many chocolates on a single turn. Each turn, the chocolatier puts down infinitely many chocolates, but the glutton can still eat only one. The chocolatier serves infinitely many, the glutton eats one; then infinitely many more, and the glutton eats one; and so on. I claim that the glutton can still win.
The queuing strategy does not work here at all. If we think of the chocolates from the first round as forming a queue, with the second-round chocolates placed behind them, the glutton will never reach the round-two chocolates. At every one of the countably many stages, the glutton will still be eating through the chocolates served in round one, and the round-two and round-three chocolates will never be reached. We have to think a little more imaginatively.
What the glutton does instead is imagine the chocolates on the serving platter as filling up an infinite matrix. The first-round chocolates are placed in the first row, the second-round chocolates in the second row, the third-round chocolates in the third row, and so on. Each entry in this matrix is a single chocolate, all of them distinct, with their exquisite glazing and cherries and whatever else. The matrix simply organizes, in the glutton’s mind, all the chocolates that will ever be served.
The glutton then eats the chocolates according to a winding zigzag path through this matrix. On the first turn the glutton eats the chocolate in position one, then moves along the path to the next position, then the next, and so on, traversing the matrix in this diagonal winding order. It is clear that every chocolate that will ever be served appears somewhere on this winding path. Moreover, every chocolate on the path has only finitely many chocolates preceding it, corresponding to the triangular region above and to the left of it in the matrix. Therefore, each chocolate will be eaten on precisely the turn whose number equals the count of chocolates preceding it on the path.
So even though the chocolatier is serving infinitely many chocolates on each turn, and the glutton is eating only one, the glutton can nonetheless proceed systematically so that every chocolate is eventually eaten at some finite stage. The glutton wins.
Can the Glutton Win Without Memory?
The strategy for the glutton we have been considering requires him to pay attention to the order in which the chocolates are served. But one might ask whether the glutton really needs to pay so much attention. Perhaps there is a strategy that tells him which chocolates to eat based only on the set of chocolates currently on offer, regardless of the order in which they have been served. This is called a memory-free strategy, and it corresponds to the distinction in game theory between a tactic and a strategy: a tactic depends only on the current situation, whereas a strategy depends on the entire history of play up to that point.
The situation becomes quite interesting once we ask what is on the menu for the chocolatier. Specifically, can the chocolatier serve the same chocolate more than once? If a memory-free strategy existed, the chocolatier could exploit it in the following way: place two chocolates before the glutton, observe which one the glutton’s tactic selects, and then simply replace that chosen chocolate with an identical one. Since the tactic depends only on what is currently on offer, the glutton would be forced to make the same choice again, and again, and again. The other chocolate would therefore never be chosen.
This gives us a straightforward way to see that if the chocolatier is permitted to serve identical chocolates repeatedly, there can be no memory-free strategy for the glutton. So let us rule that out, and stipulate that the chocolatier must not repeat identical chocolates.
Countable vs. Uncountable Creativity
The chocolatier is not allowed to repeat a chocolate ever. That constraint breaks the previous argument, and we still want to know: is there a winning tactic for the glutton? The answer turns out to depend on how creative the chocolatier is.
Suppose the list of possible chocolates the chocolatier could make is infinite in the manner of the natural numbers. There is menu item number zero, menu item number one, menu item number two, menu item number three, and so on. The chocolatier need not serve all those chocolates, nor serve them in that order; those are simply the possible chocolates available to serve. In that case, the glutton has a winning tactic, which is simply to always eat the chocolate with the lowest menu item number available.
At any stage there may be finitely many or even infinitely many chocolates on the serving platter, but one of them will always be the lowest menu item. If the glutton always eats the one with the lowest menu item number, he will eventually eat every chocolate, because any particular chocolate has only finitely many items ahead of it on the menu. Therefore no chocolate could remain uneaten at infinity, since it would have been the lowest one at some point and would already have been eaten.
In other words, if the chocolatier is merely countably creative, in the sense that the space of possible chocolates they could serve is only countable, then the glutton has a winning tactic. But what about the case where the chocolatier is uncountably creative? Perhaps there is a distinct chocolate for every real number, with some parameter such as the width of the glazing or the density of the liqueur coming from a real number, so that each real number corresponds to a strictly different chocolate type.
In that case, one can prove that it is not possible for the glutton to have a winning tactic. The argument is mathematically sophisticated, so I will not give it here, but this is one way in which the problem becomes quite deep. There is, however, something very close to a winning tactic even in the uncountably creative case.
Specifically, there is a winning tactic for the glutton in the uncountably creative case provided the glutton is also allowed to use the information of the most recently eaten chocolate. At any stage, the glutton looks at the chocolates on offer, which may be infinite, and also has the taste of the previously eaten chocolate on his tongue, and is allowed to use that information to determine which chocolate to pick. It turns out that in the case where the chocolatier is allowed to serve only finitely many chocolates at each stage, if the axiom of choice is true, then the glutton has a winning tactic that uses this memory of the previous chocolate, and the argument involves the axiom of choice and well-orders, which makes it all quite fascinating.
Wrapping Up Supertasks
That is all for this lecture. I hope you enjoyed the discussion of supertasks and the chocolatier’s game. See you next time.
The lectures will all appear in the lectures-on-infinity tag. The full collection of essays is available on Infinitely More at The Book of Infinity. And the book is also now available in printed form: