Abstract:

It is generally assumed that supertasks increase computational power. It is argued, for example, that supertask machines can compute beyond the Turing limit, e.g., compute the halting function. We challenge this assumption. We do not deny that supertask machines can compute beyond the Turing limit. Our claim, rather, is that the (hyper) computational power of these machines is not related to supertasks, but to the "right kind" of computational structure.

Notes:

Funding Information: Acknowledgments Thanks to the participants of the Workshop on Physics and Computation at Ponta Delgada (2009) and to three anonymous referees for corrections and suggestions. This research was supported by the Israel Science Foundation, grant 725/08.