# Infinite time Turing machines with only one tape

• J. D. Hamkins and D. E. Seabold, “Infinite Time Turing Machines With Only One Tape,” Mathematical Logic Quarterly, vol. 47, iss. 2, pp. 271-287, 2001.
@article{HamkinsSeabold2001:OneTape,
author = {Hamkins, Joel David and Seabold, Daniel Evan},
title = {Infinite Time Turing Machines With Only One Tape},
journal = {Mathematical Logic Quarterly},
volume = {47},
number = {2},
publisher = {WILEY-VCH Verlag Berlin GmbH},
issn = {1521-3870},
MRNUMBER = {1829946 (2002f:03074)},
url = {http://dx.doi.org/10.1002/1521-3870(200105)47:2<271::AID-MALQ271>3.0.CO;2-6},
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.

# Infinite time Turing machines

• J. D. Hamkins and A. Lewis, “Infinite time Turing machines,” J.~Symbolic Logic, vol. 65, iss. 2, pp. 567-604, 2000.
@article {HamkinsLewis2000:InfiniteTimeTM,
AUTHOR = {Hamkins, Joel David and Lewis, Andy},
TITLE = {Infinite time {T}uring machines},
JOURNAL = {J.~Symbolic Logic},
FJOURNAL = {The Journal of Symbolic Logic},
VOLUME = {65},
YEAR = {2000},
NUMBER = {2},
PAGES = {567--604},
ISSN = {0022-4812},
CODEN = {JSYLA6},
MRCLASS = {03D10 (03D25 68Q05)},
MRNUMBER = {1771072 (2001g:03072)},
MRREVIEWER = {Robert M.~Baer},
DOI = {10.2307/2586556},
URL = {http://dx.doi.org/10.2307/2586556},
eprint = {math/9808093},
archivePrefix = {arXiv},
primaryClass = {math.LO},
}

This is the seminal paper introducing infinite time Turing machines.

We extend in a natural way the operation of Turing machines to infinite ordinal time, and investigate the resulting supertask theory of computability and decidability on the reals. The resulting computability theory leads to a notion of computation on the reals and concepts of decidability and semi-decidability for sets of reals as well as individual reals. Every $\Pi^1_1$ set, for example, is decidable by such machines, and the semi-decidable sets form a portion of the $\Delta^1_2$ sets. Our oracle concept leads to a notion of relative computability for reals and sets of reals and a rich degree structure, stratified by two natural jump operators.