Supertask
Encyclopedia
In philosophy
Philosophy
Philosophy is the study of general and fundamental problems, such as those connected with existence, knowledge, values, reason, mind, and language. Philosophy is distinguished from other ways of addressing such problems by its critical, generally systematic approach and its reliance on rational...

, a supertask is a quantifiably infinite
Countable set
In mathematics, a countable set is a set with the same cardinality as some subset of the set of natural numbers. A set that is not countable is called uncountable. The term was originated by Georg Cantor...

 number of operations that occur sequentially within a finite interval of time. Supertasks are called "hypertasks" when the number of operations becomes innumerably infinite
Uncountable set
In mathematics, an uncountable set is an infinite set that contains too many elements to be countable. The uncountability of a set is closely related to its cardinal number: a set is uncountable if its cardinal number is larger than that of the set of all natural numbers.-Characterizations:There...

. The term supertask was coined by the philosopher James F. Thomson
James F. Thomson (philosopher)
James F. Thomson was a British philosopher who devised the puzzle of Thomson's lamp , to argue against the possibility of supertasks -Academic career:...

, who devised Thomson's lamp
Thomson's lamp
Thomson's lamp is a puzzle that is a variation on Zeno's paradoxes. It was devised by philosopher James F. Thomson, who also coined the term supertask....

, and the term hypertask derives from Clark and Read in their paper of that name.

Motion

The origin of the interest in supertasks is normally attributed to Zeno of Elea
Zeno of Elea
Zeno of Elea was a pre-Socratic Greek philosopher of southern Italy and a member of the Eleatic School founded by Parmenides. Aristotle called him the inventor of the dialectic. He is best known for his paradoxes, which Bertrand Russell has described as "immeasurably subtle and profound".- Life...

. Zeno claimed that motion was impossible
Zeno's paradoxes
Zeno's paradoxes are a set of problems generally thought to have been devised by Greek philosopher Zeno of Elea to support Parmenides's doctrine that "all is one" and that, contrary to the evidence of our senses, the belief in plurality and change is mistaken, and in particular that motion is...

. 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:
  1. Motion is a supertask, because the completion of motion over any set distance involves an infinite number of steps
  2. Supertasks are impossible
  3. Therefore motion is impossible


Most subsequent philosophers reject Zeno's bold conclusion in favor of common sense. Instead they turn his argument on its head (assuming it's valid) and take it as a proof by contradiction
Reductio ad absurdum
In logic, proof by contradiction is a form of proof that establishes the truth or validity of a proposition by showing that the proposition's being false would imply a contradiction...

 where the possibility of motion is taken for granted. They accept the possibility of motion and apply modus tollens
Modus tollens
In classical logic, modus tollens has the following argument form:- Formal notation :...

 (contrapositive) to Zeno's argument to reach the conclusion that either motion is not a supertask or supertasks are in fact possible.

Achilles and the tortoise

Zeno himself also discusses the notion of what he calls "Achilles
Achilles
In Greek mythology, Achilles was a Greek hero of the Trojan War, the central character and the greatest warrior of Homer's Iliad.Plato named Achilles the handsomest of the heroes assembled against Troy....

 and the tortoise". Suppose that Achilles is the fastest runner, and moves at a speed of 1 m/s. Achilles chases a tortoise, an animal renowned for being slow, that moves at 0.1 m/s. However, the tortoise starts 0.9 metres ahead. Common sense seems to decree that Achilles will catch up with the tortoise after exactly 1 second, but Zeno argues that this is not the case. He instead suggests that Achilles must inevitably come up to the point where the tortoise has started from, but by the time he has accomplished this, the tortoise will already have moved on to another point. This continues, and every time Achilles reaches the mark where the tortoise was, the tortoise will create a new point that Achilles will have to catch up with; while it begins with 0.9 metres, it becomes an additional 0.09 metres, then 0.009 metres, and so on, infinitely. While these distances will grow very small, they will remain finite, while Achilles' chasing of the tortoise will become an unending supertask. Much commentary has been made on this particular paradox; many assert that it finds a loophole in common sense.

Thomson

James F. Thomson
James F. Thomson (philosopher)
James F. Thomson was a British philosopher who devised the puzzle of Thomson's lamp , to argue against the possibility of supertasks -Academic career:...

 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
Thomson's lamp
Thomson's lamp is a puzzle that is a variation on Zeno's paradoxes. It was devised by philosopher James F. Thomson, who also coined the term supertask....

 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 (= 1/2 + 1/4) it is off, t = 7/8 (= 1/2 + 1/4 + 1/8) it is on, etc. The natural question arises: at t = 1 is the lamp on or off? There does not 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
Paul Benacerraf
Paul Joseph Salomon Benacerraf is an American philosopher working in the field of the philosophy of mathematics who has been teaching at Princeton University since he joined the faculty in 1960. He was appointed Stuart Professor of Philosophy in 1974, and recently retired as the James S....

 believes that supertasks are at least logically possible despite Thomson's 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. Logical implication does not bar the lamp from being on, off, or vanishing 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, rather like the way nothing can be found in Shakespeare's play to determine whether Hamlet
