Professor Shore's 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. He has 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 his 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 his 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 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.