Student talks on infinitary computability

Students in my Infinitary Computability course will give talks on their term papers.  Talks will be held at the CUNY Graduate Center, Room 3307, 9:30-11:30.

Monday, December 3rd

  • Miha Habič will speak on “Cardinal-Recognizing Infinite Time Turing Machines”, in which he develops the theory of infinite time Turing machines that are given information about when they have reached cardinal time.
  • Erin Carmody will speak on “Non-deterministic infinite time Turing machines”, in which she develops the theory of non-deterministic ITTM computation.
  • Alexy Nikolaev will speak on “Equivalence of ITTMs, and their simultation on a finite time computer,” in which we proves the equivalence of various formalizations of ITTMs.

Monday, December 10th

  • Manuel Alves will speak on infinite time computable model theory.
  • Syed Ali Ahmed will speak on the relation between Büchi automata and infinite time Turing machines, including $\omega$-regular languages and generalizations to longer transfinite strings.

Ansten Mørch-Klev

Ansten Mørch-Klev earned his M.Sc. degree under my direction at Universiteit van Amsterdam in July, 2007.   For his thesis, Ansten undertook to investigate the infinite-time analogue of Kleene’s $\mathcal{O}$, the natural extension of Kleene’s concept to the case of infinite time Turing machines.  The result was a satisfying and robust theory, which revealed (as predicted by Philip Welch) the central importance of the eventually writable ordinals in the theory of infinite time computability.  This work eventually appeared as:  Ansten Mørch-Klev, “Infinite time analogues of Kleene’s $\mathcal{O}$,” Archive for Mathematical Logic, 48(7):2009, p. 691-703, DOI:10.1007/s00153-009-0146-2.

Ansten Mørch Klev

web page | DBLP | google scholar

Ansten Mørch-Klev, “Extending Kleene’s O Using Infinite Time Turing Machines, or How With Time She Grew Taller and Fatter”, M.Sc. thesis for Institute of Logic, Language and Computation, Universiteit van Amsterdam, July, 2007.  ILLC publication

Abstract.  We define two successive extensions of Kleene’s $\mathcal{O}$ using infinite time Turing machines. The first extension, $\mathcal{O}^+$, is proved to code a tree of height $\lambda$, the supremum of the writable ordinals, while the second extension, $\mathcal{O}^{++}$, is proved to code a tree of height $\zeta$, the supremum of the eventually writable ordinals. Furthermore, we show that $\mathcal{O}^+$ is computably isomorphic to $h$, the lightface halting problem of infinite time Turing machine computability, and that $\mathcal{O}^{++}$ is computably isomorphic to $s$, the set of programs that eventually writes a real. The last of these results implies, by work of Welch, that $\mathcal{O}^{++}$ is computably isomorphic to the $\Sigma_2$ theory of $L_\zeta$, and, by work of Burgess, that $\mathcal{O}^{++}$ is complete with respect to the class of the arithmetically quasi-inductive sets. This leads us to conjecture the existence of a parallel of hyperarithmetic theory at the level of $\Sigma_2(L_\zeta)$, a theory in which $\mathcal{O}^{++}$ plays the role of $\mathcal{O}$, the arithmetically quasi-inductive sets play the role of $\Pi^1_1$, and the eventually writable reals play the role of $\Delta^1_1$.

 

A course in infinitary computability, Fall 2012, CUNY Graduate Center, CSC 85020

In Fall 2012 I will teach a graduate course on infinitary computability theory in the Computer Science program at the CUNY Graduate Center.   This course will be aimed at graduate students in computer science and mathematics who are interested in infinitary computational processes.

Infinitary computability, CSC 85020, Mondays, 9:30 – 11:30 am
CS course listings | this listing

This course will explore all the various infinitary theories of computability, including infinite time Turing machines, Blum-Shub-Smale computability, Büchi automata, ordinal register machines and others. The focus will be on introducing the computability models and comparing them to each other and to standard concepts of computability. In the early part of the course, we shall review the standard finitary computational models, before investigating the infinitary supertask analogues.

Students wishing to prepare for the course should review their understanding of Turing machines and the other theoretical machine models of computation.

Some of my articles on infinitary computability | Student talks on their infinitary computability term papers

Effective Mathemematics of the Uncountable

