Supertask

From Example Problems
Jump to navigation Jump to search
In computer science, supertask has a different meaning, unrelated to its meaning in mathematics and philosophy [1].

In philosophy a supertask is a task occurring within a finite interval of time involving infinitely many steps (subtasks); it is closely related to the mathematical idea of limits. A hypertask is a special type of supertask the number of whose subtasks is uncountable. The term supertask was coined by philosopher James F. Thomson (and the term hypertask by Clarke and Read in their identically named paper).

History

Zeno

The origin of the interest in supertasks is normally attributed to Zeno of Elea. Zeno claimed that motion was impossible. He argued as follows: suppose our burgeoning "mover", Achilles say, wishes to move from A to B. To achieve this he must traverse half the distance from A to B. To get from the midpoint of AB to B Achilles must traverse half this distance, and so on and so forth. However many times he performs one of these "traversing" tasks there is another one left for him to do before he arrives at B. Thus it follows, according to Zeno, that motion (travelling a non-zero distance in finite time) is a supertask. Zeno further argues that supertasks are not possible (how can this sequence be completed if for each traversing there is another one to come?). It follows that motion is impossible.

Zeno's argument takes the following form:

  • Motion is a supertask
  • Supertasks are impossible
  • Therefore motion is impossible

Most subsequent philosophers reject Zeno's bold conclusion in favour of common sense. Instead they turn his argument on its head (assuming its valid) and take it as a proof by contradiction where the possibility of motion is taken for granted. They accept the possibility of motion and apply modus tollens (contrapositive) to Zeno's argument to reach the conclusion that either motion is not a supertask or supertasks are in fact possible.

Thomson

James F. Thomson was of the former category. He believed that motion was not a supertask, and he emphatically denied that supertasks are possible. The proof Thomson offered to the latter claim involves what has probably become the most famous example of a supertask since Zeno. Thomson's lamp may either be on or off. At time t=0 the lamp is off, at time t=1/2 it is on, at time t=3/4 it is off, t=7/8 on etc etc... The natural question arises: at t=1 is the lamp on or off? There doesn't seem to be any non-arbitrary way to decide this question. Thomson goes further and claims this is a contradiction. He says that the lamp cannot be on for there was never a point when it was on where it was not immediately switched off again. And similarly he claims it cannot be off for there was never a point when it was off where it was not immediately switched on again. By Thomson's reasoning the lamp is neither on nor off, yet by stipulation it must be either on or off - this is a contradiction. Thomson thus believes that supertasks are impossible.

Benacerraf

Paul Benacerraf is of the latter category. Benacerraf believes that supertasks are at least logically possible despite Thomsons apparent contradiction. Benacerraf agrees with Thomson insofar as that the experiment he outlined does not determine the state of the lamp at t=1. However he disagrees with Thomson that he can derive a contradiction from this, since the state of the lamp at t=1 need not be logically determined by the preceding states. For all logical implication has to say about this the lamp could be on, off or vanish completely to be replaced by a horse-drawn pumpkin. There are possible worlds in which Thomson's lamp finishes on, and worlds in which it finishes off not to mention countless others where weird and wonderful things happen at t=1. The seeming arbitrariness arises from the fact that Thomson's experiment does not contain enough information to determine the state of the lamp at t=1, a bit like the way nothing can be found in Shakespeares play to determine whether Hamlet was right or left handed. So what about the contradiction? Benacerraf showed that Thomson had committed a mistake. When he claimed that the lamp could not be on because it was never on without being turned off again - this applied only to instants of time strictly less than 1. Why does it not apply to 1? Because 1 does not appear in the sequence 0, 1/2, 3/4, 7/8... whereas Thomsons experiment only specified the state of the lamp for times in this sequence.

Modern Literature

Most of the modern literature comes from the descendents of Benacerraf - those who accept the possibility of supertasks. Philosophers who reject their possibility tend not reject them on grounds such as Thomson's but because they have qualms with the notion of infinity itself (of course there are exceptions, e.g. McLaughlin claims that Thomson's lamp is inconsistent if you analyse it with internal set theory - a variant of real analysis).

Philosophy of Mathematics

If supertasks are logically possible, then the truth or falsehood of unknown propositions of number theory, such as Goldbach's conjecture, or even undecidable propositions could be determined in a finite amount of time by a brute force search of the set of all natural numbers. This would, however, be in contradiction with the Church-Turing thesis. Some have argued this poses a problem for intuitionism, since the intuitionist must delineate between things which are not humanly possible to prove (because they are too long or complicated - see Boolos "A Curious Inference") but nonetheless are considered "provable" and those which are provable by infinite brute force in the above sense.

Spontaneous Self-Excitement

Some ingeniously devised supertasks can involve spontaneous self excitement. Earman and Norton, Alper and Briger, and Laraudogoitia have explored these examples in depth.

Physical Possibility

Davies in his paper "Building Infinite Machines" concocted an ingenious device which he claims is physically possible up to infinite divisibility. It involves a machine which creates an exact replica of itself but half its size and twice its speed.

Super Turing Machines

The impact of supertasks on theoretical computer science has triggered some new and interesting work (see Hamkins and Lewis - "Infinite Time Turing Machine")

Some Interesting Supertasks

Thomson's Lamp

Thomson's lamp can be either on or off. Begin with it on at time t = 0. At time t = 1/2, switch it off; at time t = 1/2 + 1/4, switch it on again; and so on. Is the lamp on or off at time t = 1?

Hilbert's paradox of the Grand Hotel

In this puzzle there is a hotel with infinitely many rooms (countably infinite) all of which are occupied. It's holiday season and another infinite number of people want to stay in the already full hotel. What does the manager do? The answer involves a supertask, the manager asks each guest to take note of their current room number and move their stuff to the room whose number is twice that of his or her own. After everyone has done this only the even numbered rooms will be occupied and the odd numbered rooms will be empty. Since there are infinitely many odd numbers this should be sufficient to house everybody. See Hilbert's paradox of the Grand Hotel.

