A survey of infinite time Turing machines

  • J. D. Hamkins, “A Survey of Infinite Time Turing Machines,” in Machines, Computations, and Universality – 5th International Conference MCU 2007, Orleans, France, 2007, pp. 62-71.  
    @INPROCEEDINGS{Hamkins2007:ASurveyOfInfiniteTimeTuringMachines,
    AUTHOR = "Joel David Hamkins",
    TITLE = "A Survey of Infinite Time {T}uring Machines",
    BOOKTITLE = "Machines, Computations, and Universality - 5th International Conference MCU 2007",
    YEAR = "2007",
    editor = "{J\'er\^ ome} Durand-Lose and Maurice Margenstern",
    volume = "4664",
    number = "",
    series = "Lecture Notes in Computer Science",
    pages = "62--71",
    address = "Orleans, France",
    month = "",
    organization = "",
    publisher = "",
    note = "",
    abstract = "",
    keywords = "",
    doi = {10.1007/978-3-540-74593-8_5},
    ee = {http://dx.doi.org/10.1007/978-3-540-74593-8_5},
    crossref = {DBLP:conf/mcu/2007},
    file = F
    }

Infinite time Turing machines extend the operation of ordinary Turing machines into transfinite ordinal time, thereby providing a natural model of infinitary computability, with robust notions of computability and decidability on the reals, while remaining close to classical concepts of computability. Here, I survey the theory of infinite time Turing machines and recent developments. These include the rise of infinite time complexity theory, the introduction of infinite time computable model theory, the study of the infinite time analogue of Borel equivalence relation theory, and the introduction of new ordinal computational models. The study of infinite time Turing machines increasingly relies on the interaction of methods from set theory, descriptive set theory and computability theory.

Leave a Reply