EMU book jacket

  • Effective Mathematics of the Uncountable, N.~Greenberg, J.~D.~Hamkins, D.~R.~Hirschfeldt, and R.~G.~Miller, Eds., Cambridge University Press, ASL Lecture Notes in Logic, 2013, vol. 41.  
    @BOOK{EMU,
    AUTHOR = {},
    editor = {N.~Greenberg and J.~D.~Hamkins and D.~R.~Hirschfeldt and R.~G.~Miller},
    TITLE = {Effective Mathematics of the Uncountable},
    PUBLISHER = {Cambridge University Press, ASL Lecture Notes in Logic},
    YEAR = {2013},
    volume = {41},
    number = {},
    series = {},
    address = {},
    edition = {},
    month = {},
    note = {},
    abstract = {},
    isbn = {9781107014510},
    price = {},
    keywords = {},
    source = {},
    }

Classical computable model theory is most naturally concerned with countable domains. There are, however, several methods – some old, some new – that have extended its basic concepts to uncountable structures. Unlike in the classical case, however, no single dominant approach has emerged, and different methods reveal different aspects of the computable content of uncountable mathematics. This book contains introductions to eight major approaches to computable uncountable mathematics: descriptive set theory; infinite time Turing machines; Blum-Shub-Smale computability; Sigma-definability; computability theory on admissible ordinals; E-recursion theory; local computability; and uncountable reverse mathematics. This book provides an authoritative and multifaceted introduction to this exciting new area of research that is still in its early stages. It is ideal as both an introductory text for graduate and advanced undergraduate students, and a source of interesting new approaches for researchers in computability theory and related areas.

Many of the authors whose work appears in this volume were also involved in the Effective Mathematics of the Uncountable conferences EMU 2008 and EMU 2009, held at the CUNY Graduate Center.

