Infinite time computable model theory

  • J. D. Hamkins, R. Miller, D. Seabold, and S. Warner, “Infinite time computable model theory,” in New Computational Paradigms: Changing Conceptions of What is Computable, S. B. \. Cooper, B. Löwe, and A. Sorbi, Eds., New York: Springer, 2008, pp. 521-557.  
    @INCOLLECTION{HamkinsMillerSeaboldWarner2007:InfiniteTimeComputableModelTheory,
    AUTHOR = {Hamkins, Joel David and Miller, Russell and Seabold, Daniel
    and Warner, Steve},
    TITLE = {Infinite time computable model theory},
    BOOKTITLE = "New Computational Paradigms: Changing Conceptions of What is Computable",
    PAGES = {521--557},
    PUBLISHER = {Springer},
    ADDRESS = {New York},
    YEAR = {2008},
    MRCLASS = {03C57 (03D10)},
    MRNUMBER = {2762096},
    editor = {S.B.\ Cooper and Benedikt L\"owe and Andrea Sorbi},
    isbn = "0-387-36033-6",
    file = F
    }

We introduce infinite time computable model theory, the computable model theory arising with infinite time Turing machines,  which provide infinitary notions of computability for structures built on the reals  $\mathbb{R}$. Much of the finite time theory generalizes to the infinite time context, but several fundamental questions, including the infinite time  computable analogue of the Completeness Theorem, turn out to be  independent of ZFC.

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.