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)  
    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.


Leave a Reply