Ross-Littlewood Paradox

Suppose you had a jar capable of containing infinitely many marbles, and an infinite collection of marbles labelled 1, 2, 3, and so on. At t=0, marbles 1 to 10 are placed in the jar, at t=1/2 11 to 20 are placed in the jar but marble 1 is taken out. At t=3/4 marbles 21 to 30 are put in the jar and marble 2 is taken out: in general at time t=1-(1/2)^n, the marbles (10*n + 1) to (10*n + 10) are placed in the jar and marble n is taken out. The question is: How many marbles are in the jar at t=1?

  • On first glance it appears as if there are infinitely many marbles in the jar because at each step before t=1 the number of marbles increases from the previous step and does so unboundedly.
  • However Ross argues that it's empty. Consider the following argument: if the jar is non-empty then there must be ball in the jar, lets say that ball was labelled with the number n. But at t=1-(1/2)^n the nth ball was taken out so the ball cannot be in the jar. This is a contradiction so counter to intuition the jar must be empty.
  • Allis and Koetsier offer the following similar experiment: at t=0, balls 1 to 9 are placed in the jar, but instead of taking a ball out they scribble on a “0” after the “1” on the label of the first ball so it becomes “10”. At t=1/2 balls 11 to 19 are placed in the jar and instead of taking out ball 2 a “0” is added to the 2 ball making it 20, so the jar contains balls labelled 3 to 20 like in the first experiment. And so on. At each step of this experiment the contents of this jar is exactly the same as the first jar. But in this experiment no balls have been taken out, yet infinitely many have been put in. In fact at t=1 there are infinitely many balls each labelled with a natural number followed by an infinite amount of 0’s.

Ross’ paradox was originally labelled a paradox because it was so unintuitive – however Allis and Koetsier’s experiment lends new weight to its paradoxical nature since in their experiment the two jars are exactly the same for each instant of time before t=1 yet at t=1 the first jar should be empty and the second one should have infinitely many balls. Here it would be wise to heed Benacerraf’s words that the states of the jars before t=1 do not logically determine the state at t=1, and thus neither Ross’s or Allis and Koetsier’s arguments for the state of the jar at t=1 proceed by logical means only. They must be sneaking in some extra premise unnoticed. A&K believe the extra premise is the physical law that the marbles have continuous space-time paths and therefore Ross’ argument is valid because we can determine from the fact that for each n, marble n is out of the jar for t<1 that it must still be outside the jar at t=1 by continuity. The difference between the two experiments is thus that one involves the motion of the marbles.

Benardete’s Paradox

This is not so much a supertask although papers about supertasks based on this idea have been written. A man called Prometheus angers Zeus so Zeus gathers an infinite number of demons and issues them with the following commands. Demon 1: if Prometheus is not dead in 1 hour kill him, Demon 2: if Prometheus is not dead in 1/2 an hour kill him, Demon 3: if Prometheus is not dead in 1/4 of an hour kill him, and so on. As it turns out Prometheus was dead within the hour (he didn’t really have much chance did he?). The council of gods was not happy about this and pressed Zeus on the point. But none of his demons could be found guilty, for each n the nth demon couldn’t have killed Prometheus because the (n+1)th demon should already have killed him. Similar paradoxes involving a man trying to walk a mile from A to B but the demon’s building a wall in front of him if he reaches 1/2, 1/4, 1/8… of a mile past A, so he hits a kind of invisible barrier when he reaches A, yet no wall has been built.

Laraudogoitia’s Beautiful Supertask

This supertask is an example of indeterminism in Newtonian mechanics. The supertask consists of an infinite collection of point masses all of which are stationary and which will spontaneously self excite (start moving for no apparent reason). The point masses are all of mass m, and are placed along a line AB a meters length, at B, 1/2AB, 1/4 AB, 1/8 AB, and so on. The first particle at B is accelerated to a velocity of one meter per second towards A. According to the laws of Newtonian mechanics, when the first particle collides with the second particle it will come to rest and the second particle will now inherit its velocity of 1m/s. This will continue with an infinite amount of collisions and after 1 second all the collisions will have finished since they were all moving at 1 meter per second. However no particle will emerge out of the other side, i.e. moving away from A, since there is no last particle in the sequence. It follows that all the particles are now at rest (contradicting conservation of energy). Now the laws of Newtonian mechanics is time reversal invariant, that is, if we reverse the direction of time all the laws will remain the same. If time is reversed with this super task we have a system of stationary point masses along A to 1/2AB which will at random, spontaneously start colliding with each other resulting in a particle moving away from B at a velocity of 1m/s. Alper and Bridger have questioned the reasoning in this supertask invoking the distinction between actual and potential infinity.

Davies' Super-Machine

This is a machine which can, in the space of half an hour, create an exact replica of itself which is half its size and twice its speed. This replica will in turn create an even faster version of itself with the same specifications resulting in a supertask that finishes after an hour. If additionally the machines create a communication link between parent and child machine which get successively faster bandwidth and the machines can do simple arithmetic, the supertask can used to perform brute force proofs of unknown conjectures. For example for Goldbach's Conjecture the first machine will spend the first half hour checking if 4 can be expressed as the sum of two primes (an inefficient use of the whole hour, but nontheless), the next quarter of an hour 6, and so on. This can even be extended to undecidable number theoretical problems, which some claim can lead to problems for intuitionism in the philosophy of mathematics.

External links

References

  • Thomson, J., 1954-55, ‘Tasks and Super-Tasks’, Analysis, XV, pp. 1-13.

sl:supernaloga