Infinite time Turing machines with only one tape

  • J. D. Hamkins and D. E. Seabold, “Infinite time Turing machines with only one tape,” MLQ Math. Log. Q., vol. 47, iss. 2, pp. 271-287, 2001.  
    @article{HamkinsSeabold2001:OneTape,
    AUTHOR = {Hamkins, Joel David and Seabold, Daniel Evan},
    TITLE = {Infinite time {T}uring machines with only one tape},
    JOURNAL = {MLQ Math. Log. Q.},
    FJOURNAL = {MLQ. Mathematical Logic Quarterly},
    VOLUME = {47},
    YEAR = {2001},
    NUMBER = {2},
    PAGES = {271--287},
    ISSN = {0942-5616},
    MRCLASS = {03D10 (68Q05)},
    MRNUMBER = {1829946 (2002f:03074)},
    MRREVIEWER = {Robert M. Baer},
    DOI = {10.1002/1521-3870(200105)47:2<271::AID-MALQ271>3.0.CO;2-6},
    URL = {http://dx.doi.org/10.1002/1521-3870(200105)47:2<271::AID-MALQ271>3.0.CO;2-6},
    eprint = {math/9907044}
    }

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.

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>