 |
 |
 |
|||||||||||||||||||||||||||
|
 |
||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||
|
EducationPh.D. (1972) Massachusetts Institute of Technology Research Area: Mathematical logic, recursion theory, effective and reverse mathematics, set theoryMy major research interests have centered around analyzing the structures of relative complexity of computation of functions on the natural numbers. The primary measure of such complexity is given by Turing reducibility: f is easier to compute than g, if there is a (Turing) machine which can compute f if it is given access to the values of g. I have also worked with various other interesting measures of complexity that are defined by restricting the resources available primarily in terms of access to g. The general thrust of my work has been to show that these structures are as complicated as possible both algebraically and logically (in terms of the complexity of the decision problems for their theories). These results also allow one to differentiate among different notions of relative complexity in terms of the orderings they define. Another major theme in my work has been the relationship between these notions of computational complexity and ones based on the difficulty of defining functions in arithmetic. Restricting the computational resources more directly in terms of time or space leads out of recursion theory and into complexity theory. Relaxing the restrictions by allowing various infinitary procedures leads instead into generalized recursion theory and set theory. I have also worked on issues in effective model theory and algebra connected with the problem of how the computational properties of algebraic structures can vary with different (but always computable) presentations of the models. The methods developed in many of these investigations are also useful in determining the effective content of standard mathematical theorems (when can existence proofs be made effective) and the inherent difficulty of combinatorial theorems in proof as well as complexity theoretic terms. Recently, I have been working on classifying results in algebra, combinatorics and logic in these "reverse mathematics" settings. I have been particularly interested in ones that are incomparable with the standard theories typically found in such work. Selected PublicationsThe degrees of unsolvability: the ordering of functions by relative computability; in Proceedings of the International Congress of Mathematicians (Warsaw) 1983, PWN-Polish Scientific Publishers, Warsaw 1984, Vol. 1, 337–346. Logic for Applications (with A. Nerode), Texts and Monographs in Computer Science, Springer-Verlag, New York, 1993; second edition, Graduate Texts in Computer Science, Springer-Verlag, New York, 1997. Computable structures: presentations matter; In the Scope of Logic, Methodology and the Philosophy of Science, Vol. 1, International Congress of LMPS, Cracow, August 1999 (P. Gardenfors, J. Wolenski and K. Kijania-Placek, eds.), Synthese Library 315, Kluwer Academic Publishers, Dordrecht, 2002, pp. 81–95. Boolean algebras, invariants and ACA_0^+, Transactions of the American Mathematical Society 358 (2006), 989–1014. Combinatorial principles weaker than Ramsey’s Theorem for pairs (with D. Hirschfeldt), Journal of Symbolic Logic 72 (2007), 171–206. Degree structures: local and global investigations, Bulletin of Symbolic Logic 12 (2006), 369–389. Local definability in degree structures: the Turing jump, hyperdegrees and beyond, Bulletin of Symbolic Logic 13 (2007), 226–239. Last modified: October 31, 2006 |
