Richard A. Shore

Professor of Mathematics

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, f <_T 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 such 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 or set theory. The methods developed in 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 theoretic terms.

Professional Activities:

• Member of the AMS, ASL, ACM and SIGACT.
• Referee and reviewer for the NSF, the Natural Sciences and Engineering Research Council of Canada, the US-Israeli Bi-National Science Foundation, the New Zealand Mathematical Society Research Awards and many journals.
• Editor of the Journal of Symbolic Logic (1989-93).
• Nominating committee and publications committee of the Association of Symbolic Logic (1993-94).
• Managing editor for the Bull. Symbolic Logic (1993-).
• Council member of the Assn. Symbolic Logic (1984-).
• Editor of Studies in Logic and the Foundations of Mathematics, North-Holland (1996-).

Selected Publications:

• alpha-Recursion Theory, in Handbook of Mathematical Logic, J.Barwise ed., North-Holland, 1977, 653-680.

• The Homogeneity Conjecture, Proceedings of the National Academy of Sciences 76 (1979), 4218-4219.

• Definable Degrees and Automorphisms of D, Bull. Amer. Math. Soc. (NS) 4 (1981), 97-100 (with L. Harrington).

• The Degrees of Unsolvability: the Ordering of Functions by Relative Computability, in Proc. Inter. Congress of Mathematicians (Warsaw) 1983, PWN-Polish Scientific Publishers, Warsaw 1984, Vol. 1, 337-346.

• The Structure of the Degrees of Unsolvability, in Recursion Theory, Proceedings of the Symposia in Pure Mathematics 42, A. Nerode and R.A. Shore, eds., American Mathematical Society,Providence, R.I., 1985, 33-51.

• Recursive Limits on the Hahn-Banach Theorem, Contemporary Mathematics 39 (1985), 85-91 (with A. Nerode and G. Metakides).

• On the Strength of König's Duality Theorem for Infinite Bipartite Graphs, J. Comb. Theory (B) 54 (1992), 257-290 (with R. Aharoni and M. Magidor).

• The p-T-degrees of the Recursive Sets: Lattice Embeddings, Extension of Embeddings and the Two Quantifier Theory, Theoretical Computer Science 97 (1992), 263-284 (with T. Slaman).

• Logic for Applications, Texts and Monographs in Computer Science, Springer-Verlag, New York, 1993 (with A. Nerode).

• Definability in the recursively enumerable degrees, Bull. Symb. Logic 2 (1996), 392-404, (with A. Nies and T. Slaman).

• Computable Isomorphisms, Degree Spectra of Relations, and Scott Families, Ann. of Pure Applied Logic, to appear (with B. Khoussainov).