Projects in Previous Years

2nd Semester 2006/07: Infinitary Computation

Joel David Hamkins
If you are interested in this project, please contact Joel by e-mail.
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 :lassical computability. The model gives rise to a robust theory of infinitary computability on the reals, such as notions of computability for functions f:R->R and notions of decidability for sets A subset R, exhibiting a rich degree structure. In this project, we will explore the basic results in the area, including the recent development of infinitary complexity theory, with the corresponding solution of the infinitary analogue of P vs. NP. Students in this project will read and make presentations based on recent research journal articles, and write a brief expository paper of their own.