- J. D. Hamkins, “Infinite time Turing machines,” Minds and Machines, vol. 12, iss. 4, p. 521–539, 2002.
[Bibtex]@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}, url = {http://wp.me/p5M0LV-2e}, }
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.