Abstract:

Accelerating Turing machines are devices with the same computational structure as Turing machines (TM), but able to perform super-tasks. We ask whether performing super-tasks alone produces more computational power; for example, whether accelerating TM can solve the halting problem. We conclude that this is not the case. No accelerating TM solves the halting problem. The argument rests on an analysis of the reasoning that leads to Thomson's paradox. The key point is that the paradox rests on a conflation of different perspectives of accelerating processes. This leads to concluding that the same conflation underlies the claim that accelerating TM can solve the halting problem.

Notes:

Funding Information: I am thankful to Mark Burgin, Jack Copeland, Yuval Dolev, Itamar Pitowsky, Carl Posy and Michael Roubach for discussion and comments. This research was supported by The Israel Science Foundation (Grant No. 857/03–07).