Computability in Europe, Heidelberg, July 2009

Abstract: The infinite-time Turing machine is a generalization of the classical Turing machine introduced by Hamkins. It has essentially the same apparatus as a Turing machine, but it is allowed to continue computation even after infinitely many steps. At limit ordinal stages, it enters a special limit state, the read/write head resets to the left of its tape, and the value of each cell passes to the lim-sup of the values that it formerly held. The sets recognized by such a machine lie properly within the class $\mathbf{\Delta}^1_2$. In this talk, I will outline a few recent developments in the descriptive set-theoretic aspects of inifinite-time Turing machine theory. I will also discuss some connections with the theory of Borel equivalence relations. This talk will include work of Joel Hamkins, Philip Welch and others.