- J. D. Hamkins and D. E. Seabold, “Infinite Time Turing Machines With Only One Tape,” Math.~Logic Q., vol. 47, iss. 2, p. 271–287, 2001.
[Bibtex]@article{HamkinsSeabold2001:OneTape, author = {Hamkins, Joel David and Seabold, Daniel Evan}, title = {Infinite Time {Turing} Machines With Only One Tape}, journal = {Math.~Logic Q.}, volume = {47}, number = {2}, publisher = {WILEY-VCH Verlag Berlin GmbH}, issn = {1521-3870}, MRNUMBER = {1829946 (2002f:03074)}, url = {http://jdh.hamkins.org/onetape/}, doi = {10.1002/1521-3870(200105)47:2<271::AID-MALQ271>3.0.CO;2-6}, pages = {271--287}, keywords = {One-tape infinite Turing machine, Supertask computation}, year = {2001}, eprint = {math/9907044}, archivePrefix = {arXiv}, primaryClass = {math.LO}, }
Infinite time Turing machines with only one tape are in many respects fully as powerful as their multi-tape cousins. In particular, the two models of machine give rise to the same class of decidable sets, the same degree structure and, at least for functions $f:\mathbb{R}\to\mathbb{N}$, the same class of computable functions. Nevertheless, there are infinite time computable functions $f:\mathbb{R}\to\mathbb{R}$ that are not one-tape computable, and so the two models of supertask computation are not equivalent. Surprisingly, the class of one-tape computable functions is not closed under composition; but closing it under composition yields the full class of all infinite time computable functions. Finally, every ordinal which is clockable by an infinite time Turing machine is clockable by a one-tape machine, except certain isolated ordinals that end gaps in the clockable ordinals.