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