Post's problem for supertasks has both positive and negative solutions

  • J. D. Hamkins and A. Lewis, “Post’s problem for supertasks has both positive and negative solutions,” Arch.~Math.~Logic, vol. 41, iss. 6, pp. 507-523, 2002.  
    @article{HamkinsLewis2002:PostProblem,
    AUTHOR = {Hamkins, Joel David and Lewis, Andrew},
    TITLE = {Post's problem for supertasks has both positive and negative solutions},
    JOURNAL = {Arch.~Math.~Logic},
    FJOURNAL = {Archive for Mathematical Logic},
    VOLUME = {41},
    YEAR = {2002},
    NUMBER = {6},
    PAGES = {507--523},
    ISSN = {0933-5846},
    CODEN = {AMLOEH},
    MRCLASS = {03D10 (68Q05)},
    MRNUMBER = {1923194 (2003f:03052)},
    MRREVIEWER = {Robert M.~Baer},
    DOI = {10.1007/s001530100112},
    URL = {http://dx.doi.org/10.1007/s001530100112},
    eprint = {math/9808128},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    }

Recently we have introduced a new model of infinite computation by extending the operation of ordinary Turing machines into transfinite ordinal time. In this paper we will show that the infinite time Turing machine analogue of Post’s problem, the question whether there are supertask degrees between $0$ and the supertask jump $0^\triangledown$, has in a sense both positive and negative solutions. Namely, in the context of the reals there are no degrees between $0$ and $0^\triangledown$, but in the context of sets of reals, there are; indeed, there are incomparable semi-decidable supertask degrees. Both arguments employ a kind of transfinite-injury construction which generalizes canonically to oracles.

Infinite time Turing machines

  • J. D. Hamkins, “Infinite time Turing machines,” Minds and Machines, vol. 12, iss. 4, pp. 521-539, 2002. (special issue devoted to hypercomputation)  
    @ARTICLE{Hamkins2002:Turing,
    author = {Joel David Hamkins},
    title = {Infinite time {T}uring machines},
    journal = {Minds and Machines},
    year = {2002},
    volume = {12},
    number = {4},
    pages = {521--539},
    month = {},
    note = {special issue devoted to hypercomputation},
    key = {},
    annote = {},
    eprint = {math/0212047},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    }

This is a survey of the theory of infinite time Turing machines.

Infinite time Turing machines extend the operation of ordinary Turing machines into transfinite ordinal time. By doing so, they provide a natural model of infinitary computability, a theoretical setting for the analysis of the power and limitations of supertask algorithms.

 

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.