Infinite time Turing machines and an application to the hierarchy of equivalence relations on the reals

  • S. Coskey and J. D. Hamkins, “Infinite time Turing machines and an application to the hierarchy of equivalence relations on the reals,” in Effective mathematics of the uncountable, Assoc. Symbol. Logic, La Jolla, CA, 2013, vol. 41, pp. 33-49.  
    @incollection {CoskeyHamkins2013:ITTMandApplicationsToEquivRelations,
    AUTHOR = {Coskey, Samuel and Hamkins, Joel David},
    TITLE = {Infinite time {T}uring machines and an application to the
    hierarchy of equivalence relations on the reals},
    BOOKTITLE = {Effective mathematics of the uncountable},
    SERIES = {Lect. Notes Log.},
    VOLUME = {41},
    PAGES = {33--49},
    PUBLISHER = {Assoc. Symbol. Logic, La Jolla, CA},
    YEAR = {2013},
    MRCLASS = {03D30 (03D60 03E15)},
    MRNUMBER = {3205053},
    eprint = {1101.1864},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    url = {http://arxiv.org/abs/1101.1864},
    }

We describe the basic theory of infinite time Turing machines and some recent developments, including the infinite time degree theory, infinite time complexity theory, and infinite time computable model theory. We focus particularly on the application of infinite time Turing machines to the analysis of the hierarchy of equivalence relations on the reals, in analogy with the theory arising from Borel reducibility. We define a notion of infinite time reducibility, which lifts much of the Borel theory into the class ${\Delta}^1_2$ in a satisfying way.

Infinite time decidable equivalence relation theory

  • S. Coskey and J. D. Hamkins, “Infinite time decidable equivalence relation theory,” Notre Dame J.~Form.~Log., vol. 52, iss. 2, pp. 203-228, 2011.  
    @ARTICLE{CoskeyHamkins2011:InfiniteTimeComputableEquivalenceRelations,
    AUTHOR = {Coskey, Samuel and Hamkins, Joel David},
    TITLE = {Infinite time decidable equivalence relation theory},
    JOURNAL = {Notre Dame J.~Form.~Log.},
    FJOURNAL = {Notre Dame Journal of Formal Logic},
    VOLUME = {52},
    YEAR = {2011},
    NUMBER = {2},
    PAGES = {203--228},
    ISSN = {0029-4527},
    MRCLASS = {03D65 (03D30 03E15)},
    MRNUMBER = {2794652},
    DOI = {10.1215/00294527-1306199},
    URL = {http://dx.doi.org/10.1215/00294527-1306199},
    eprint = "0910.4616",
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    }

We introduce an analog of the theory of Borel equivalence relations in which we study equivalence relations that are decidable by an infinite time Turing machine. The Borel reductions are replaced by the more general class of infinite time computable functions. Many basic aspects of the classical theory remain intact, with the added bonus that it becomes sensible to study some special equivalence relations whose complexity is beyond Borel or even analytic. We also introduce an infinite time generalization of the countable Borel equivalence relations, a key subclass of the Borel equivalence relations, and again show that several key properties carry over to the larger class. Lastly, we collect together several results from the literature regarding Borel reducibility which apply also to absolutely $\Delta^1_2$ reductions, and hence to the infinite time computable reductions.

Post's problem for ordinal register machines: an explicit approach

  • J. D. Hamkins and R. G. Miller, “Post’s problem for ordinal register machines: an explicit approach,” Ann.~Pure Appl.~Logic, vol. 160, iss. 3, pp. 302-309, 2009.  
    @ARTICLE{HamkinsMiller2009:PostsProblemForORMsExplicitApproach,
    AUTHOR = {Hamkins, Joel David and Miller, Russell G.},
    TITLE = {Post's problem for ordinal register machines: an explicit approach},
    JOURNAL = {Ann.~Pure Appl.~Logic},
    FJOURNAL = {Annals of Pure and Applied Logic},
    VOLUME = {160},
    YEAR = {2009},
    NUMBER = {3},
    PAGES = {302--309},
    ISSN = {0168-0072},
    CODEN = {APALD7},
    MRCLASS = {03D60 (03D10)},
    MRNUMBER = {2555781 (2010m:03086)},
    MRREVIEWER = {Robert S.~Lubarsky},
    DOI = {10.1016/j.apal.2009.01.004},
    URL = {http://dx.doi.org/10.1016/j.apal.2009.01.004},
    file = F
    }

We provide a positive solution for Post’s Problem for ordinal register machines, and also prove that these machines and ordinal Turing machines compute precisely the same partial functions on ordinals. To do so, we construct ordinal register machine programs which compute the necessary functions. In addition, we show that any set of ordinals solving Post’s Problem must be unbounded in the writable ordinals.

Infinite time computable model theory

  • J. D. Hamkins, R. Miller, D. Seabold, and S. Warner, “Infinite time computable model theory,” in New Computational Paradigms: Changing Conceptions of What is Computable, S. B. \. Cooper, B. Löwe, and A. Sorbi, Eds., New York: Springer, 2008, pp. 521-557.  
    @INCOLLECTION{HamkinsMillerSeaboldWarner2007:InfiniteTimeComputableModelTheory,
    AUTHOR = {Hamkins, Joel David and Miller, Russell and Seabold, Daniel
    and Warner, Steve},
    TITLE = {Infinite time computable model theory},
    BOOKTITLE = "New Computational Paradigms: Changing Conceptions of What is Computable",
    PAGES = {521--557},
    PUBLISHER = {Springer},
    ADDRESS = {New York},
    YEAR = {2008},
    MRCLASS = {03C57 (03D10)},
    MRNUMBER = {2762096},
    editor = {S.B.\ Cooper and Benedikt L\"owe and Andrea Sorbi},
    isbn = "0-387-36033-6",
    file = F
    }

We introduce infinite time computable model theory, the computable model theory arising with infinite time Turing machines,  which provide infinitary notions of computability for structures built on the reals  $\mathbb{R}$. Much of the finite time theory generalizes to the infinite time context, but several fundamental questions, including the infinite time  computable analogue of the Completeness Theorem, turn out to be  independent of ZFC.

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.

${\rm P}\neq{\rm NP}\cap\textrm{co-}{\rm NP}$ for infinite time Turing machines

  • V. Deolalikar, J. D. Hamkins, and R. Schindler, “${\rm P}\neq{\rm NP}\cap$ co-NP for infinite time Turing machines,” J.~Logic Comput., vol. 15, iss. 5, pp. 577-592, 2005.  
    @ARTICLE{DeolalikarHamkinsSchindler2005:NPcoNP,
    AUTHOR = {Deolalikar, Vinay and Hamkins, Joel David and Schindler, Ralf},
    TITLE = {{${\rm P}\neq{\rm NP}\cap$} co-{NP} for infinite time {T}uring machines},
    JOURNAL = {J.~Logic Comput.},
    FJOURNAL = {Journal of Logic and Computation},
    VOLUME = {15},
    YEAR = {2005},
    NUMBER = {5},
    PAGES = {577--592},
    ISSN = {0955-792X},
    MRCLASS = {68Q05 (03D05 68Q15)},
    MRNUMBER = {2172411 (2006k:68026)},
    MRREVIEWER = {Peter G.~Hinman},
    DOI = {10.1093/logcom/exi022},
    URL = {http://dx.doi.org/10.1093/logcom/exi022},
    month = "October",
    eprint = {math/0307388},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    file = F,
    }

Extending results of Schindler [math.LO/0106087] and also my paper with Philip Welch, we establish in the context of infinite time Turing machines that $P$ is properly contained in $NP$ intersect $coNP$. Furthermore, $NP\cap coNP$ is exactly the class of hyperarithmetic sets. For the more general classes, we establish that $P^+ = (NP^+\cap coNP^+) = (NP \cap  coNP)$, though $P^{++}$ is properly contained in $NP^{++}\cap coNP^{++}$. Within any contiguous block of infinite clockable ordinals, we show that $P_\alpha$ is not equal to $NP_\alpha\cap coNP_\alpha$, but if $\beta$ begins a gap in the clockable ordinals, then $P_\beta = NP_\beta\cap coNP_\beta$. Finally, we establish that $P^f$ is not equal to $NP^f \cap  coNP^f$ for most functions $f$ from the reals to the ordinals, although we provide examples where $P^f = NP^f \cap coNP^f$ and $P^f$ is not equal to $NP^f$.

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.

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.

${\rm P}^f\neq {\rm NP}^f$ for almost all $f$

  • J. D. Hamkins and P. D. Welch, “${\rm P}^f\neq {\rm NP}^f$ for almost all $f$,” MLQ Math.~Log.~Q., vol. 49, iss. 5, pp. 536-540, 2003.  
    @ARTICLE{HamkinsWelch2003:PfneqNPf,
    AUTHOR = {Hamkins, Joel David and Welch, Philip D.},
    TITLE = {{${\rm P}^f\neq {\rm NP}^f$} for almost all {$f$}},
    JOURNAL = {MLQ Math.~Log.~Q.},
    FJOURNAL = {MLQ.~Mathematical Logic Quarterly},
    VOLUME = {49},
    YEAR = {2003},
    NUMBER = {5},
    PAGES = {536--540},
    ISSN = {0942-5616},
    MRCLASS = {03D65 (03D10 03E45 68Q05 68Q15)},
    MRNUMBER = {1998405 (2004m:03163)},
    MRREVIEWER = {Peter G.~Hinman},
    DOI = {10.1002/malq.200310057},
    URL = {http://dx.doi.org/10.1002/malq.200310057},
    eprint = {math/0212046},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    }

Abstract. We discuss the question of Ralf-Dieter Schindler whether for infinite time Turing machines $P^f = NP^f$ can be true for any function $f$ from the reals into $\omega_1$. We show that “almost everywhere” the answer is negative.

Post's problem for supertasks has both positive and negative solutions

  • J. D. Hamkins and A. Lewis, “Post’s problem for supertasks has both positive and negative solutions,” Arch.~Math.~Logic, vol. 41, iss. 6, pp. 507-523, 2002.  
    @article{HamkinsLewis2002:PostProblem,
    AUTHOR = {Hamkins, Joel David and Lewis, Andrew},
    TITLE = {Post's problem for supertasks has both positive and negative solutions},
    JOURNAL = {Arch.~Math.~Logic},
    FJOURNAL = {Archive for Mathematical Logic},
    VOLUME = {41},
    YEAR = {2002},
    NUMBER = {6},
    PAGES = {507--523},
    ISSN = {0933-5846},
    CODEN = {AMLOEH},
    MRCLASS = {03D10 (68Q05)},
    MRNUMBER = {1923194 (2003f:03052)},
    MRREVIEWER = {Robert M.~Baer},
    DOI = {10.1007/s001530100112},
    URL = {http://dx.doi.org/10.1007/s001530100112},
    eprint = {math/9808128},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    }

Recently we have introduced a new model of infinite computation by extending the operation of ordinary Turing machines into transfinite ordinal time. In this paper we will show that the infinite time Turing machine analogue of Post’s problem, the question whether there are supertask degrees between $0$ and the supertask jump $0^\triangledown$, has in a sense both positive and negative solutions. Namely, in the context of the reals there are no degrees between $0$ and $0^\triangledown$, but in the context of sets of reals, there are; indeed, there are incomparable semi-decidable supertask degrees. Both arguments employ a kind of transfinite-injury construction which generalizes canonically to oracles.

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)  
    @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},
    }

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.