Let's talk about supertasks, which are tasks involving infinitely many steps.
Consider a puzzle called Thompson's Lamp. It is hard to believe, but there are hundreds of papers in the academic literature devoted to it. The setup is simple: you are at home reading in your study as the twilight fades, so you turn on the lamp. It is a little too bright, so you switch it off. It is then 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. After exactly one minute, you have turned the lamp on and off infinitely many times. The lamp cycles on, off, on, off, faster and faster, completing infinitely many steps in finite time.
The question Thompson asked concerns the intelligibility of the supertask itself: what is the state of the lamp after one minute? At time T = 1, is it on or off? Is that question even well-defined? Is the answer determined by the description of the task?
There are, of course, physics-based objections one can raise against the thought experiment. It is not physically possible to flick a switch so rapidly toward the end of the sequence. Electric current flows at a finite rate, so the lamp could not respond to those vanishingly brief intervals. And every period 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 have had infinitely many distinct intervals of being on. These objections are quite strong.
They are, however, beside the point. What is really at stake is not whether a supertask can be performed in physical reality, but whether it is even logically coherent, whether a task involving infinitely many steps is intelligible at all. Mathematically, we can easily construct a step function that behaves exactly as described: on over the interval from zero to one-half, off over the next quarter, on over the next eighth, and so forth. The question then becomes what value the function takes at the limit point T = 1. And the mathematical answer is straightforward: there is no obstacle to assigning any value we like at that point. The function could be on there, or off, or left undefined. Mathematics alone does not determine it.
Let's return to the Zeno situation. Zeno argued that it is not possible to walk from here to there. I want to consider not the first version of his paradox, but rather the second: 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 accomplished infinitely many things along the way. You first reached the halfway point, then the halfway point of what remained, then the halfway point 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, 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 stage of that walk as a separate accomplishment.
This suggests a different way of thinking about Thomson'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. In doing so, however, you have performed infinitely many actions: you left it on during the first half of that period, then again during the next quarter, then during half of what remained, and so on indefinitely.
This does not seem problematic in any way. You simply left the lamp on for a minute, and we can view that ordinary task as a supertask by dividing the action into these infinitely many successive moments. Equally, one could leave the lamp off for the entire minute; that is another trivial supertask of the same kind. It appears, then, that in at least some cases, performing a supertask is entirely unproblematic.
Consider a particular supertask I find especially illuminating, known as the Deal with the Devil. Suppose you have made some shrewd investments and find yourself carrying infinitely many dollar bills, with serial numbers 1, 3, 5, and so on, all the odd-numbered bills. You enter an underground bar where the Devil is sitting at a table piled high with money. He holds all the even-numbered bills: 2, 4, 6, and so on. The Devil has a particular attachment to your dollar bills and is willing to pay a premium to acquire them, two dollars for every one of yours.
He offers you a two-for-one exchange, and at first this seems harmless enough. You would still have infinitely much money, and trading at two-for-one surely cannot leave you worse off. So you agree, and the Devil draws up a contract specifying exactly how the exchange will be carried out in supertask fashion. In the first half-hour, he gives you two dollar bills and takes one from you. In the next quarter-hour, he does the same. In the next eighth of an hour, again the same, and so on through the geometric series. After one hour, all infinitely many trades are complete.
The contract, however, is very specific about the order of the transactions. The Devil always buys from you your currently lowest-numbered bill, and he always pays you with higher-numbered bills. At the start you hold bills 1, 3, 5, 7, 9, and so on. In the first round, he gives you bills 2 and 4 and takes bill number 1. In the next round, he gives you bills 6 and 8 and takes bill number 2, which he had just paid you, and which is now your lowest-numbered bill. In the round after that, he gives you 10 and 12 and takes bill number 3. Then 14 and 16 for bill number 4, and so on.
The pattern becomes clear: because the Devil always buys your currently lowest-numbered bill and always pays with higher-numbered bills, your lowest-numbered bill grows larger and larger as the process continues. Every single bill is eventually purchased by the Devil at some stage of the supertask. When all the trades are complete, the Devil holds every bill, and you are left with nothing.
This example illustrates how supertask transactions can behave in ways that defy ordinary intuition about infinite exchanges. A deal that appears straightforwardly beneficial, receiving two dollars for every one, can result in total ruin, depending on the precise order in which the infinitely many steps are carried out. The details of how an infinitary process unfolds matter enormously, and the results are sometimes deeply surprising.
Here is another example of a similar kind. Suppose you have lost a bet with your friends, and the agreement is that you must stand in humiliation holding a large, empty wool sack. Nearby is a pile of infinitely many billiard balls. Your task is to undertake a certain supertask procedure: at each step, you take two billiard balls from the pile and put them into the sack, and then you remove one billiard ball from the sack and discard it permanently. Moreover, you must perform these steps faster and faster, the first step taking half a minute, the second a quarter of a minute, the third an eighth of a minute, and so on, so that after exactly one minute you will have completed infinitely many steps. You are 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 exactly n balls in the sack. The sack grows heavier and heavier as the procedure continues. How could it possibly be empty after infinitely many steps? Nevertheless, redemption is achievable, and the method depends critically on which ball you choose to remove at each step.
Think of the billiard balls as numbered by the natural numbers: ball 0, ball 1, ball 2, and so on. At every stage, you add the next two balls from the pile, but you always remove the lowest-numbered ball currently in the sack. On the first step, you place balls 0 and 1 into the sack and remove ball 0, the lowest. On the second step, you place balls 2 and 3 into the sack and remove ball 1. On the third step, you place balls 4 and 5 into the sack and remove ball 2. In general, ball n is removed from the sack on the nth step and is never returned.
When the supertask is complete, the sack must be empty. For suppose some ball were still inside: what number could it have? It cannot be ball n for any particular n, because ball n was removed at step n and never re-entered the sack. Since every ball has been removed at some finite stage, no ball remains, and the sack is indeed empty at the end.
This is another striking illustration of how supertasks can produce outcomes that simply have no finite analogue. If you performed only finitely many steps, the net gain of one ball per step would guarantee that the sack contains exactly n balls after n steps. Yet by arranging the details in precisely this way, always discarding the lowest-numbered ball, the infinite completion of the procedure yields an empty sack.
We can also arrange for the sack to be completely full, containing infinitely many balls, at the end of the process. To achieve this, always remove the highest-numbered ball added in each step. Put in balls zero and one and take out ball one; put in balls two and three and take out ball three; put in balls four and five and take out ball five. In this way, all the even-numbered balls remain in the sack, while all the odd-numbered balls are the ones removed.
This suggests a natural generalization: how could one arrange the process so that exactly the prime numbers remain in the sack at the end? Or so that exactly the multiples of 17 remain? The answer turns out to be quite robust. One can design a process so that any given target set is precisely what remains at the end. There are, in fact, necessary and sufficient conditions on the target set that determine exactly when this can be achieved.
There is a stochastic way of thinking about the balls-in-a-sack puzzle, that is, thinking of it as a random process. Suppose that whenever you add two balls to the sack, the ball you then remove is chosen uniformly at random from all the balls currently in the sack. You start with an empty sack, add two balls, and pick one at random. Then you add two more, giving three balls in the sack, 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 of this supertask? Will there be any balls left in the sack?
Consider one particular ball from the very first pair placed in the sack, and ask how likely it is to survive each successive step. At the first step there are two balls in the sack, so our chosen ball has a one-half chance of not being selected for removal. Given that it survives the first step, two more balls are added to give three in total, so it has a two-thirds chance of surviving the second step. Given that it survives the first two steps, two more balls are added to give four in total, so it has a three-quarters chance of surviving the third step.
A clear pattern emerges. At the n-th step, the probability of surviving that step, given survival of all previous steps, is n over n + 1. The probability of surviving all n steps is therefore the product one-half times two-thirds times three-quarters, continuing up to n over n + 1. This is a telescoping product: the twos cancel, the threes cancel, the fours cancel, and so on, leaving simply 1 over n + 1.
As n grows large, 1 over n + 1 approaches zero. The probability that our ball survives infinitely many steps must be less than 1 over n + 1 for every n, which forces it to be exactly zero. In other words, the probability that any particular ball is never chosen for removal is zero.
It is a probability-zero event for a given ball never to be picked. The same argument applies to balls added at later stages. Consider the balls in the sack at stage k: there is a k over k+1 chance of surviving the next round, then k+1 over k+2, and so on, multiplying through to k+n over k+n+1. The same cancellation phenomenon occurs, leaving us with k over k+n+1. For 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. That phrase, almost surely, is a technical term used by probabilists with a very precise meaning: the probability of the event in question is 100%. This is importantly different from being logically certain, and that distinction is the philosophical point at issue here.
In this kind of stochastic reasoning, a probability-zero event and an impossible event are not the same thing. Just because something has probability zero does not mean it is logically impossible. It is logically possible, for instance, that some red ball is simply never chosen, that on every round it happens to be passed over. That is logically possible, yet it is probability zero, as our calculation shows: 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 must keep in mind that probability zero and impossibility are not the same thing.
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, any particular ball is almost surely chosen and removed at some stage, so with probability one we should expect the sack to be empty.
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 we concluded afterwards, however, is 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, we want to say it is very likely that every ball is chosen at some stage.
The subtle gap, then, is this: how do we move from a probability calculation about every individual ball to the claim that almost surely something is true of every ball simultaneously? It may be helpful to think about the situation of a dartboard.
Suppose we are playing darts and throwing at a dartboard with a uniform probability distribution: the dart will land somewhere on the board, and the probability that it lands in any particular region is simply the ratio of that region's area to the total area of the dartboard. For example, the probability of landing on the left half is one-half, since the left and right halves 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. Yet the dart must land somewhere: it will hit the board and come to rest at some specific point. That means the dart will almost certainly strike a point whose probability of being hit was zero. In other words, almost surely, some probability-zero event will occur.
There is a compact way of putting this: it is very likely that rare things happen. The space of possible outcomes is so enormous that, while any particular outcome is vanishingly unlikely, it is virtually certain that one of them will occur. A coin flipped ten times will produce some specific sequence of heads and tails, and that particular sequence had probability only 1/210 — yet some sequence is guaranteed to appear. This is mildly paradoxical in appearance, but on reflection it is quite natural.
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 to be removed, and from this we conclude that almost surely all the balls are removed. For any particular point on the dartboard, it is very likely the dart will not land there, but we do not conclude that the dart is unlikely to land anywhere at all, since it certainly will land somewhere. What justifies making the inference in the balls case but not in the dartboard case?
The answer lies in the philosophy of probability and, specifically, in the distinction between countable and uncountable collections. The number of balls is only a countably infinite collection, whereas the number of points on the dartboard is uncountably infinite. Probability theory is countably additive: a countable union of probability-zero events still has probability zero. This means that when we have a countable list of probability-zero events, we can legitimately conclude that the probability of any one of them occurring is still zero. That inference is not available for uncountable collections, which is precisely the situation with the dartboard.
Exploring the subtle differences between these two cases leads directly into the philosophy of probability and into the deeper question of why we require our probability measures, and Lebesgue measure more generally, to be countably additive rather than something stronger.
Let us consider another supertask: the Chocolatier's Game. This is a two-player game. One player is the chocolatier, who serves up exquisite chocolate creations on a serving platter. The other player is the glutton, who eats the chocolates as the game proceeds.
In this version of the game, play continues for infinitely many rounds. On every round, the chocolatier serves finitely many new chocolate creations, but the glutton is allowed to eat only one. The chocolates accumulate on the serving platter. Perhaps the chocolatier serves seventeen chocolates, and the glutton picks one and eats it; then thirty-seven more arrive on the next round, and the glutton again picks one; then perhaps two more arrive, and the glutton picks one from among all the chocolates accumulated so far.
The glutton wins if he eats every single chocolate that was ever served — every chocolate must be eaten at some stage. We can think of the entire infinite process as completing in a finite amount of time, using the geometric-series reasoning we have already discussed, though nothing actually turns on that decision. The logic of the game is simply that there are infinitely many steps, and we ask who has won once all the steps have been made, regardless of how long that took.
At first glance, it might seem impossible for the glutton to eat all the chocolate. At every stage, the number of chocolates on the platter is increasing and growing without bound, so how could the glutton possibly finish them all? But drawing on the ideas from the Deal with the Devil and the Balls in a Sack puzzle, we can see that the glutton can in fact win.
Here is a winning strategy. The glutton will be systematic, mentally arranging all the chocolates on the platter into a queue — a line. Whenever new chocolates arrive, they are added to the back of the queue, and the glutton always eats from the front. This is precisely the stock-rotation method used in any well-run kitchen: new supplies go to the back of the cupboard, and one always cooks with the oldest items from the front, ensuring that everything is eventually used.
This queue strategy is a winning strategy for the glutton. For any particular chocolate ever served, it occupies a definite position in the queue at the moment it arrives. Since only finitely many chocolates stand ahead of it in line, we know exactly which turn that chocolate will be eaten on — and therefore it will be eaten. Since this reasoning applies to every chocolate ever served, every chocolate is eaten at some finite stage. After infinitely many steps, the glutton will have eaten every single chocolate. The glutton has a winning strategy in the Chocolatier's Game.
There is another version of the chocolatier's game — a slightly harder version. What makes it appealing is that it begins with the easy case we just discussed, which is quite clear, and then becomes progressively more difficult. In fact, one can make it harder and harder, and in the end the chocolatier's game becomes quite sophisticated mathematically. I will only 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 places down infinitely many chocolates, but the glutton can still eat only one. The chocolatier then serves infinitely many more, the glutton eats just one, and so on. The claim is that the glutton can still win.
The queuing strategy no longer works here. If we think of the first round's chocolates as forming a queue, with the second round's chocolates placed behind them, the glutton will never reach the round-two chocolates at all — every one of the countably many stages will be spent eating through the round-one chocolates, and rounds two, three, and beyond will never be reached. We must think 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 occupy the first row, the second-round chocolates occupy the second row, the third-round chocolates the third row, and so on. The glutton then eats the chocolates according to a zigzag path through this matrix — a winding diagonal path that sweeps back and forth across the rows.
It is clear that every chocolate ever served will appear on this winding path at some finite position. Moreover, every chocolate on the path has only finitely many chocolates preceding it — namely, those in the triangular region above and to the left of it. Therefore, each chocolate will be eaten on precisely the turn corresponding to its position along the path. Even though the chocolatier serves infinitely many chocolates on each turn and the glutton eats only one, the glutton can systematically work through them so that every chocolate is eventually eaten. The glutton wins.
The strategy for the glutton described earlier requires paying attention to the order in which the chocolates are served. One might ask, however, whether the glutton really needs to track that history at all. Perhaps there is a strategy that tells the glutton which chocolate 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 options are available to the chocolatier. In particular, can the chocolatier repeat chocolates — can they serve the exact same chocolate more than once? If a memory-free strategy existed and repetition were permitted, the chocolatier could exploit this immediately. Suppose the chocolatier places two chocolates before the glutton and the glutton eats one; the chocolatier could then replace that eaten chocolate with an identical one. Since the glutton's tactic depends only on the current set of chocolates on offer, the same choice would be made again, and the chocolatier could simply keep replacing that chocolate indefinitely.
The result is that the other chocolate would never be chosen. This gives a straightforward argument that if the chocolatier is permitted to serve identical chocolates repeatedly, no memory-free strategy for the glutton can exist. To make the problem genuinely interesting, then, we must impose the restriction that the chocolatier must serve each chocolate at most once.
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 — menu item number zero, menu item number one, menu item number two, and so on. This is not to say the chocolatier must serve all those chocolates or in that order; those are simply the possible chocolates available to serve. In that case, the glutton has a winning tactic: always eat the chocolate with the lowest menu item number. At any stage, there may be finitely many or even infinitely many chocolates on the serving platter, but one of them will be the lowest-numbered item. If the glutton always eats that one, he will eventually eat every chocolate, because any particular chocolate has only finitely many items ahead of it on the menu. No chocolate can remain at infinity, since it would have been the lowest-numbered item at some point and would therefore already have been eaten.
In other words, if the chocolatier is merely countably creative — meaning the space of possible chocolates 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: the width of the glazing, or the density of the liqueur, is drawn from a real number, so each real number corresponds to its own strictly distinct chocolate type. In that case, one can prove that it is not possible for the glutton to have a winning tactic — though the argument is mathematically sophisticated, so we will not go into it here.
There is, however, something very close to a winning tactic even in the uncountably creative case. Specifically, the glutton has a winning tactic provided he is also allowed to use the information of the most recently eaten chocolate — that is, at any stage he may consider both the chocolates currently on offer and the taste of the chocolate he just ate, and use both pieces of information to determine his choice. It turns out that if the chocolatier is allowed to serve only finitely many chocolates at each stage, and if the axiom of choice is true, then the glutton has a winning tactic of this kind, one that is otherwise memory-free but incorporates the taste of the previous chocolate. The argument involves the axiom of choice, well-orders, and related ideas — and it is all quite fascinating.
That is all for this lecture. I hope you enjoyed the supertasks and the chocolatier's game. See you next time.