Richard A. Shore

Goldwin Smith Professor Emeritus of Mathematics

Research Focus

Mathematical logic, recursion theory, effective and reverse mathematics, set theory

My 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. Another interesting current application of these approaches has been to produce very elementary proofs of Ramsey type combinatorial theorems that previously only had proofs using ultrafilters and other even high order notions and structures.

Publications

  • The Limits of Determinacy in Second Order Arithmetic: Consistency and Complexity Strength (with A. Montalban), Israel Journal of Mathematics, 204 (2014), 477-508.
  • Reverse mathematics: the playground of logic, Bulletin of Symbolic Logic 16 (2010), 378–402.
  • Direct and local definitions of the Turing jump, Journal of Mathematical Logic 7 (2007), 229–262.
  • Degree structures: local and global investigations, Bulletin of Symbolic Logic 12 (2006), 369–389.
  • Combinatorial principles weaker than Ramsey’s Theorem for pairs (with D. Hirschfeldt), Journal of Symbolic Logic 72 (2007), 171–206.
  • Boolean algebras, invariants and ACA_0^+, Transactions of the American Mathematical Society 358 (2006), 989–1014.
  • 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.
  • 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.
  • The 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.