Infinite time computations and ranks in descriptive set theory

What happens when you let a Turing machine run for infinite time? This question has been studied for a very natural machine model, the infinite time Turing machines of Hamkins and Kidder. Of course these machines become more powerful as the length of computations increases. A series of works explains their precise power, in particular where they fit in the hierarchy of sets studied in descriptive set theory.

We study the question ‘given a set A and an infinite string w, how hard is it to determine whether w ∈ A?’ in the context of infinite time Turing machines. We interpret this as the time needed to decide membership in A. What is the supremum of countable decision times? We give precise answers to this and related questions.

Concepts analogous to halting and decision times are ubiquitous in descriptive set theory in the form of ranks. A fundamental example is the rank of a wellorder on the natural numbers. I will explain how our results also work for such ranks and give applications in descriptive set theory on the level of Π11 and Σ12 sets.

This is joint work in progress with Philip Welch and Merlin Carl.