Supertask computation

  • J. D. Hamkins, “Supertask computation,” in Classical and new paradigms of computation and their complexity hierarchies, Dordrecht, 2004, pp. 141-158. (Papers of the conference “Foundations of the Formal Sciences III” held in Vienna, September 21-24, 2001)  
    @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://dx.doi.org/10.1007/978-1-4020-2776-5_8},
    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