An accelerating Turing machine is a Turing machine (TM) that is capable of carrying out a “super-task,” that is, an infinite number of steps in a finite amount of time, for instance by using one minute for the first step, one half-minute for the second, and so on. It seems that such a device should be capable of solving problems that are beyond ordinary Turing machines, like the halting problem. This paper discusses certain paradoxes in this context and certain considerations that have been brought forth as arguments against the conceptual possibility of performing super-tasks (Thomson’s paradox).

Shagrir argues that such paradoxes cause disturbance only because accelerating TMs (in the mathematical sense) are confused with corresponding physical devices. In the mathematical sense, there is nothing like a state after the execution of all (infinitely many) steps. By contrast, it is assumed that such a state exists for a physical implementation, and that it satisfies certain persistency properties: if the contents of some tape cell are never changed after some step, then the contents should still be the same after the super-task is finished.

The final conclusion is that accelerating TMs do not have greater computational power than ordinary Turing machines, in contrast to the so-called infinite time Turing machines, for which computations of transfinite length are defined. From a mathematical point of view, this conclusion is obvious, since it does not matter whether the sequence of configurations in a nonterminating computation is associated with times 0, 1, 2, 3 ... or with times 0, 1, 3/2, 7/4 ....

The paper does not contain any mathematical results, but it discusses various arguments made, and clarifies some misconceptions.