June 10, 2008

There once was a debate about whether supertasks were possible. I think just about everyone these days has taken the view that they’re weird, but not impossible. I’m ok with this as far as it goes – I think there’s a good case to be made that motion involves a supertask. So supertasks are possible in virtue of being actual. However, not all supertasks are possible – and I want to argue that a great majority of supertasks are in fact impossible.

Now, clearly we can iterate supertasks. Zeno’s runner performs two supertasks in succession by running from A to B to C. In fact, there is a supertask in between every step in the supertask from A to B – so you can have a supertask each step of which is also a supertask. An $\omega^2$-task. This motivates the following definition:

• Definition: A $\lambda$-task is a supertask such that the events in the supertask under the temporal ordering ‘later-than’ is order isomorphic to the ordinal $\lambda$.

Now, given some natural assumptions about the structure of time we can give some constraints on what kinds of supertasks are possible. We assume that time is isomorphic to the reals $\mathbb{R}$, and that events can be mapped to disjoint extended intervals in the reals that represent their duration. We can then show

• Proposition: $\omega_1$-tasks are impossible.

Since doing any uncountable $\lambda$-task involves doing an $\omega_1$-task, this is a fairly strong limit on the kinds of supertasks possible. Why is this true? Well, each event in the supertask takes up an interval of time. Since every interval of time contains a rational number, and we can assign these rationals so that each event only gets one rational each (note, it sounds like I’m using choice here – I don’t need to, the rationals can be well ordered, so just take the least one in each interval.) Since there are countably many rationals there must be only countably events in the supertask. So only countable $\lambda$-tasks are possible. What about the converse? Are all countable $\lambda$-tasks possible?

• Proposition: every countable $\lambda$-task is possible.

Why is this? Well we can assume every $\gamma$-task less than $\lambda$ is possible for transfinite induction. If $\lambda$ is a successor ordinal or 0 it’s easy, so suppose it’s a limit ordinal. Since it’s a countable ordinal we can match it’s elements up with $\omega$, so we have an enumeration $\gamma_1, \gamma_2, \ldots \in \lambda$. Since we know $\omega$-tasks are possible, and that $\gamma_i$-tasks are possible, we know that the concatenated $\omega$-task $\gamma_1 ^\wedge \gamma_2 ^\wedge \ldots$ is possible (the task performed by doing $\gamma_1$, then doing $\gamma_2$ in half the time, and so on.) But if this concatenated task is possible, then so is the $\lambda$-task. Call the ordinal we just got by concatenating: $\gamma$. If $\lambda > \gamma$ then $\gamma$ appears in the sequence $(\gamma_i)_{i\in\omega}$ so for some n $\gamma = \gamma_n < \gamma$ which is a contradiction. Alternatively, if $\lambda \leq \gamma$ then we are done – if a $\gamma$-task is possible, then so is any subtask (although I think this case is impossible anyway.)

So we have a nice characterisation of which kinds of $\lambda$-tasks are possible – precisely the countable ones. Anyway, those are all my thoughts for now – I was going to post about how this relates to hypercomputers and the incompleteness theorems, but I have to dash somewhere – some other time maybe!

1. Well, each event in the supertask takes up an interval of time.

Hi Andrew,
Since you’re providing an impossibility proof, this claim would have ot be necessary. I wonder if it is. There could not be instantanous events? It does sound strange, but I wonder why it would be impossible.

2. That is a good point. One argument I haven’t really thought through, but first popped into my mind is that the uncertainty principle should gives us that each event takes up an interval of time. It seems you could either think of time as coming in quantized chunks of Planck length (and necessarily in intervals) or as continuous in which nothing can occur in shorter than Planck length intervals.

Although, this seems that it must be true for macro-objects, I’m not entirely sure that for Planck length or smaller objects this still has to hold. Maybe superstrings can perform uncountable supertasks?

3. Hi Mike. Yes, I guess that is a serious worry. If we want to include instantaneous happenings as events, then I’m more open to the possibility of uncountable supertasks.

However, I’m not sure it is immediately clear. To get the kind of uncountable supertask you need, these instantaneous events would have to be dense in the reals (between any two reals you can find one of these events.) But this strikes me as a little weird – this means you can’t separate the events from each other, yet no two events touch one another.

I don’t think its true that any arbitrary undetached part of an event is also an event. So to get some constraints on eventhood, you should include stuff like ‘separable from the surrounding events’ and or something like this – but this kind of constraint would clearly be violated by any sequence of events that is dense.

4. WOAH! I found this blog by chance and it is way over my head! I don’t understand any of it except for the fact that you’re arguing over wether supertasks are possible or not.

I do have one question, though.

Why is this argument important, and where will its answer lead us?

Thanks. 🙂

5. Well, here’s one consequence I thought this result might have on the limits of hypercomputation.

If you allow there to be computers that can perform an infinite number of steps in a finite time, they can break the Turing barrier – e.g. you could simulate an ordinary Turing machine, and simply decide whether it ever halts, solving the halting problem (ordinary Turing machines can’t do this.) If we allow computers that can only perform $\omega$-tasks we don’t get that much computational power. However, you can extend the notion of Turing machine to allow it to run for arbitrary ordinal times (these are called infinite time Turing machines.) It turns out that an ITTM either halts before it reaches $\omega_1$ or will loop forever. So if we can get every kind up supertask up to but not including $\omega_1$ then, from only these considerations it should be possible to run any ITTM which eventually halts. So this is an argument for the metaphysical possibility of every halting run of an ITTM. Of course, to know what kind of supertask you’re going to have to run, you need to know how many steps the computation will take in advance. So its not really harnessable – it’s strictly a possibility result.