Hamlet
The Tragical History of Hamlet, Prince of Denmark, or more simply Hamlet, is a tragedy by William Shakespeare, believed to have been written between 1599 and 1601...

 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. It does not apply to 1 because 1 does not appear in the sequence {0, 1/2, 3/4, 7/8, …} whereas Thomson's experiment only specified the state of the lamp for times in this sequence.

Modern literature

Most of the modern literature comes from the descendants of Benacerraf, those who tacitly accept the possibility of supertasks. Philosophers who reject their possibility tend not to reject them on grounds such as Thomson's but because they have qualms with the notion of infinity itself (of course there are exceptions; for example, McLaughlin claims that Thomson's lamp is inconsistent if it is analyzed with internal set theory
Internal set theory
Internal set theory is a mathematical theory of sets developed by Edward Nelson that provides an axiomatic basis for a portion of the non-standard analysis introduced by Abraham Robinson. Instead of adding new elements to the real numbers, the axioms introduce a new term, "standard", which can be...

, a variant of real analysis
Real analysis
Real analysis, is a branch of mathematical analysis dealing with the set of real numbers and functions of a real variable. In particular, it deals with the analytic properties of real functions and sequences, including convergence and limits of sequences of real numbers, the calculus of the real...

).

Philosophy of mathematics

If supertasks are possible, then the truth or falsehood of unknown propositions of number theory, such as Goldbach's conjecture
Goldbach's conjecture
Goldbach's conjecture is one of the oldest unsolved problems in number theory and in all of mathematics. It states:A Goldbach number is a number that can be expressed as the sum of two odd primes...

, or even undecidable
Undecidable problem
In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is impossible to construct a single algorithm that always leads to a correct yes-or-no answer....

 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
Intuitionism
In the philosophy of mathematics, intuitionism, or neointuitionism , is an approach to mathematics as the constructive mental activity of humans. That is, mathematics does not consist of analytic activities wherein deep properties of existence are revealed and applied...

, since the intuitionist must distinguish between things that cannot be proven (because they are too long or complicated; see Boolos, "A Curious Inference") but nonetheless are considered "provable", and those that are provable by infinite brute force in the above sense.

Physical possibility

Some have claimed Thomson's lamp is physically impossible since it must have parts moving at speeds faster than the speed of light
Speed of light
The speed of light in vacuum, usually denoted by c, is a physical constant important in many areas of physics. Its value is 299,792,458 metres per second, a figure that is exact since the length of the metre is defined from this constant and the international standard for time...

 (e.g., the lamp switch). Adolf Grünbaum
Adolf Grünbaum
Adolf Grünbaum is a philosopher of science and a critic of psychoanalysis. He is also well-known as a critic of Karl Popper's philosophy of science....

 suggests that the lamp could have a strip of wire which, when lifted, disrupts the circuit and turns off the lamp; this strip could then be lifted by a smaller distance each time the lamp is to be turned off, maintaining a constant velocity. However, such a design would ultimately fail, as eventually the distance between the contacts would be so small as to allow electrons to jump the gap, preventing the circuit from being broken at all.

Other physically possible supertasks have been suggested. In one proposal, one person (or entity) counts upward from 1, taking an infinite amount of time, while another person observes this from a frame of reference where this occurs in a finite space of time. For the counter, this is not a supertask, but for the observer, it is. (This could theoretically occur due to time dilation
Time dilation
In the theory of relativity, time dilation is an observed difference of elapsed time between two events as measured by observers either moving relative to each other or differently situated from gravitational masses. An accurate clock at rest with respect to one observer may be measured to tick at...

, for example if the observer were falling into a black hole
Black hole
A black hole is a region of spacetime from which nothing, not even light, can escape. The theory of general relativity predicts that a sufficiently compact mass will deform spacetime to form a black hole. Around a black hole there is a mathematically defined surface called an event horizon that...

 while observing a counter whose position is fixed relative to the singularity.)

Davies in his paper "Building Infinite Machines" concocted a device which he claims is physically possible up to infinite divisibility. It involves a machine which creates an exact replica of itself but has half its size and twice its speed. Still, for either a human or any device, to perceive or act upon the state of the lamp some measurement has to be done, for example the light from the lamp would have to reach an eye or a sensor. Any such measurement will take a fixed frame of time, no matter how small and, therefore, at some point measurement of the state will be impossible. Since the state at t=1 can not be determined even in principle, it is not meaningful to speak of the lamp being either on or off.

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").

The diary of Tristram Shandy

Tristram Shandy, the hero of a novel by Laurence Sterne
Laurence Sterne
Laurence Sterne was an Irish novelist and an Anglican clergyman. He is best known for his novels The Life and Opinions of Tristram Shandy, Gentleman, and A Sentimental Journey Through France and Italy; but he also published many sermons, wrote memoirs, and was involved in local politics...

, writes his autobiography so conscientiously that it takes him one year to lay down the events of one day. If he is mortal he can never terminate; but if he lived forever then no part of his diary would remain unwritten, for to each day of his life a year devoted to that day's description would correspond.

