Sample1 Proposal for a Joint Summer Research Conference 1. Proposal submitted by: Steffen Lempp Department of Mathematics University of Wisconsin 480 Lincoln Drive Madison, WI 53706-1388 Phone (608) 263-1975 Fax (608) 263-8891 Email lempp@math.wisc.edu 2. Title of proposed conference: Computability Theory and Applications 3. Organizing committee: Peter Cholak, University of Notre Dame Steffen Lempp (co-chair), University of Wisconsin Manuel Lerman (co-chair), University of Connecticut Richard Shore (co-chair), Cornell University 4. Program information: 4.1. Program summary: Computability theory (or recursion theory) is the area of mathematical logic dealing with the theoretical bounds on, and structure of, computability and with the interplay between computability and definability in mathematical languages and structures. The field started in the 1930's with the ground-breaking work of G\"{o}del and Turing and has developed into a rich theory with applications and connections to areas ranging from computer science to descriptive set theory as well as more traditional branches of mathematics including algebra, analysis and combinatorics. There are many interesting notions that have some claim to be versions of the intuitive idea of an effective procedure, and each has its own place in the study of computability. There is, however, one notion that is accepted as the correct formalization of the idea of being computable by an arbitrary algorithm. This is the notion of computability defined by Turing machines or, equivalently, other standard models of computation. Other common notions of computability are usually defined by either restricting such computations in time or space (memory) or by enlarging them to include certain infinitary operations. We expect to concentrate on the fundamental notion of (Turing) computability as the basic measure of (relative) complexity. Our meeting will focus on classical computability theory in which many recent advances have been made and those applications which currently seem most directly connected to, and most likely to benefit from, these advances. In particular, applications in algebra, model theory and proof theory will be highlighted. 4.1.1. Pure computability theory: The pure classical theory concentrates on sets of, and functions on, the natural numbers {\bf N}. (Note here that most of the common countable structures in mathematics can be viewed as ones on the integers by ``coding", a trick going back to G\"odel's work.) The basic areas of interest here are the structure of sets or functions under the ordering of relative computability {\it (Turing reducibility)} and the relations between computational complexity and other measures of difficulty. These measures include the complexity of the definition of a set (for example, in arithmetic), set-theoretic properties, approximation procedures and rates of growth of functions. The equivalence classes of sets or functions under the relation of being computable from one another (i.e., by a Turing machine that has unlimited access to membership information about the other set or the values of the other function) are called the {\it (Turing) degrees}. Various substructures of the collection of all sets or degrees are of particular interest because of their connection with various types of approximations or definability. We begin with the {\it computable} (or {\it recursive}) subsets of, or functions on, {\bf N}. These are the ones whose membership (or values) can be determined effectively, e.g., by a Turing machine. This is equivalent to the membership (or functional) relation being definable by both an existential and a universal formula in the language of arithmetic. The {\it computably enumerable} (or {\it recursively enumerable}) sets are those whose members can be listed by a Turing machine or, equivalently, whose membership relation is definable by an existential formula in the language of arithmetic. Another important class is that of the functions with computable approximations (i.e., approximations that eventually stabilize at the correct answer). These are the functions that are definable by both existential-universal and universal-existential formulas. They are also the ones computable from the Halting problem (the set of indices of computer programs that eventually halt). The next steps up iterate the relativized Halting problem, generally called the {\it Turing jump}. Each iteration corresponds to the next level of quantifier complexity of a set's definition in arithmetic. The union of the finite iterations corresponds to definability in arithmetic. Transfinite iterations move on to definability in analysis, descriptive set theory, inductive definability, generalized recursion theory, admissibility and other areas. There have been a number of major advances in the understanding of these structures in the past few years, including a phenomenal number of solutions to problems that had been open for decades and had always been considered very hard. To name just a few on the structure of the degrees and relations to definability in arithmetic, Slaman and Woodin showed that there are at most countably many automorphisms of the Turing degrees; Cooper proved that several important apparently external notions, such as Turing jump and computable enumerability, are definable in the Turing degrees from the partial ordering alone; work of Shore and others (Nerode, Harrington, Jockusch) showed that almost all relations definable in second order arithmetic (e.g., those well defined up to some number of jumps or those on only degrees above some number of jumps of the empty set) are actually definable in the degrees just from the ordering; Nies, Shore and Slaman have recently shown that a similar definability result hold for the computably enumerable degrees. On the other hand, Cooper has recently claimed that there is a nontrivial automorphism of the Turing degrees and indeed of the computably enumerable degrees that shows that these definability results are, in a certain way, the best possible. If Cooper's construction can be understood and applied elsewhere it will provide an entry into a whole new realm of nondefinability results. In the area of relations between degrees and set-theoretic properties, we point particularly to a series of papers now coming out by Harrington and Soare. They show, for example, that there is a set-theoretic property of computably enumerable sets ensuring that the set has degree strictly less than the halting problem. At the level of investigation of the algebraic structure of these orderings, the Turing degrees and most of the substructures are quite well understood (the embedding questions for partial orderings, lattices and initial segments are almost all solved; the two quantifier theory is generally decidable but not the three quantifier theory, etc.). The crucial open problems here are about the basic structure of the computably enumerable degrees. An important recent summary and extension of many of the older positive results is the solution to the extension of embeddings problem by Slaman and Soare. On the other hand, a number of very hard long-standing questions at the very next level of complexity remain open. We cite, in particular, the classification of the finite lattices embeddable into the computably enumerable degrees. Important recent progress in this area has been made by Lempp and Lerman but the remaining issues seem very difficult. This problem is also a crucial part of the decidability of the two quantifier theory of the computably enumerable degrees. (The three quantifier theory has recently been shown to be undecidable by Lempp, Nies, and Slaman.) 4.1.2. Computable mathematics: The area of applied computability theory on which we propose to concentrate might well be called computable mathematics. Generally speaking, one wishes to investigate the effective content of mathematical constructions and theorems, that is, to determine which procedures or relations are computable and the relative complexity of those that are not. One's studies may start with important individual classical structures such as {\bf N}, {\bf Z}, {\bf Q}, etc., and then move on to general classes of structures such linear orderings, Boolean algebras, groups, rings, fields, etc. Finally one reaches effective model theory which is a general approach to the issues of computability and effectiveness in the study of the construction and classification of structures and the relation between formal languages and axioms and their interpretations in these structures (models). A structure is computable if its underlying set and all the relations and functions being considered on it are computable. It is decidable if its entire theory (the set of all sentences in the language being considered with names for each element of the structure) that are true in the structure is computable. Important issues here include determining when a given structure has a computable (decidable) presentation, i.e., is isomorphic to a computable (decidable) structure. A classical example is provided by presentations of groups (in the usual group-theoretic sense of a presentation). Here the question of the group being computable is equivalent to the decidability of the word problem. On one hand, there are many results that give conditions on the group or its presentation that guarantee its computability. On the other hand, the celebrated results of Novikov and Boone on the undecidability of the word problem show that not all finitely presented groups are computable. More generally, the problems addressed deal with determining what properties of computable structures can be decided effectively from their presentations and, if not, on the possible limits on their complexity. Examples here include issues in linear algebra, factoring in polynomial fields and, in general, determinations of various dependency relations. There are many specific results establishing the interrelations among the computability properties of such notions depending on various properties of the structure in question (e.g., the dimension of the vector space or the transcendence degree of the field). Many important open questions ask for generalizations of these results and model-theoretic characterizations of the issues involved. These issues were studied in the U.S. mainly in the 1970's and more sporadically since then (primarily in the investigation of the particular structures of linear orderings and Boolean Algebras in the work of Downey, Jockusch, Knight, Lerman, Remmel, Soare and others). On the other hand, they have been the focal point of continuous investigations in computability theory in the former Soviet Union for the past forty years, with work by Ershov, Goncharov, Mal'tsev, and many others. With increasing communication between researchers in the West and in the former Soviet Union, there has been a revival of interest in the West in these areas. In particular, the technical methods developed in the West in pure computability theory have provided the tools to answer a number of important old problems in the area. We cite the nested priority arguments used in the work of Ash and Knight, priority tree constructions used in the recent work of Cholak, Goncharov, Knight, Khoussainov and Shore and the use of forcing constructions in the work of Ash, Cholak, Knight and Slaman. Thus the time seems appropriate to stress a combination of pure computability and its applications to computable mathematics. Another version of many of these questions is investigated in reverse mathematics as developed by H. Friedman and Simpson. This approach is, on its face, a proof-theoretic and foundational investigation into the axiomatic systems needed to prove standard theorems of classical mathematics. On closer scrutiny, one sees that many of the arguments and results in this area can also be viewed as ones in computable mathematics. There is an almost perfect translation between the proof-theoretic systems used and the established levels of complexity in computability. Each approach, however, contributes its own techniques and often produces results with overlapping but supplementary content. In particular, priority arguments produce constructions that theorems are not provable in {\it RCA}$_0$ (the system corresponding to computable structures and mathematics). (The early work of Nerode and his collaborators and the more recent results of Downey and others are good examples.) Results on $\Pi^0_1$ classes by Jockusch and Soare, Nerode and Remmel supply constructions for proving equivalences and nonequivalences with {\it WKL}$_0$. More recently, with the revival of interest in computable mathematics generally among pure computability theorists, there has been a revival in the issues of reverse mathematics. Forcing constructions combined with delicate priority arguments (Cholak, Jockusch and Slaman) have produced surprising results in the reverse mathematics of combinatorial problems like Ramsey's theorem. An important foundational issue is the existence of classical theorems not equivalent to any of the standard systems. It seems likely that further computability theoretic analyses using more delicate techniques can shed light on this area. We think it not only appropriate but important to try to bring the proof-theoretic and model-theoretic approaches developed in reverse mathematics and computability theory together at this time. 4.2. Conference description: As mentioned above, the past eight years have seen a phenomenal number of solutions to problems that had been open for decades and had always been considered very hard. On the other hand, a number of very hard long-standing questions remain open, such as the classification of the automorphism groups of the Turing degrees and various substructures, the classification of finite lattices embeddable into the computably enumerable degrees, and the classification of types in the Turing degrees and its substructures, to name only a few. On all of these problems, there have been some exciting developments recently, but complete solutions are at this time not in sight. We envision our conference to stimulate progress on these and other open problems. To this end, we propose a limited number of invited full-length lectures (say, five to ten), each focusing on one of the major open problems of pure and applied computability theory, and short talks on other open problems by most participants, each followed by longer breaks, thus allowing participants to further discuss these problems. 4.3. Partial list of speakers: The following participants have already been invited. (Those marked with an asterisk have already agreed to attend.) Note: This list, while included in the original proposal, has been deleted from this sample for reasons of confidentiality. 4.4. Recent conferences in same or closely related areas: Leeds Recursion Theory Colloquium, July 1994 Oberwolfach meeting in Recursion Theory, January 1996 Kazan Workshop in Recursion and Complexity Theory, July 1997 Special Sessions at AMS Meetings in Orlando (January 1996), and Milwaukee (October 1997), and Baltimore (January 1998) 4.5. Budget and estimated attendance: Assuming funding as budgeted, we expect to pay local expenses for all of the approximately sixty to seventy-five invited participants. The remainder of the budget will be used for those participants who have difficulties covering their transportation expenses to and from the conference site. Bibliography Ash, C. J., and Knight, J., {\it Ramified systems}, Ann.\ Pure and Appl.\ Logic {\bf 70} (1994), 205-221. Ash, C. J., Knight, J., Manasse, M., and Slaman, T., {\it Generic copies of countable structures}, Ann.\ Pure and Appl.\ Logic {\bf 42} (1989), 195-205. Ash, C. J., Cholak, P., and Knight, J., {\it Permitting, forcing, and copies of a given recursive relation} (to appear). Cholak, P., Downey, R., and Harrington, L., {\it Automorphisms of the computably enumerable sets: $\Sigma^{1}_{1}$-completeness} (in preparation). Cholak, P., Jockusch, C., and Slaman, T., {\it Ramsey's theorem for pairs} (to appear). Cholak, P., Goncharov, S. Khoussainov, B. and Shore R. A., {\it Computably categorical structures and extensions by constants} (to appear). Cooper, S. B., {\it The jump is definable in the structure of the degrees of unsolvability (research announcement)}, Bull.\ Amer.\ Math.\ Soc.\ {\bf 23} (1990), 151-158. Cooper, S. B., {\it Beyond G{\"o}del's theorem: the failure to capture information content}, University of Leeds, Department of Pure Mathematics Preprint Series, No. 4. Downey, R. G. and Jockusch, C. G., {\it Every low Boolean algebra is isomorphic to a recursive one}, Proc. Amer. Math. Soc.\ {\bf 122} (1994), 871-880. Er{\v s}ov, Yu.\ L., {\it Theory of Numerations 3 (Constructive Models)}, Novosibirsk State University, 1974. Er{\v s}ov, Yu.\ L., {\it Decision Problems and Constructivizable Models}, 1980. Goncharov, S. S., {\it Countable Boolean Algebras and Decidability}, Plenum, 1998. Goncharov, S. S., {\it Constructive Models}, Plenum, 1998. Harrington, L., Morley, M. D., Scedrov, A. and Simpson S. G., eds., {\it Harvey Friedman's research in the foundations of mathematics}, North-Holland, Amsterdam, 1985. Harrington, L. and Shore, R. A., {\it Definable degrees and automorphisms of $\cal D$}, Bull.\ Amer.\ Math.\ Soc.\ (N. S.) {\bf 4} (1981), 97-100. Jockusch, C. G. and Soare, R. I., {\it Degrees of orderings not isomorphic to recursive linear orderings}, Ann. Pure Appl. Logic {\bf 52} (1991), 39-64. Jockusch, C. G. and Soare, R. I., {\it Boolean algebras, Stone spaces, and the iterated Turing jump}, J. Symbolic Logic {\bf 59} (1994), 1121-1138. Jockusch, C. G. Jr. and Shore, R. A., {\it Pseudo-jump operators II: Transfinite iterations, hierarchies and minimal covers}, J. Symbolic Logic {\bf 49} (1984), 1205-1236. Jockusch, C. G. Jr. and Soare, R. I., {\it Degrees of members of $\Pi^0_1$ classes}, Pacific J. Math.\ {\bf 40} (1972), 605-616. Jockusch, C. G. Jr. and Soare, R. I., {\it $\Pi^0_1$ classes and degrees of theories}, Trans.\ Amer.\ Math.\ Soc.\ {\bf 173} (1972), 33-56. Jockusch, C. G. and Soare, R. I., {\it Degrees of orderings not isomorphic to recursive linear orderings}, Ann.\ Pure Appl.\ Logic {\bf 52} (1991), 39-64. Jockusch, C. G. and Soare, R. I., {\it Boolean algebras, Stone spaces, and the iterated Turing jump,} J. Symbolic Logic {\bf 59} (1994) 1121--1138. Khoussainov, B. and Shore, R. A., {\it Computable isomorphisms, degree spectra of relations and Scott families}, Ann.\ Pure Appl.\ Logic (to appear). Knight, J., {\it A metatheorem for construction by finitely many workers}, J. Symbolic Logic {\bf 55} (1990), 787-804. Knight, J., {\it Constructions for transfinitely many workers}, Ann.\ Pure Appl.\ Logic {\bf 46} (1990), 211-234. Knight, J., {\it Requirement systems}, J. Symbolic Logic {\bf 60} (1995), 222-245. Lempp, S. and Lerman, M., {\it A finite lattice without critical triples that cannot be embedded into the enumerable Turing degrees}, Ann.\ Pure Appl.\ Logic (to appear). Lempp, S., Nies, A. and Slaman, T., {\it The $\Pi _{3}$ theory of the enumerable Turing degrees is undecidable}, Trans.\ Amer.\ Math.\ Soc.\ (to appear). Lerman, M., {\it On recursive linear orderings}, in Lerman, M., Schmerl, J.H. and Soare, R.I., {\it Logic Year 1979-80,} Springer-Verlag Lecture Notes in Math.\ {\bf 850}, 1981. Mal'tsev, A. I., {\it Constructible algebras. I,} Uspekhi Mat. Nauk {\bf 16}(3) (1961), 3--60. Mal'tsev, A. I., {\it Algebraic Systems,} Springer-Verlag, 1973. Marek, W., Nerode, A., and Remmel, J. B., {\it A theory of non-monotonic rule systems I}, Ann.\ Math.\ and Artificial Intelligence {\bf 1} (1990), 241-273. Marek, W., Nerode, A., and Remmel, J. B., {\it A theory of non-monotonic rule systems II}, Ann.\ Math.\ and Artificial Intelligence {\bf 5} (1992), 229-263. Metakides, G., and Nerode, A., {\it Effective content of field theory}, Ann.\ Math.\ Logic {\bf 17} (1979), 289-320. Metakides, G., and Nerode, A., {\it Recursion theory on fields and abstract dependence}, J. of Algebra {\bf 65} (1980), 36-59. Nies, A., Shore R. A. and Slaman, T., {\it Definability in the recursively enumerable degrees}, Bull.\ Symbolic Logic {\bf 2} (1996), 392-404. Nies, A., Shore R. A. and Slaman, T., {\it Interpretability and definability in the recursively enumerable degrees}, Proc.\ London Math.\ Soc.\ (to appear). Nerode, A. and Shore, R. A., {\it Second order logic and first order theories of reducibility orderings}, in {\it The Kleene Symposium}, J. Barwise, H.J. Keisler and K. Kunen, eds., North-Holland, 1980, 181-200. Nerode, A. and Shore, R. A., {\it Reducibility orderings: theories, definability and automorphisms}, Ann.\ Math.\ Logic {\bf 18} (1980), 61-89. Remmel, J. B., {\it Recursive isomorphism types of recursive Boolean algebras,} J. Symbolic Logic {\bf 46} (1981), 572--594. Remmel, J. B., {\it Recursion theory on orderings II,} J. Symbolic Logic {\bf 45} (1980) 317--333. Remmel, J. B., {\it Recursive Boolean algebras}, in {\it Handbook of Boolean Algebras} {\bf 3} (1980), 1097-1165. Shore, R. A., {\it The degrees of unsolvability: the ordering of functions by relative computability}, in {\it Proceedings of the International Congress of Mathematicians (Warsaw) 1983}, PWN-Polish Scientific Publishers, Warsaw 1984, Vol.\ 1, 337-346. Simpson, S. G., ed., {\it Logic and Combinatorics, Contemporary Mathematics} {\bf 65}, American Mathematical Society, Providence, 1985. Slaman, T. A., {Degree structures}, in {\it Proc. Int. Cong. Math., Kyoto 1990}, Springer-Verlag, Tokyo, 1991, 303-316. Slaman, T. A. and Soare, R. I., {\it Algebraic aspects of the computably enumerable degrees}, Proc.\ Natl.\ Acad.\ Sci.\ {\bf 92} (1995), 617-621. Slaman, T. A. and Soare, R. I., {\it Extension of embeddings in the recursively enumerable degrees}, Ann.\ of Math.\ (to appear). Slaman, T. A. and Woodin, W. H., {\it Definability in Degree Structures} (in preparation).

12/17/1999 Comments: pop@ams.org © Copyright 1999, American Mathematical Society.