Supertask computation

  • [DOI] J. D. Hamkins, “Supertask computation,” in Classical and New Paradigms of Computation and their Complexity Hierarchies, Dordrecht, 2004, p. 141–158, Papers of the conference “Foundations of the Formal Sciences III” held in Vienna, September 21-24, 2001.
    [Bibtex]
    @INPROCEEDINGS{Hamkins2004:SupertaskComputation,
    AUTHOR = {Hamkins, Joel David},
    TITLE = {Supertask computation},
    BOOKTITLE = {{Classical and New Paradigms of Computation and their Complexity Hierarchies}},
    SERIES = {Trends Log.~Stud.~Log.~Libr.},
    VOLUME = {23},
    PAGES = {141--158},
    PUBLISHER = {Kluwer Acad.~Publ.},
    ADDRESS = {Dordrecht},
    YEAR = {2004},
    MRCLASS = {03D10 (03D25 68Q05)},
    MRNUMBER = {2155535},
    DOI = {10.1007/978-1-4020-2776-5_8},
    URL = {http://jdh.hamkins.org/supertaskcomputation/},
    note = {Papers of the conference ``Foundations of the Formal Sciences III'' held in Vienna, September 21-24, 2001},
    eprint = {math/0212049},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    file = F,
    }

Infinite time Turing machines extend the classical Turing machine concept to transfinite ordinal time, thereby providing a natural model of infinitary computability that sheds light on the power and limitations of supertask algorithms.

Leave a Reply