Ross-Littlewood paradox

Suppose there is a jar capable of containing infinitely many marbles and an infinite collection of marbles labelled 1, 2, 3, and so on. At time t = 0, marbles 1 through 10 are placed in the jar and marble 1 is taken out. At t = 0.5, marbles 11 through 20 are placed in the jar and marble 2 is taken out; at t = 0.75, marbles 21 through 30 are put in the jar and marble 3 is taken out; and in general at time t = 1 − 0.5n, marbles 10n + 1 through 10n + 10 are placed in the jar and marble n + 1 is taken out. How many marbles are in the jar at time t = 1?

One argument states that there should be 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. A second argument, however, shows that the jar is empty. Consider the following argument: if the jar is non-empty, then there must be a marble in the jar. Let us say that that marble is labeled with the number n. But at time t = 1 − 0.5n - 1, the nth marble has been taken out, so marble n cannot be in the jar. This is a contradiction, so the jar must be empty. The Ross-Littlewood paradox is that here we have two seemingly perfectly good arguments with completely opposite conclusions.

Further complications are introduced by the following variant. Suppose that we follow the same process as above, but instead of taking out marble 1 at t = 0, one takes out marble 2. And, at t = 0.5 one takes out marble 3, at t = 0.75 marble 4, etc. Then, one can use the same logic from above to show that while at t = 1, marble 1 is still in the jar, no other marbles can be left in the jar. Similarly, one can construct scenarios where in the end, 2 marbles are left, or 17 or, of course, infinitely many. But again this is paradoxical: given that in all these variations the same number of marbles are added or taken out at each step of the way, how can the end result differ?

Some people decide to simply bite the bullet and say that apparently, the end result does depend on which marbles are taken out at each instant. However, one immediate problem with that view is that one can think of the thought experiment as one where none of the marbles are actually labeled, and thus all the above variations are simply different ways of describing the same process; it seems unreasonable to say that the end result of the one actual process depends on the way we describe what happens.

Moreover, Allis and Koetsier offer the following variation on this thought experiment: at t = 0, marbles 1 to 9 are placed in the jar, but instead of taking a marble out they scribble a 0 after the 1 on the label of the first marble so that it is now labeled "10". At t = 0.5, marbles 11 to 19 are placed in the jar, and instead of taking out marble 2, a 0 is written on it, marking it as 20. The process is repeated ad infinitum. Now, notice that the end result at each step along the way of this process is the same as in the original experiment, and indeed the paradox remains: Since at every step along the way, more marbles were added, there must be infinitely marbles left at the end, yet at the same time, since every marble with number n was taken out at t = 1 − 0.5n - 1, no marbles can be left at the end. However, in this experiment, no marbles are ever taken out, and so any talk about the end result 'depending' on which marbles are taken out along the way is made impossible.

A bare-naked variation that really goes straight to the heart of all of this goes as follows: at t = 0, there is one marble in the jar with the number 0 scribbled on it. At t = 0.5, the number 0 on the marble gets replaced with the number 1, at t = 0.75, the number gets changed to 2, etc. Now, no marbles are ever added to or removed from the jar, so at t = 1, there should still be exactly that one marble in the jar. However, since we always replaced the number on that marble with some other number, it should have some number n on it, and that is impossible because we know precisely when that number was replaced, and never repeated again later. In other words, we can also reason that no marble can be left at the end of this process, which is quite a paradox.

Of course, 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. Thus, neither Ross’s or Allis’s and Koetsier’s argument for the state of the jar at t = 1 proceeds by logical means only. Therefore, some extra premise must be introduced in order to say anything about the state of the jar at t = 1. Allis and Koetsier believe such an extra premise can be provided by the physical law that the marbles have continuous space-time paths, and therefore from the fact that for each n, marble n is out of the jar for t < 1, it must follow that it must still be outside the jar at t = 1 by continuity. Thus, the contradiction, and the paradox, remains.

One obvious solution to all these conundrums and paradoxes is to say that supertasks are impossible. If supertasks are impossible, then the very assumption that all of these scenarios had some kind of 'end result' to them is mistaken, preventing all of the further reasoning (leading to the contradictions) to go through.

Benardete’s paradox

There has been considerable interest in Benardete’s “Paradox of the Gods”:

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 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 that is a meters in length at positions B, AB / 2, AB / 4, AB / 8, 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, it will come to rest and the second particle will inherit its velocity of 1 m/s. This process will continue as an infinite amount of collisions, and after 1 second, all the collisions will have finished since all the particles were moving at 1 meter per second. However no particle will emerge 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 are time-reversal-invariant; that is, if we reverse the direction of time, all the laws will remain the same. If time is reversed in this supertask, we have a system of stationary point masses along A to AB / 2 that will, at random, spontaneously start colliding with each other, resulting in a particle moving away from B at a velocity of 1 m/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 that can, in the space of half an hour, create an exact replica of itself that is half its size and capable of twice its replication 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 that yields successively faster bandwidth and the machines are also capable of simple arithmetic, the supertask can be used to perform brute-force proofs of unknown conjectures.

External links

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK