Infinitary computability with infinite time Turing machines

  • J. D. Hamkins, “Infinitary computability with infinite time Turing machines,” in New Computational Paradigms, Amsterdam, 2005.  
    @INPROCEEDINGS{Hamkins2005:InfinitaryComputabilityWithITTM,
    AUTHOR = "Joel David Hamkins",
    TITLE = "Infinitary computability with infinite time {T}uring machines",
    BOOKTITLE = "New Computational Paradigms",
    YEAR = "2005",
    editor = "Cooper, Barry S.~and {L\"owe}, Benedikt",
    volume = "3526",
    number = "",
    series = "LNCS",
    pages = "",
    address = "Amsterdam",
    month = "June 8-12",
    organization = "CiE",
    publisher = "Springer-Verlag",
    isbn = "3-540-26179-6",
    note = "",
    abstract = "",
    keywords = "",
    doi = {10.1007/11494645_22},
    ee = {http://dx.doi.org/10.1007/11494645_22},
    crossref = {DBLP:conf/cie/2005},
    file = F
    }

Infinite time Turing machines extend the operation of ordinary Turing machines into transfinite ordinal time. By doing so, they provide a theoretical model of infinitary computability, while remaining close in spirit to many of the methods and concepts of classical computability. The model gives rise to a robust theory of infinitary computability on the reals, such as notions of computability for functions $f:\mathbb{R}\to\mathbb{R}$ and notions of decidability for sets $A\subset\mathbb{R}$, with a rich degree structure. In this brief article, I would like to announce and explain a few of the most recent developments in the theory of infinite time Turing machines. These developments include the rise of infinitary complexity theory, with a solution of the infinite time Turing machine analogue of the $P$ versus $NP$ question, and the development of infinitary computable model theory. Much of the work on infinite time Turing machines lies within the boundaries between set theory, descriptive set theory, computability theory and computable model theory.

Leave a Reply